Campuses:

The Phase Transition in Site Percolation on Pseudo-Random Graphs

Friday, September 12, 2014 - 10:15am - 11:05am
Keller 3-180
Michael Krivelevich (Tel Aviv University)
We establish the existence of the phase transition in site percolation on pseudo-random d-regular graphs. Let G=(V,E) be an (n,d,lambda)-graph, that is, a d-regular graph on n vertices in which all eigenvalues of the adjacency matrix, but the first one, are at most lambda in their absolute values. Form a random subset R of V by putting every vertex v in V into R independently with probability p. Then for any small enough constant epsilon>0, if p=(1-epsilon)/d, then with high probability all connected components of the subgraph of G induced by R are of size at most logarithmic in n, while for p=(1+epsilon)/d, if the eigenvalue ratio lambda/d is small enough as a function of epsilon, then typically R contains a connected component of size at least epsilon n/d and a path of length proportional to epsilon^2n/d.
MSC Code: 
68Q87