Cycle saturation in random graphs

Abstract

For a fixed graph $F,$ the minimum number of edges in an edge-maximal $F$-free subgraph of $G$ is called the $F$-saturation number. The asymptotics of the $F$-saturation number of the binomial random graph $G(n,p)$ for constant $p\in (0,1)$ is known for complete graphs $F=K_m$ and stars $F=K_{1,m}.$ This paper is devoted to the case when the pattern graph $F$ is a simple cycle $C_m.$ We prove that, for $m⩾5,$ whp $\mathrm{sat}\left(G\left(n,p\right),C_m\right)=n+\Theta \left(\frac{n}{\ln n}\right).$ Also we find $c=c(p)$ such that whp $\frac{3}{2}n(1+o(1))⩽\mathrm{sat}\left(G\left(n,p\right),C_4\right)⩽cn(1+o(1)).$ In particular, whp $\mathrm{sat}\left(G\left(n,\frac{1}{2}\right),C_4\right)⩽\frac{27}{14}n(1+o(1)).$