# 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](https://doi.org/10.1007/BF01204214), Probab. Theory Related Fields **103** (1995), 199–213.
2. R. Durrett, [Oriented percolation in two dimensions](https://doi.org/10.1214/aop/1176993140), Ann. Probab. **12** (1984), 999–1040.

## Source

Imported from [David Aldous's open problems hammersley_flow](https://www.stat.berkeley.edu/~aldous/Research/OP/hammersley_flow.html), 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.