MathDB

Higher-dimensional max-flow min-cut law for random networks

Let d≥2d\geq 2 and let mm be the common distribution of the independent edge capacities on the lattice Zd\mathbb{Z}^d. Write pc(Zd)p_c(\mathbb{Z}^d) for the bond-percolation threshold, let ∂∗A\partial^*A denote the reduced boundary of a convex set AA, let νA(x)\nu_A(x) be its exterior measure-theoretic unit normal, and let Hd−1\mathcal{H}^{d-1} be (d−1)(d-1)-dimensional Hausdorff measure. Assume

m(0)<1−pc(Zd)m(0)<1-p_c(\mathbb{Z}^d)

and, for some c>0c>0,

∫[0,∞)exp⁡(cx) dm(x)<+∞.\int_{[0,\infty)}\exp(cx)\,dm(x)<+\infty.

Higher-dimensional max-flow min-cut conjecture. There exists a map μ\mu on the unit sphere such that, for every convex set AA with 00 in its interior,

lim⁡n→+∞Mincut⁡(nA,∞)nd−1=∫∂∗Aμ(νA(x)) dHd−1(x).\lim_{n\to+\infty}\frac{\operatorname{Mincut}(nA,\infty)}{n^{d-1}}=\int_{\partial^*A}\mu(\nu_A(x))\,d\mathcal{H}^{d-1}(x).

The conjecture proposes that the normalized minimum capacity separating a dilated convex set from infinity has a deterministic anisotropic surface-energy limit in higher dimensions, extending the two-dimensional results discussed in the paper. The supplied text gives no resolution status or further conditions beyond those stated above.

Sources & referencesView supporting material

Primary source

Olivier Garet, “Capacitive flows on a 2D random net”, arXiv:math/0608676 (2009).

max-flow-min-cutpercolationrandom-networks

Progress summary

Refreshed
Solved

The conjectured law is now a theorem in every dimension covered by the problem’s assumptions.

Garet proposed the higher-dimensional extension in 2009; the two-dimensional case was already known. The assertion identifies a deterministic limiting surface energy for the minimum capacity separating a large convex region from infinity.

Known results

  • Dimension 22: the law was proved by Garet (year not specified in the retrieved source).

2018–2019 higher-dimensional proof

A paper proves the conjecture for d≥3d\geq 3 under the percolation and exponential-moment hypotheses, with convergence of Mincut⁡(nA,∞)/nd−1\operatorname{Mincut}(nA,\infty)/n^{d-1} to the stated anisotropic boundary integral. It also gives an exponential deviation estimate and establishes existence of a minimal cutset. The result appeared as a 2018 preprint and was published in 2019.

Current status (as of August 2026): the law is settled for d=2d=2 and d≥3d\geq 3 under the stated hypotheses, so no case in the stated range remains open.

Sources

Solutions 0

No solutions have been posted yet.