***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Sahar Diskin (Tel Aviv U)

Thursday 19th September, 3:00 in Fine Hall 224.

Title: Component sizes in percolation on finite regular graphs

A classical result by Erdos and Renyi 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 the 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.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)