Critical percolation on finite graphs

Опубликовано 6 сентября 2016, 16:54

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 1-p 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 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.