Aspects of first passage percolation. (English) Zbl 0602.60098

Kesten, Harry

É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

MSC:

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

Keywords:

survey paper; first-passage percolation theory; shape problem; asymptotic growth rate; large-deviation theory; randomly-capacitated networks; list of open problems

Citations:

Zbl 0579.00013