Maximal flow through oriented percolation as p tends to 1

In an $n \times n$ grid where each edge is open with probability $p$, how many edge-disjoint up-right open paths can cross from the bottom and left sides to the top and right sides? As $p \to 1$ almost all of the $2n$ possible paths survive, and a heuristic based on Hammersley's process predicts exactly how fast the deficit vanishes: like $\sqrt{2(1-p)}$. Simulations agree, but no proof is known.

Problem

Consider the grid $\{0, 1, \dots, n-1\}^2$ with edges between nearest neighbours. Each edge is independently open with probability $p \in (0, 1)$ and closed otherwise; paths may only move up or right. Let $V(n, p)$ be the maximum number of edge-disjoint open paths, each starting at a vertex on the left or bottom side of the square and ending at a vertex on the top or right side. Equivalently, $V(n,p)$ is the maximum flow when open edges have capacity 1 and closed edges capacity 0.

There is a deterministic function $v(p)$ with $V(n, p)/(2n) \to v(p)$ in $L^1$ as $n \to \infty$, and $v(p) \to 1$ as $p \to 1$.

Conjecture (Aldous and Lenderman). As $p \uparrow 1$,

$$1 - v(p) \sim \sqrt{2(1 - p)}.$$

Background

By duality, $1 - v(p)$ is, up to negligible terms, the limit of $U(n, p)/(2n)$, where $U(n, p)$ is the minimum number of edge-disjoint up-right paths needed to cover all closed edges. When $p$ is close to 1 the closed edges look like a Poisson process of rate $2(1 - p)$ per unit area, and covering points of a Poisson process by up-right paths is governed by Hammersley's interacting particle process, the same object that describes longest increasing subsequences of random permutations. Combining these heuristics gives the conjecture; the difficulty is to justify the interchange of the limits $n \to \infty$ and $p \to 1$. Aldous calls the model a discrete Hammersley process seen as an extreme case of oriented percolation flows.

What is known

• The limit $v(p)$ exists, is $0$ below the critical value $p_*$ of oriented percolation, is positive above it, and tends to 1 as $p \to 1$ (stated by Aldous as following from straightforward arguments).
• The conjecture was formulated by Aldous and Jason Lenderman in 2004; they could not prove it, and Lenderman's simulations support it.
• The behaviour of $v(p)$ as $p \downarrow p_*$ is a separate, harder question in the style of statistical physics, which Aldous deliberately sets aside.

What would count as progress

• A proof of the conjecture, or at least bounds $c_1\sqrt{1-p} \le 1 - v(p) \le c_2\sqrt{1-p}$ for $p$ near 1.
• A rigorous analysis of the continuum covering problem: the minimum number of up-right paths, entering through the left and bottom sides and leaving through the top and right sides of a large square, needed to cover a Poisson point process.
• New simulations: $V(n, p)$ is a maximum-flow problem computable in polynomial time, so the ratio $(1 - V(n,p)/(2n))/\sqrt{2(1-p)}$ can be estimated for large $n$ and $p$ close to 1, with attention to the order of limits.

References

1. D. Aldous and P. Diaconis, Hammersley's interacting particle process and longest increasing subsequences, Probab. Theory Related Fields 103 (1995), 199–213.
2. R. Durrett, Oriented percolation in two dimensions, Ann. Probab. 12 (1984), 999–1040.

Source

Imported from David Aldous's open problems hammersley_flow, curated by David Aldous. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.