Title:
Weak saturation and collapsible complexes in a random graph
Abstract:
Let H, G be two graphs. A spanning subgraph G’ of G is called weakly H-saturated if the following holds: one can add to G' the edges of G \ G’ in some order so that whenever a new edge is added, a new copy of H is formed.
Obtaining lower bounds for the size of such a G’ (for various H and G) is a classical problem in extremal combinatorics.
In particular, in the past 40 years, various algebraic tools have been used in order to prove such lower bounds.
Our first contribution in this work unravels a new algebraic/topological connection which can be used in order to prove the following result.
Let w-sat(t,G) be the size of a smallest weakly K_t-saturating subgraph of G.
Korandi and Sudakov asked to determine the threshold probability for the property that w-sat(t,G(n,p))=w-sat(t,K_n).
Using our new observation, in the case t=3, we show that the threshold probability is located at p=n^{-1/3 +/- o(1)}.
Moreover, using an argument inspired by Gromov's `local to global' theorem, we determine, up to a multiplicative constant factor, the threshold probability for a bounded diameter version of the theorem.
Interestingly, our new connection between weak saturation and topological properties goes both ways since it also enables us to use combinatorial arguments in order to obtain new results concerning topological properties of random clique complexes.
In particular, we obtain a new upper bound on the threshold probability for simple connectivity of the 2-dimensional clique complex of G(n,p), improving a result of Khale.
Joint work with Yuval Peled, Asaf Shapira, Mykhaylo Tyomkyn, and Maksim Zhukovskii.