Weak saturation in sparse random graphs

The notion of weak saturation was introduced in 1968 by Bollobas. Let $H$ be a spanning subgraph of a graph $G$, and $F$ be a pattern graph. $H$ is called weakly $F$-satured in $G$, if the edges of $G \setminus H$ may be added back one by one in a way such that every edge creates a new copy of $F$. The smallest number of edges in a weakly $F$-satured graph in $G$ is called a weak saturation number and is denoted by w-sat $(G, F)$.

Bollobas conjectured that w-sat $(K_n, K_s)=(s-2)n-{{s-1}\choose 2}$. This conjecture was proved by P. Frankl in 1982. Unexpectedly, w-sat is stable: if we remove edges from $K_n$ independently with constant probability, the weak saturation number does not change. This result was proven by Korandi and Sudakov in 2016. More formally, for every constant $p \in (0,1)$ , a.a.s. w-sat $(G(n,p), K_s)$ w-sat$(K_n, K_s)=(s-2)n-{{s-1}\choose 2}$. They also noticed that the same is true for $n^{-\varepsilon(s)}\le p \le 1$ for certain small enough $\varepsilon(s)>0$ and ask about smaller $p$ and about possible threshold for the property w-sat$(G(n,p), K_s)=(s-2)n-{{s-1}\choose 2}$.

We prove that the threshold exists. Moreover,

if $p\ge n^{-\frac{1}{2s-3}}[\ln n]^\frac{8}{5}$, then a.a.s. w-sat $(G(n,p), K_s=(s-2)n-{{s-1}\choose 2}$;

if $p\le n^{-\frac{2}{s+1}}[\ln n]^\frac{2}{(s-2)(s+1)}$, then a.a.s. w-sat $(G(n,p), K_s\ne(s-2)n-{{s-1}\choose 2}$.

Joint work with Mohamad Reza Bidgoli.

Дополнительные материалы: maksim_zhukovskii_w_sat_k_n_random.pdf (4.9 Mb)