Mean-field conditions for percolation on finite graphs
| dc.creator | Nachmias, Asaf | |
| dc.date | 2007-09-11 | |
| dc.date | 2008-11-25 | |
| dc.date.accessioned | 2026-07-07T10:20:22Z | |
| dc.date.available | 2026-07-07T10:20:22Z | |
| dc.description | Let G_n be a sequence of finite transitive graphs with vertex degree d=d(n) and |G_n|=n. Denote by p^t(v,v) the return probability after t steps of the non-backtracking random walk on G_n. We show that if p^t(v,v) has quasi-random properties, then critical bond-percolation on G_n has a scaling window of width n^{-1/3}, as it would on a random graph. A consequence of our theorems is that if G_n is a transitive expander family with girth at least (2/3 + eps) \log_{d-1} n, then the size of the largest component in p-bond-percolation with p={1 +O(n^{-1/3}) \over d-1} is roughly n^{2/3}. In particular, bond-percolation on the celebrated Ramanujan graph constructed by Lubotzky, Phillips and Sarnak has the above scaling window. This provides the first examples of quasi-random graphs behaving like random graphs with respect to critical bond-percolation. | |
| dc.description | 29 pages. to appear in Geometric and Functional Analysis | |
| dc.identifier | https://arxiv.org/abs/0709.1719 | |
| dc.identifier | http://arxiv.org/abs/0709.1719 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/174822 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.title | Mean-field conditions for percolation on finite graphs | |
| dc.type | text |