
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 G_{p} of G obtained by independently deleting each edge with probability 1p and retaining it with probability p. For many graphs, the size of the largest component of G_{p} 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 ErdosRenyi random graph: at the phase transition, i.e. p=1/n, the largest component satisfies a powerlaw of order 2/3. For which dregular graphs does percolation with p=1/(d1) exhibit similar "meanfield" behavior? We show that this occurs for graphs where the probability of a nonbacktracking random walk to return to its initial location behaves as it does on the complete graph. In particular, the celebrated LubotzkyPhillipsSarnak expander graphs and Cartesian products of 2 or 3 complete graphs exhibit meanfield behavior at p=1/(d1); surprisingly, a product of 4 complete graphs does not.
©2008 Microsoft Corporation. All rights reserved.
