Weak saturation numbers in random graphs

Abstract

For two given graphs $G$ and $F$, a graph $H$ is said to be weakly $(G,F)$-saturated if $H$ is a spanning subgraph of $G$ which has no copy of $F$ as a subgraph and one can add all edges in $E(G)\setminus E(H)$ to $H$ in some order so that a new copy of $F$ is created at each step. The weak saturation number $wsat(G,F)$ is the minimum number of edges of a weakly $(G,F)$-saturated graph. In this paper, we deal with the relation between $wsat(G(n,p),F)$ and $wsat(K_n,F)$, where $G(n,p)$ denotes the Erdős--Rényi random graph and $K_n$ denotes the complete graph on $n$ vertices. For every graph $F$ and constant $p$, we prove that $wsat(G(n,p),F)=wsat(K_n,F)(1+o(1))$ with high probability. Also, for some graphs $F$ including complete graphs, complete bipartite graphs, and connected graphs with minimum degree $1$ or $2$, it is shown that there exists an $\epsilon (F)>0$ such that, for any $p⩾n^{-\epsilon (F)}\log n$, $wsat(G(n,p),F)=wsat(K_n,F)$ with high probability.

The only difference with the previous file is here that the grant number of the first author was wrong and is corrected now