Candidate Talk: Critical percolation on finite graphs

Speaker  Asaf Nachmias

Host  Jennifer Chayes

Affiliation  UC Berkeley

Duration  01:02:17

Date recorded  4 January 2008

Bond percolation on a graph G with parameter p in [0,1] is the random subgraph Gp of G obtained by independently deleting each edge with probability 1-p and retaining it with probability p. For many graphs, the size of the largest component of Gp exhibits a phase transition: it changes sharply from logarithmic to linear as p increases. When G is the complete graph, this model is known as the Erdos-Renyi random graph: at the phase transition, i.e. p=1/n, the largest component satisfies a power-law of order 2/3.

For which d-regular graphs does percolation with p=1/(d-1) exhibit similar "mean-field" behavior? We show that this occurs for graphs where the probability of a non-backtracking random walk to return to its initial location behaves as it does on the complete graph. In particular, the celebrated Lubotzky-Phillips-Sarnak expander graphs and Cartesian products of 2 or 3 complete graphs exhibit mean-field behavior at p=1/(d-1); surprisingly, a product of 4 complete graphs does not.

©2008 Microsoft Corporation. All rights reserved.
> Candidate Talk: Critical percolation on finite graphs