Aspects of first passage percolation. (English) Zbl 0602.60098

École d’été de probabilités de Saint-Flour XIV - 1984, Lect. Notes Math. 1180, 125-264 (1986).
[For the entire collection see Zbl 0579.00013.]
This is largely a survey paper of the advancing boundary of first-passage percolation theory, containing also many new results and insights. Particular emphasis is placed upon the shape problem: What can be said about the asymptotic growth rate of the set of points attainable from the origin in less than time t, as \(t\to \infty ?\) There are careful discussions of some progress towards a small-deviation theorem for first- passage times, as well as a revised account of the large-deviation theory.
In two dimensions, first-passage percolation is basically equivalent to a problem in flows through randomly-capacitated networks. This suggests the problem of studying the network flow problem in its own right in higher dimensions. Certain results are reported in this direction. The paper terminates with a list of open problems.
Reviewer: G.Grimmett


60K35 Interacting random processes; statistical mechanics type models; percolation theory
60F10 Large deviations


Zbl 0579.00013