Abstract:

Let G be a d-regular graph of growing degree on n vertices. Form a random subgraph G_p of G by retaining each edge independently with probability p=p(d). Which conditions suffice to observe a phase transition at p=1/d, similar to that in the binomial random graph G(n,p)?
We argue that in the supercritical regime p=(1+epsilon)/d, epsilon>0 a small constant, it suffices that every subset S of G of at most n/2 vertices has edge-boundary of size at least C|S|, for some large enough constant C=C(epsilon)>0, to guarantee the likely appearance of the giant component in G_p. Moreover, its asymptotic order is equal to that in the random graph G(n,(1+epsilon)/n), and all other components are typically much smaller.
We further give examples demonstrating the tightness of this result in several key senses.
Joint work with Joshua Erde, Mihyun Kang, and Michael Krivelevich.