Speaker: Sahar Diskin (Tel-Aviv University)

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 − ϵ)/n, where ϵ > 0 is a
constant, all connected components are typically logarithmic in n, whereas for p = (1 + ϵ)/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 Gp of
specific host graphs G, such as the d-dimensional binary hypercube, random d-regular graphs,
and pseudo-random (n, d, λ)-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.