The triangle-edge dichotomy conjecture for saturation numbers in random graphs

Let $G(n,p)$ be the binomial random graph, let $F$ be a graph, and let $\operatorname{sat}(G,F)$ denote the minimum number of edges in an inclusion-maximal $F$-free subgraph of $G$. Here, $\textbf{whp}$ means with high probability as $n\to\infty$.

Triangle-edge dichotomy conjecture. Let $0<p<1$ be a constant. If every edge of $F$ belongs to a triangle in $F$, then, with high probability,

$$\operatorname{sat}(G(n,p),F)=\Theta(n\ln n).$$

If some edge of $F$ does not belong to a triangle in $F$, then, with high probability,

$$\operatorname{sat}(G(n,p),F)=O(n).$$

The paper proves the $O(n\ln n)$ upper bound for every fixed graph $F$, the $\Theta(n\ln n)$ order when every edge of $F$ belongs to a triangle, and the $O(n)$ bound for a large family including all bipartite graphs. The conjecture asserts that these two structural conditions completely determine the asymptotic order.