Candidate Talk: Critical percolation on finite graphs

  • Asaf Nachmias | UC Berkeley

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.

Speaker Details

Asaf Nachmias is a Mathematics graduate student at UC Berkeley under the supervision of Prof. Yuval Peres and conducting research in Probability theory and Combinatorics. His current favorite hobby is to cook a wicked stirfry dinner with almost any leftovers in the kitchen, blasting Tom Waits in the background.

Watch Next