first-passage percolation and the time constant
First-passage percolation (FPP) replaces the open/closed dichotomy of Bernoulli percolation with random PASSAGE TIMES on the edges, turning percolation into a model of a random metric and of spreading growth. It is the canonical model for fluid seeping through a random medium, for the shortest route across a noisy network, and for the growth of an infection — and it is the probabilist's gateway to the famous KPZ universality class of random growth. The central question is how far fluid has spread by time t, and how rough the spreading front is.
Assign to each edge e of Z^d an independent nonnegative random passage time tau(e) from a common distribution F. The first-passage time T(x,y) between two vertices is the minimum over all paths from x to y of the sum of passage times along the path — a random graph metric. The basic limit law is the time constant: under mild moment conditions, T(0, n e_1)/n converges almost surely and in L^1 to a deterministic constant mu(F) (the time constant in the direction e_1), and more generally T(0, x)/|x| has a directional limit. This is a consequence of Kingman's subadditive ergodic theorem, since T is subadditive: T(0, x+y) <= T(0,x) + T(x, x+y). The Cox-Durrett shape theorem upgrades this to a law of large numbers for the whole growing ball: the set of vertices reachable by time t, rescaled by t, converges to a deterministic convex compact 'limit shape' B determined by F. The time constant is the reciprocal of the speed in a given direction and is the support function of the limit shape.
FPP is honest mathematics with deep open problems. The time constant mu(F) is almost never known explicitly (even its positivity requires F(0) < p_c, since if open-with-probability F(0) edges already percolate, zero-cost paths exist and mu = 0). The limit shape B is provably convex and compact, but it is NOT known to be a Euclidean ball or even to have any curvature, in any dimension — whether it is ever a polygon is open. Most strikingly, the FLUCTUATIONS of T(0, n e_1) around its mean are conjectured to be of order n^(1/3) with Tracy-Widom limit law in 2D (the KPZ prediction), but rigorously only weak bounds (sublinear variance, Benjamini-Kalai-Schramm; n^(o(1)) at best in general) are known — the exact 1/3 exponent for genuine lattice FPP remains one of the major open problems. So FPP is a model where the answers are believed, simulated, and physically compelling, yet rigorously elusive.
Take Z^2 with passage times that are exponential(1) on each edge. Then T(0, n e_1)/n converges to a time constant mu in (0, infinity), and the wet region by time t looks, after dividing by t, like a fixed convex shape. Simulations show the front fluctuating with width of order t^(1/3) and one-point fluctuations matching the Tracy-Widom GUE law — the KPZ signature — even though proving this for lattice FPP is open.
FPP grows a deterministic limit shape; its front fluctuations are conjectured to be KPZ (order t^(1/3), Tracy-Widom).
The time constant exists by Kingman's subadditive ergodic theorem but is almost never explicit, and it is positive only when F(0) < p_c. The limit shape is provably convex/compact but NOT known to be a ball or to be curved; and the conjectured n^(1/3) KPZ fluctuations are unproven for lattice FPP.