First passage percolation has sublinear distance variance

Benjamini, Itai ; Kalai, Gil ; Schramm, Oded

Ann. Probab., Tome 31 (2003) no. 1, p. 1970-1978 / Harvested from Project Euclid

Résumé

Let $0 < a < b < \infty$, and for each edge e of $\Z^d$ let $\omega_e=a$ or $\omega_e=b$, each with probability $1/2$, independently. This induces a random metric $\dist_\omega$ on the vertices of $\Z^d$, called first passage percolation. We prove that for $d>1$, the distance $\dist_\omega(0,v)$ from the origin to a vertex $v$, $|v|>2$, has variance bounded by $C|v|/\log|v|$, where $C=C(a,b,d)$ is a constant which may only depend on a, b and d. Some related variants are also discussed.

Détail

Publié le : 2003-10-14
Classification:  Hypercontractive,  harmonic analysis,  discrete harmonic analysis,  discrete cube,  random metrics,  discrete isoperimetric inequalities,  influences,  60K35,  60B15,  28A35,  60E15