A discrete Hammersley process as an extreme case of oriented percolation flows

Consider the finite square lattice $ \{0,1, \ldots, n-1\} \times \{0,1, \ldots, n-1\} $ and $0 < p < 1$ and the usual oriented percolation model: edges are independently open with probability $ p $ or else closed, and a path consists of edges oriented either up or right. Standard theory includes existence of a critical value $p_*$ such that, in the infinite lattice, infinite open paths exist for $ p > p_* $ but not for $ p < p_* $.

We consider flows, as follows. Imagine open edges have capacity $1 $ and closed edges have capacity $ 0 $. Imagine sources at each vertex on the left and bottom sides of the square; what volume of flow can be transported to the top and right sides? In other words, we consider the random variable

$V(n,p) := $ maximum number of edge-disjoint open paths starting from some vertex in $ \{ (0,0), (0,1), \ldots (0,n-2), (1,0), (2,0), \ldots (n-2,0) \} $ and ending at some vertex in $ \{ (0,n-1), (1, n-1), \ldots , (n-1,n-1), (n-1, n-2),\ldots (n-1,0) \} $

Straightforward arguments show that there is a deterministic limit function $v(p)$ such that $$ \frac{V(n,p)}{2n} \to v(p) \mbox{ in } L^1 \mbox{ as } n \to \infty $$ and that $$ v(p) = 0, \ p < p_*; \quad v(p) > 0, \ p > p_*; \quad v(p) \to 1 \mbox{ as } p \to 1 . $$ Studying scaling properties as $ p \downarrow p_* $ would be a classical style of hard statistical physics project. Instead we consider $ p \uparrow 1$ behavior. By considering complements we see that (up to negligible terms) $$ 1 - v(p) = \lim_n \frac{U(n,p)}{2n} $$ where

$U(n,p) := $ minimum number of edge-disjoint paths, starting and ending as above, which cover all the closed edges.

We now start heuristic arguments. For $ p $ near $ 1 $, the closed edges are approximately a Poisson point process of rate $ 2(1-p) $ per unit area in the continuum square $ [0,n]^2 $ and so $U(n,p) $ should be approximately $ U^*(n, \delta) $, the minimum number of oriented paths in the continuum square $ [0,n]^2 $ needed to cover all the points of a Poisson (rate $ \delta = 2(1-p) $) process in the square. By scaling $ U^*(n, \delta) $ has the same distribution as $ U^*(\delta^{-1/2}n, 1) $ and by the theory surrounding the Hammersley process (see e.g. Figure 3 of Aldous-Diaconis (1995); I'm not sure if this is written explicitly anywhere) $$ U^*(m,1) = (1 + o(1)) m \mbox{ as } m \to \infty . $$ Putting this all together leads to

Conjecture. $$ 1 - v(p) \sim \sqrt{2(1-p)} \mbox{ as } p \uparrow 1 $$

Thinking more carefully, the heuristic argument above involves an "interchange of limits" which seems rather difficult to justify.

History. The conjecture was formulated in work with Jason Lenderman in 2004 but we were unable to prove it. Simulations by Jason support the conjecture.

Back to Open Problem list