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
DOI: https://doi.org/10.1090/S0002-9947-2011-05341-9
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 (2003a:49002)
  • 2. P. Assouad and T. Quentin de Gromard.
    Sur la dérivation des mesures dans $ \mathbb{R}^n$.
    1998.
    Unpublished note.
  • 3. Marcel Berger and Bernard Gostiaux.
    Géométrie différentielle.
    Librairie Armand Colin, Paris, 1972.
    Maîtrise de mathématiques, Collection U/Série ``Mathématiques''. MR 0494180 (58:13102)
  • 4. A. S. Besicovitch.
    A general form of the covering principle and relative differentiation of additive functions. II.
    Proc. Cambridge Philos. Soc., 42:1-10, 1946. MR 0014414 (7:281e)
  • 5. Béla Bollobás.
    Graph theory, volume 63 of Graduate Texts in Mathematics.
    Springer-Verlag, New York, 1979.
    An introductory course. MR 536131 (80j:05053)
  • 6. Raphaël Cerf.
    Large deviations for three dimensional supercritical percolation.
    Astérisque, (267):vi+177, 2000. MR 1774341 (2001j:60180)
  • 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 arxiv.org/abs/0907.5501, 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 arxiv.org/abs/0907.5499, 24 pages, 2009.
  • 9. Raphaël Cerf.
    The Wulff crystal in Ising and percolation models.
    In École d'Été de Probabilités de Saint Flour, number 1878 in Lecture Notes in Mathematics. Springer-Verlag, 2006. MR 2241754 (2008d:82032)
  • 10. E. De Giorgi, F. Colombini, and L. C. Piccinini.
    Frontiere orientate di misura minima e questioni collegate.
    Scuola Normale Superiore, Pisa, 1972. MR 0493669 (58:12647)
  • 11. Ennio De Giorgi.
    Nuovi teoremi relativi alle misure $ (r-1)$-dimensionali in uno spazio ad $ r$ dimensioni.
    Ricerche Mat., 4:95-113, 1955. MR 0074499 (17:596a)
  • 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 (93f:28001)
  • 13. K. J. Falconer.
    The geometry of fractal sets, volume 85 of Cambridge Tracts in Mathematics.
    Cambridge University Press, Cambridge, 1986. MR 867284 (88d:28001)
  • 14. Herbert Federer.
    Geometric measure theory.
    Die Grundlehren der mathematischen Wissenschaften, Band 153. Springer-Verlag, New York Inc., New York, 1969. MR 0257325 (41:1976)
  • 15. O. Garet.
    Capacitive flows on a $ 2d$ random net.
    Annals of Applied Probability, 19(2):641-660, 2009. MR 2521883 (2010f:60277)
  • 16. Enrico Giusti.
    Minimal surfaces and functions of bounded variation, volume 80 of Monographs in Mathematics.
    Birkhäuser Verlag, Basel, 1984. MR 775682 (87a:58041)
  • 17. Alfred Gray.
    Tubes, volume 221 of Progress in Mathematics.
    Birkhäuser Verlag, Basel, second edition, 2004.
    With a preface by Vicente Miquel. MR 2024928 (2004j:53001)
  • 18. Harry Kesten.
    Aspects of first passage percolation.
    In École d'Été de Probabilités de Saint Flour XIV, number 1180 in Lecture Notes in Mathematics. Springer-Verlag, 1984. MR 876084 (88h:60201)
  • 19. Harry Kesten.
    Surfaces with minimal random weights and maximal flows: A higher dimensional version of first-passage percolation.
    Illinois Journal of Mathematics, 31(1):99-166, 1987. MR 869483 (88i:60162)
  • 20. Serge Lang.
    Differential manifolds.
    Springer-Verlag, New York, second edition, 1985. MR 772023 (85m:58001)
  • 21. Umberto Massari and Mario Miranda.
    Minimal surfaces of codimension one, volume 91 of North-Holland Mathematics Studies.
    North-Holland Publishing Co., Amsterdam, 1984.
    Notas de Matemática [Mathematical Notes], 95. MR 795963 (87f:49058)
  • 22. Pertti Mattila.
    Geometry of sets and measures in Euclidean spaces, volume 44 of Cambridge Studies in Advanced Mathematics.
    Cambridge University Press, Cambridge, 1995.
    Fractals and rectifiability. MR 1333890 (96h:28006)
  • 23. T. Quentin de Gromard.
    Strong approximation of sets in $ BV(\Omega)$.
    Proceedings of the Royal Society of Edinburgh, 138(A):1291-1312, 2008. 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 Processes and their Applications, 120(6):873-900, 2010. 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 arxiv.org/abs/0907.0614, 14 pages, 2009.
  • 27. Yu Zhang.
    Critical behavior for maximal flows on the cubic lattice.
    Journal of Statistical Physics, 98(3-4):799-811, 2000. MR 1749233 (2000m:82018)
  • 28. Yu Zhang.
    Limit theorems for maximum flows on a lattice.
    Available from arxiv.org/ abs/0710.4589, 2007.
  • 29. William P. Ziemer.
    Weakly differentiable functions, volume 120 of Graduate Texts in Mathematics.
    Springer-Verlag, New York, 1989.
    Sobolev spaces and functions of bounded variation. MR 1014685 (91e:46046)

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
Email: rcerf@math.u-psud.fr

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
Email: marie.theret@ens.fr, marie.theret@univ-paris-diderot.fr

DOI: https://doi.org/10.1090/S0002-9947-2011-05341-9
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.

American Mathematical Society