|
Law of large numbers for the maximal flow through a domain of 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
Posted:
February 25, 2011
MathSciNet review:
2775823
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We consider the standard first passage percolation model in the rescaled graph for , and a domain of boundary in . Let and be two disjoint open subsets of , representing the parts of through which some water can enter and escape from . We investigate the asymptotic behaviour of the flow through a discrete version of between the corresponding discrete sets and . We prove that under some conditions on the regularity of the domain and on the law of the capacity of the edges, converges almost surely towards a constant , 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 .
- 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 . 1998. Unpublished note.
- 3.
Marcel
Berger and Bernard
Gostiaux, Géométrie différentielle,
Librairie Armand Colin, Paris, 1972 (French). Ma\cflexı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 (1946), 1–10. MR 0014414
(7,281e)
- 5.
Béla
Bollobás, Graph theory, Graduate Texts in Mathematics,
vol. 63, 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 (2000), vi+177
(English, with English and French summaries). MR 1774341
(2001j:60180)
- 7.
Raphaël Cerf and Marie Théret.
Lower large deviations for the maximal flow through a domain of 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 in first passage percolation. To appear in Annals of Applied Probability, available from arxiv.org/abs/0907.5499, 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
(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 (Italian). MR 0493669
(58 #12647)
- 11.
Ennio
De Giorgi, Nuovi teoremi relativi alle misure
(𝑟-1)-dimensionali in uno spazio ad 𝑟 dimensioni,
Ricerche Mat. 4 (1955), 95–113 (Italian). 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, Cambridge Tracts in
Mathematics, vol. 85, 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.
Olivier
Garet, Capacitive flows on a 2D random set, Ann. Appl. Probab.
19 (2009), no. 2, 641–660. MR 2521883
(2010f:60277), http://dx.doi.org/10.1214/08-AAP556
- 16.
Enrico
Giusti, Minimal surfaces and functions of bounded variation,
Monographs in Mathematics, vol. 80, Birkhäuser Verlag, Basel,
1984. MR
775682 (87a:58041)
- 17.
Alfred
Gray, Tubes, 2nd ed., Progress in Mathematics, vol. 221,
Birkhäuser Verlag, Basel, 2004. With a preface by Vicente Miquel. MR 2024928
(2004j:53001)
- 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
(88h:60201), http://dx.doi.org/10.1007/BFb0074919
- 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
(88i:60162)
- 20.
Serge
Lang, Differential manifolds, 2nd ed., Springer-Verlag, New
York, 1985. MR
772023 (85m:58001)
- 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
(87f:49058)
- 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
(96h:28006)
- 23.
Thierry
Quentin de Gromard, Strong approximation of sets in
𝐵𝑉(Ω), Proc. Roy. Soc. Edinburgh Sect. A
138 (2008), no. 6, 1291–1312. MR 2488060
(2010i:49022), http://dx.doi.org/10.1017/S0308210507000492
- 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
(2011e:60229), http://dx.doi.org/10.1016/j.spa.2010.02.005
- 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, J. Statist. Phys. 98 (2000), no. 3-4,
799–811. MR 1749233
(2000m:82018), http://dx.doi.org/10.1023/A:1018631726709
- 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, Graduate Texts in
Mathematics, vol. 120, Springer-Verlag, New York, 1989. Sobolev spaces
and functions of bounded variation. MR 1014685
(91e:46046)
- 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 . 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 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 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 -dimensionali in uno spazio ad 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 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 . 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:
http://dx.doi.org/10.1090/S0002-9947-2011-05341-9
PII:
S 0002-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
Posted:
February 25, 2011
Article copyright:
© Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
|