A Jump of the Saturation Number in Random Graphs?

Abstract

For graphs $G$ and $F$, the saturation number $\text{sat}(G,F)$ is the minimum number of edges in an inclusion-maximal $F$-free subgraph of $G$. In 2017, Korándi and Sudakov initiated the study of saturation in random graphs. They showed that for constant $p\in (0,1)$, whp $\text{sat}\left(G(n,p),K_s\right)=\left(1+o(1)\right)n{\log }_{\frac{1}{1-p}}n$. We show that for every graph $F$ and every constant $p\in (0,1)$, whp $\text{sat}\left(G(n,p),F\right)=O(n\ln n)$. Furthermore, if every edge of $F$ belongs to a triangle, then the above is the right asymptotic order of magnitude, that is, whp $\text{sat}\left(G(n,p),F\right)=\Theta (n\ln n)$. We further show that for a large family of graphs $\mathcal{F}$ with an edge that does not belong to a triangle, which includes all the bipartite graphs, for every $F\in \mathcal{F}$ and constant $p\in (0,1)$, whp $\text{sat}\left(G(n,p),F\right)=O(n)$. We conjecture that this sharp transition from $O(n)$ to $\Theta (n\ln n)$ depends only on this property, that is, that for any graph $F$ with at least one edge that does not belong to a triangle, whp $\text{sat}\left(G(n,p),F\right)=O(n)$. We further generalise the result of Korándi and Sudakov, and show that for a more general family of graphs ${\mathcal{F}}^{\prime }$, including all complete graphs $K_s$ and all complete multipartite graphs of the form $K_{1,1,s_3,\dots ,s_{\ell }}$, for every $F\in {\mathcal{F}}^{\prime }$ and every constant $p\in (0,1)$, whp $\text{sat}\left(G(n,p),F\right)=\left(1+o(1)\right)n{\log }_{\frac{1}{1-p}}n$. Finally, we show that for every complete multipartite graph $K_{s_1,s_2,\dots ,s_{\ell }}$ and every $p\in \left[\frac{1}{2},1\right)$, $\text{sat}\left(G(n,p),K_{s_1,s_2,\dots ,s_{\ell }}\right)=\left(1+o(1)\right)n{\log }_{\frac{1}{1-p}}n$.