Maximal stream and minimal cutset for first passage percolation through a domain of \(\mathbb{R}^{d}\). (English) Zbl 1302.60132

Cerf, Raphaël; Théret, Marie

Ann. Probab. 42, No. 3, 1054-1120 (2014).

The authors consider a first passage percolation model in the rescaled graph \(\mathbb{Z}/n\) for \(d\geq 2\) and a domain \(\Omega\) of boundary \(\Gamma\) in \(\mathbb{R}^n\). Recall that a maximal stream is a vector measure \(\mu_n^{\text{max}}\) that describes how the maximal amount of fluid can cross \(\Omega\). The asymptotic behavior of a maximal stream and a minimal cutset are studied. Under some conditions it is proved that the sequence \(\left(\mu_n^{\text{max}}\right)_{n\geq 1}\) converges a.s.to the set of the solutions of a continuous deterministic problem of maximal stream in an anisotropic network. Let \(\Gamma^1\) and \(\Gamma^2\) be two disjoint open subsets of \(\Gamma\), representing the parts of \(\Gamma\) through which some water can enter and escape from \(\Omega\). A minimal cutset can be seen as the boundary of a set \(E_n^{\text{min}}\) that separates \(\Gamma^1\) from \(\Gamma^2\) in \(\Omega\) and whose random capacity is minimal. Under the same conditions, the authors prove that the sequence \(\left(E_n^{\text{min}}\right)_{n\geq 1}\) converges toward the set of the solutions of a continuous deterministic problem of minimal cutset. From this, a continuous deterministic max-flow min-cut theorem and a new proof of the law of large numbers for the maximal flow are obtained.

Reviewer: Utkir A. Rozikov (Tashkent)

MSC:

60K35	Interacting random processes; statistical mechanics type models; percolation theory
49K20	Optimality conditions for problems involving partial differential equations
35Q35	PDEs in connection with fluid mechanics
82B20	Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

Keywords:

first passage percolation; continuous and discrete max-flow min-cut theorem; maximal stream; maximal flow

References:

[1]	Blum, W. (1990). A measure-theoretical max-flow-min-cut problem. Math. Z. 205 451-470. · Zbl 0691.90023
[2]	Bogachev, V. I. (2007). Measure Theory. Vol. I , II . Springer, Berlin. · Zbl 1120.28001
[3]	Bollobás, B. (1979). Graph Theory : An Introductory Course. Graduate Texts in Mathematics 63 . Springer, New York. · Zbl 0411.05032
[4]	Cerf, R. (2006). The Wulff Crystal in Ising and Percolation Models. Lecture Notes in Math. 1878 . Springer, Berlin. · Zbl 1103.82010
[5]	Cerf, R. and Pisztora, Á. (2001). Phase coexistence in Ising, Potts and percolation models. Ann. Inst. Henri Poincaré Probab. Stat. 37 643-724. · Zbl 1006.60094
[6]	Cerf, R. and Théret, M. (2011). Law of large numbers for the maximal flow through a domain of \(\mathbb{R}^{d}\) in first passage percolation. Trans. Amer. Math. Soc. 363 3665-3702. · Zbl 1228.60107
[7]	Cerf, R. and Théret, M. (2011). Lower large deviations for the maximal flow through a domain of \(\mathbb{R}^{d}\) in first passage percolation. Probab. Theory Related Fields 150 635-661. · Zbl 1230.60101
[8]	Cerf, R. and Théret, M. (2011). Upper large deviations for the maximal flow through a domain of \(\mathbb{R}^{d}\) in first passage percolation. Ann. Appl. Probab. 21 2075-2108. · Zbl 1261.60089
[9]	Federer, H. (1969). Geometric Measure Theory . Springer, New York. · Zbl 0176.00801
[10]	Giusti, E. (1984). Minimal Surfaces and Functions of Bounded Variation. Monographs in Mathematics 80 . Birkhäuser, Basel. · Zbl 0545.49018
[11]	Guillemin, V. and Pollack, A. (1974). Differential Topology . Prentice-Hall, Englewood Cliffs, NJ. · Zbl 0361.57001
[12]	Kesten, H. (1986). Aspects of first passage percolation. In École D’été de Probabilités de Saint-Flour , XIV- 1984. Lecture Notes in Math. 1180 125-264. Springer, Berlin. · Zbl 0602.60098
[13]	Kesten, H. (1987). Surfaces with minimal random weights and maximal flows: A higher-dimensional version of first-passage percolation. Illinois J. Math. 31 99-166. · Zbl 0591.60096
[14]	Mattila, P. (1995). Geometry of Sets and Measures in Euclidean Spaces : Fractals and Rectifiability. Cambridge Studies in Advanced Mathematics 44 . Cambridge Univ. Press, Cambridge. · Zbl 0819.28004
[15]	Nozawa, R. (1990). Max-flow min-cut theorem in an anisotropic network. Osaka J. Math. 27 805-842. · Zbl 0723.90020
[16]	Rossignol, R. and Théret, M. (2010). Lower large deviations and laws of large numbers for maximal flows through a box in first passage percolation. Ann. Inst. Henri Poincaré Probab. Stat. 46 1093-1131. · Zbl 1221.60144
[17]	Rudin, W. (1987). Real and Complex Analysis , 3rd ed. McGraw-Hill, New York. · Zbl 0925.00005
[18]	Schwartz, L. (1950). Théorie des Distributions. Tome I . Hermann, Paris. · Zbl 0037.07301
[19]	Schwartz, L. (1951). Théorie des Distributions. Tome II . Hermann, Paris. · Zbl 0042.11405
[20]	Strang, G. (1983). Maximal flow through a domain. Math. Program. 26 123-143. · Zbl 0513.90026
[21]	Zhang, Y. (2000). Critical behavior for maximal flows on the cubic lattice. J. Stat. Phys. 98 799-811. · Zbl 0991.82019
[22]	Zhang, Y. (2007). Limit theorems for maximum flows on a lattice. Available at .