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?)

  • 1. 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
  • 2. P. Assouad and T. Quentin de Gromard.
    Sur la dérivation des mesures dans $ \mathbb{R}^n$.
    Unpublished note.
  • 3. 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
  • 4. 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,
  • 5. Béla Bollobás, Graph theory, Graduate Texts in Mathematics, vol. 63, Springer-Verlag, New York-Berlin, 1979. An introductory course. MR 536131
  • 6. Raphaël Cerf, Large deviations for three dimensional supercritical percolation, Astérisque 267 (2000), vi+177 (English, with English and French summaries). MR 1774341
  • 7. 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.
  • 8. 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.
  • 9. 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
  • 10. 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
  • 11. Ennio De Giorgi, Nuovi teoremi relativi alle misure (𝑟-1)-dimensionali in uno spazio ad 𝑟 dimensioni, Ricerche Mat. 4 (1955), 95–113 (Italian). MR 74499
  • 12. 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
  • 13. K. J. Falconer, The geometry of fractal sets, Cambridge Tracts in Mathematics, vol. 85, Cambridge University Press, Cambridge, 1986. MR 867284
  • 14. Herbert Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York Inc., New York, 1969. MR 0257325
  • 15. Olivier Garet, Capacitive flows on a 2D random set, Ann. Appl. Probab. 19 (2009), no. 2, 641–660. MR 2521883,
  • 16. Enrico Giusti, Minimal surfaces and functions of bounded variation, Monographs in Mathematics, vol. 80, Birkhäuser Verlag, Basel, 1984. MR 775682
  • 17. Alfred Gray, Tubes, 2nd ed., Progress in Mathematics, vol. 221, Birkhäuser Verlag, Basel, 2004. With a preface by Vicente Miquel. MR 2024928
  • 18. 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,
  • 19. 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
  • 20. Serge Lang, Differential manifolds, 2nd ed., Springer-Verlag, New York, 1985. MR 772023
  • 21. 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
  • 22. 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
  • 23. Thierry Quentin de Gromard, Strong approximation of sets in 𝐵𝑉(Ω), Proc. Roy. Soc. Edinburgh Sect. A 138 (2008), no. 6, 1291–1312. MR 2488060,
  • 24. 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,
  • 25. 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.
  • 26. Marie Théret.
    Upper large deviations for maximal flows through a tilted cylinder.
    Available from, 14 pages, 2009.
  • 27. Yu Zhang, Critical behavior for maximal flows on the cubic lattice, J. Statist. Phys. 98 (2000), no. 3-4, 799–811. MR 1749233,
  • 28. Yu Zhang.
    Limit theorems for maximum flows on a lattice.
    Available from abs/0710.4589, 2007.
  • 29. 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

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.