First-passage percolation (Q4444983)

This paper is devoted to the description and the proof of the important ``shape theorem'' in the study of first passage percolation. In this stochastic growth model, generalization of ordinary percolation, the edges \(e\) of \(\mathbb Z^d\) are equipped with ``passage time'', i.i.d. random variables \(t(e)\) of common distribution \(F\). Passage times generalize for paths, points and hyperplane, and the fundamental object of study is the set \(B(t)\) of points which can be reached before time \(t\). Under mild assumptions on \(F\) (a bit weaker than having a first moment), the shape theorem states that there exists a non-random convex set with non-empty interior towards which the renormalized \(B(t)/t\) converges in a suitable sense. When \(F(0)\) is bigger than the critical Bernoulli bond percolation, the spread is too fast and the asymptotic shape is \(\mathbb{R}^d\), otherwise it is compact. The main part of this paper is devoted to a complete rigorous proof of this shape theorem. It is based on Kigman's subadditive ergodic theorem, concentration of measures and a careful treatment of bounds for large and moderate deviations. The proof is completed by many remarks and open problems. For the entire collection see [Zbl 1024.00032].