Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Law of large numbers for the maximal flow through a domain of $\mathbb {R}^d$ in first passage percolation

Authors: Raphaël Cerf and Marie Théret
Journal: Trans. Amer. Math. Soc. 363 (2011), 3665-3702
MSC (2010): Primary 60K35, 49Q20
Published electronically: February 25, 2011
MathSciNet review: 2775823
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We consider the standard first passage percolation model in the rescaled graph $\mathbb {Z}^d/n$ for $d\geq 2$, and a domain $\Omega$ of boundary $\Gamma$ in $\mathbb {R}^d$. 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$. We investigate the asymptotic behaviour of the flow $\phi _n$ through a discrete version $\Omega _n$ of $\Omega$ between the corresponding discrete sets $\Gamma ^1_n$ and $\Gamma ^2_n$. We prove that under some conditions on the regularity of the domain and on the law of the capacity of the edges, $\phi _n$ converges almost surely towards a constant $\phi _{\Omega }$, which is the solution of a continuous non-random min-cut problem. Moreover, we give a necessary and sufficient condition on the law of the capacity of the edges to ensure that $\phi _{\Omega } >0$.

References [Enhancements On Off] (What's this?)

  • Luigi Ambrosio, Nicola Fusco, and Diego Pallara, Functions of bounded variation and free discontinuity problems, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 2000. MR 1857292
  • P. Assouad and T. Quentin de Gromard. Sur la dérivation des mesures dans $\mathbb {R}^n$. 1998. Unpublished note.
  • Marcel Berger and Bernard Gostiaux, Géométrie différentielle, Librairie Armand Colin, Paris, 1972 (French). Maîtrise de mathématiques; Collection U/Série “Mathématiques”. MR 0494180
  • A. S. Besicovitch, A general form of the covering principle and relative differentiation of additive functions. II, Proc. Cambridge Philos. Soc. 42 (1946), 1–10. MR 14414, DOI
  • Béla Bollobás, Graph theory, Graduate Texts in Mathematics, vol. 63, Springer-Verlag, New York-Berlin, 1979. An introductory course. MR 536131
  • Raphaël Cerf, Large deviations for three dimensional supercritical percolation, Astérisque 267 (2000), vi+177 (English, with English and French summaries). MR 1774341
  • Raphaël Cerf and Marie Théret. Lower large deviations for the maximal flow through a domain of $\mathbb {R}^d$ in first passage percolation. To appear in Probability Theory and Related Fields, available from \, 23 pages, 2009.
  • Raphaël Cerf and Marie Théret. Upper large deviations for the maximal flow through a domain of $\mathbb {R}^d$ in first passage percolation. To appear in Annals of Applied Probability, available from \, 24 pages, 2009.
  • R. Cerf, The Wulff crystal in Ising and percolation models, Lecture Notes in Mathematics, vol. 1878, Springer-Verlag, Berlin, 2006. Lectures from the 34th Summer School on Probability Theory held in Saint-Flour, July 6–24, 2004; With a foreword by Jean Picard. MR 2241754
  • E. De Giorgi, F. Colombini, and L. C. Piccinini, Frontiere orientate di misura minima e questioni collegate, Scuola Normale Superiore, Pisa, 1972 (Italian). MR 0493669
  • Ennio De Giorgi, Nuovi teoremi relativi alle misure $(r-1)$-dimensionali in uno spazio ad $r$ dimensioni, Ricerche Mat. 4 (1955), 95–113 (Italian). MR 74499
  • Lawrence C. Evans and Ronald F. Gariepy, Measure theory and fine properties of functions, Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1992. MR 1158660
  • K. J. Falconer, The geometry of fractal sets, Cambridge Tracts in Mathematics, vol. 85, Cambridge University Press, Cambridge, 1986. MR 867284
  • Herbert Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York Inc., New York, 1969. MR 0257325
  • Olivier Garet, Capacitive flows on a 2D random set, Ann. Appl. Probab. 19 (2009), no. 2, 641–660. MR 2521883, DOI
  • Enrico Giusti, Minimal surfaces and functions of bounded variation, Monographs in Mathematics, vol. 80, Birkhäuser Verlag, Basel, 1984. MR 775682
  • Alfred Gray, Tubes, 2nd ed., Progress in Mathematics, vol. 221, Birkhäuser Verlag, Basel, 2004. With a preface by Vicente Miquel. MR 2024928
  • Harry Kesten, Aspects of first passage percolation, École d’été de probabilités de Saint-Flour, XIV—1984, Lecture Notes in Math., vol. 1180, Springer, Berlin, 1986, pp. 125–264. MR 876084, DOI
  • Harry Kesten, Surfaces with minimal random weights and maximal flows: a higher-dimensional version of first-passage percolation, Illinois J. Math. 31 (1987), no. 1, 99–166. MR 869483
  • Serge Lang, Differential manifolds, 2nd ed., Springer-Verlag, New York, 1985. MR 772023
  • Umberto Massari and Mario Miranda, Minimal surfaces of codimension one, North-Holland Mathematics Studies, vol. 91, North-Holland Publishing Co., Amsterdam, 1984. Notas de Matemática [Mathematical Notes], 95. MR 795963
  • Pertti Mattila, Geometry of sets and measures in Euclidean spaces, Cambridge Studies in Advanced Mathematics, vol. 44, Cambridge University Press, Cambridge, 1995. Fractals and rectifiability. MR 1333890
  • Thierry Quentin de Gromard, Strong approximation of sets in ${\rm BV}(\Omega )$, Proc. Roy. Soc. Edinburgh Sect. A 138 (2008), no. 6, 1291–1312. MR 2488060, DOI
  • Raphaël Rossignol and Marie Théret, Law of large numbers for the maximal flow through tilted cylinders in two-dimensional first passage percolation, Stochastic Process. Appl. 120 (2010), no. 6, 873–900. MR 2610330, DOI
  • Raphaël Rossignol and Marie Théret. Lower large deviations and laws of large numbers for maximal flows through a box in first passage percolation. Annales de l’Institut Henri Poincaré - Probabilités et Statistiques, 46(4):1093–1131, 2010.
  • Marie Théret. Upper large deviations for maximal flows through a tilted cylinder. Available from \, 14 pages, 2009.
  • Yu Zhang, Critical behavior for maximal flows on the cubic lattice, J. Statist. Phys. 98 (2000), no. 3-4, 799–811. MR 1749233, DOI
  • Yu Zhang. Limit theorems for maximum flows on a lattice. Available from \ \verb+abs/0710.4589+, 2007.
  • William P. Ziemer, Weakly differentiable functions, Graduate Texts in Mathematics, vol. 120, Springer-Verlag, New York, 1989. Sobolev spaces and functions of bounded variation. MR 1014685

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 60K35, 49Q20

Retrieve articles in all journals with MSC (2010): 60K35, 49Q20

Additional Information

Raphaël Cerf
Affiliation: Mathématique, Université Paris Sud, bâtiment 425, 91405 Orsay Cedex, France
MR Author ID: 349311

Marie Théret
Affiliation: DMA, École Normale Supérieure, 45 rue d’Ulm, 75230 Paris Cedex 05, France
Address at time of publication: LPMA, Université Paris Diderot Site Chevaleret, Case 7012, 75205 Paris Cedex 12 France

Keywords: First passage percolation, maximal flow, minimal cut, law of large numbers, polyhedral approximation.
Received by editor(s): November 5, 2009
Published electronically: February 25, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.