Title: Component sizes in percolation on finite regular graphs
Abstract: A classical result by Erdős and Rényi from 1960 shows that the binomial random graph G(n,p) undergoes a fundamental phase transition in its component structure when the expected average degree is around 1 (i.e., around p=1/n). Specifically, for p = (1-\epsilon)/n, where \epsilon > 0 is a constant, all connected components are typically logarithmic in n, whereas for p = (1+\epsilon)/n a unique giant component of linear order emerges, and all other components are of order at most logarithmic in n.
A similar phenomenon — the typical emergence of a unique giant component surrounded by components of at most logarithmic order — has been observed in random subgraphs G_p of specific host graphs G, such as the d-dimensional binary hypercube, random d-regular graphs, and pseudo-random (n,d,\lambda)-graphs, though with quite different proofs.
This naturally leads to the question: What assumptions on a d-regular n-vertex graph G suffice for its random subgraph to typically exhibit this phase transition around a critical probability p=1/(d-1)? Furthermore, is there a unified approach that encompasses these classical cases? In this talk, we demonstrate that it suffices for G to have mild global edge expansion and (almost-optimal) expansion of sets of (poly-)logarithmic order in n. This result covers many previously considered concrete setups.
We also discuss the tightness of our sufficient conditions.
Joint work with Michael Krivelevich.