Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

   
 
 

 

Laplacian growth, sandpiles, and scaling limits


Authors: Lionel Levine and Yuval Peres
Journal: Bull. Amer. Math. Soc. 54 (2017), 355-382
MSC (2010): Primary 31C20, 35R35, 60G50, 60K35, 82C24
DOI: https://doi.org/10.1090/bull/1573
Published electronically: April 13, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Laplacian growth is the study of interfaces that move in proportion to harmonic measure. Physically, it arises in fluid flow and electrical problems involving a moving boundary. We survey progress over the last decade on discrete models of (internal) Laplacian growth, including the abelian sandpile, internal DLA, rotor aggregation, and the scaling limits of these models on the lattice $ \epsilon {\mathbb{Z}}^d$ as the mesh size $ \epsilon $ goes to zero. These models provide a window into the tools of discrete potential theory, including harmonic functions, martingales, obstacle problems, quadrature domains, Green functions, smoothing. We also present one new result: rotor aggregation in $ {\mathbb{Z}}^d$ has $ O(\log r)$ fluctuations around a Euclidean ball, improving a previous power-law bound. We highlight several open questions, including whether these fluctuations are $ O(1)$.


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

  • [1] Dov Aharonov and Harold S. Shapiro, Domains on which analytic functions satisfy quadrature identities, J. Analyse Math. 30 (1976), 39-73. MR 0447589, https://doi.org/10.1007/BF02786704
  • [2] Amine Asselah and Alexandre Gaudillière, From logarithmic to subdiffusive polynomial fluctuations for internal DLA and related growth models, Ann. Probab. 41 (2013), no. 3A, 1115-1159. MR 3098673, https://doi.org/10.1214/12-AOP762
  • [3] Amine Asselah and Alexandre Gaudillière, Sublogarithmic fluctuations for internal DLA, Ann. Probab. 41 (2013), no. 3A, 1160-1179. MR 3098674, https://doi.org/10.1214/11-AOP735
  • [4] Amine Asselah and Alexandre Gaudillière, Lower bounds on fluctuations for internal DLA, Probab. Theory Related Fields 158 (2014), no. 1-2, 39-53. MR 3152779, https://doi.org/10.1007/s00440-012-0476-6
  • [5] Siva R. Athreya and Antal A. Járai, Infinite volume limit for the stationary distribution of abelian sandpile models, Comm. Math. Phys. 249 (2004), no. 1, 197-213. MR 2077255, https://doi.org/10.1007/s00220-004-1080-0
  • [6] László Babai, Lecture notes on the sandpile model. http://people.cs.uchicago.edu/~laci/REU05/#problem
  • [7] Per Bak, Chao Tang, and Kurt Wiesenfeld, Self-organized criticality, Phys. Rev. A (3) 38 (1988), no. 1, 364-374. MR 949160, https://doi.org/10.1103/PhysRevA.38.364
  • [8] Matthew Baker and Serguei Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math. 215 (2007), no. 2, 766-788. MR 2355607, https://doi.org/10.1016/j.aim.2007.04.012
  • [9] Itai Benjamini, Russell Lyons, Yuval Peres, and Oded Schramm, Uniform spanning forests, Ann. Probab. 29 (2001), no. 1, 1-65. MR 1825141, https://doi.org/10.1214/aop/1008956321
  • [10] Anders Björner, László Lovász, and Peter W. Shor, Chip-firing games on graphs, European J. Combin. 12 (1991), no. 4, 283-291. MR 1120415, https://doi.org/10.1016/S0195-6698(13)80111-4
  • [11] L. A. Caffarelli, The obstacle problem revisited, J. Fourier Anal. Appl. 4 (1998), no. 4-5, 383-402. MR 1658612, https://doi.org/10.1007/BF02498216
  • [12] Hannah Cairns, Some halting problems for abelian sandpiles are undecidable in dimension three. arXiv:1508.00161
  • [13] Sergio Caracciolo, Guglielmo Paoletti, and Andrea Sportiello, Explicit characterization of the identity configuration in an abelian sandpile model, J. Phys. A 41 (2008), no. 49, 495003, 17. MR 2515893, https://doi.org/10.1088/1751-8113/41/49/495003
  • [14] Sergio Caracciolo and Andrea Sportiello, Exact integration of height probabilities in the abelian sandpile model, J. Stat. Mech. Theory Exp. 9 (2012), P09013, 14. MR 2994907
  • [15] Joshua N. Cooper and Joel Spencer, Simulating a random walk with constant error, Combin. Probab. Comput. 15 (2006), no. 6, 815-822. MR 2271828, https://doi.org/10.1017/S0963548306007565
  • [16] Deepak Dhar, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett. 64 (1990), no. 14, 1613-1616. MR 1044086, https://doi.org/10.1103/PhysRevLett.64.1613
  • [17] Deepak Dhar, Theoretical studies of self-organized criticality, Phys. A 369 (2006), no. 1, 29-70. MR 2246566, https://doi.org/10.1016/j.physa.2006.04.004
  • [18] Deepak Dhar, Tridib Sadhu and Samarth Chandra, Pattern formation in growing sandpiles, Europhys. Lett. 85 (2009), 48002. arXiv:0808.1732
  • [19] Persi Diaconis and William Fulton, A growth model, a game, an algebra, Lagrange inversion, and characteristic classes, Rend. Sem. Mat. Univ. Pol. Torino 49 (1991), no. 1, 95-119.
  • [20] Anne Fey, Ronald Meester, and Frank Redig, Stabilizability and percolation in the infinite volume sandpile model, Ann. Probab. 37 (2009), no. 2, 654-675. MR 2510019, https://doi.org/10.1214/08-AOP415
  • [21] Laura Florescu, Lionel Levine and Yuval Peres, The range of a rotor walk, 2014. arXiv:1408.5533
  • [22] Yasunari Fukai and Kôhei Uchiyama, Potential kernel for two-dimensional random walk, Ann. Probab. 24 (1996), no. 4, 1979-1992. MR 1415236, https://doi.org/10.1214/aop/1041903213
  • [23] Geoffrey Grimmett, The random-cluster model, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 333, Springer-Verlag, Berlin, 2006. MR 2243761
  • [24] Björn Gustafsson, Quadrature identities and the Schottky double, Acta Appl. Math. 1 (1983), no. 3, 209-240. MR 726725, https://doi.org/10.1007/BF00046600
  • [25] Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp and David B. Wilson, Chip-firing and rotor-routing on directed graphs, In and out of equilibrium $ 2$, 331-364, Progr. Probab. 60, Birkhäuser, 2008. arXiv:0801.3306
  • [26] Alexander E. Holroyd and James Propp, Rotor walks and Markov chains, Algorithmic probability and combinatorics, Contemp. Math., vol. 520, Amer. Math. Soc., Providence, RI, 2010, pp. 105-126. MR 2681857, https://doi.org/10.1090/conm/520/10256
  • [27] Antal A. Járai, Sandpile models, Cornell probability summer school lecture notes, 2014. arXiv:1401.0354
  • [28] Monwhea Jeng, Geoqffroy Piroux and Philippe Ruelle, Height variables in the Abelian sandpile model: scaling fields and correlations, J. Stat. Mech. 61 (2006), 15.
  • [29] David Jerison, Lionel Levine, and Scott Sheffield, Logarithmic fluctuations for internal DLA, J. Amer. Math. Soc. 25 (2012), no. 1, 271-301. MR 2833484, https://doi.org/10.1090/S0894-0347-2011-00716-9
  • [30] David Jerison, Lionel Levine, and Scott Sheffield, Internal DLA in higher dimensions, Electron. J. Probab. 18 (2013), No. 98, 14. MR 3141799, https://doi.org/10.1214/EJP.v18-3137
  • [31] David Jerison, Lionel Levine, and Scott Sheffield, Internal DLA and the Gaussian free field, Duke Math. J. 163 (2014), no. 2, 267-308. MR 3161315, https://doi.org/10.1215/00127094-2430259
  • [32] Adrien Kassel, Learning about critical phenomena from scribbles and sandpiles, Modélisation Aléatoire et Statistique--Journées MAS 2014, ESAIM Proc. Surveys, vol. 51, EDP Sci., Les Ulis, 2015, pp. 60-73 (English, with English and French summaries). MR 3440791, https://doi.org/10.1051/proc/201551004
  • [33] Adrien Kassel and David B. Wilson, Looping rate and sandpile density of planar graphs, 2014. arXiv:1402.4169
  • [34] Richard Kenyon, Spanning forests and the vector bundle Laplacian, Ann. Probab. 39 (2011), no. 5, 1983-2017. MR 2884879, https://doi.org/10.1214/10-AOP596
  • [35] Richard W. Kenyon and David B. Wilson, Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs, J. Amer. Math. Soc. 28 (2015), no. 4, 985-1030. MR 3369907, https://doi.org/10.1090/S0894-0347-2014-00819-5
  • [36] Gady Kozma and Ehud Schreiber, An asymptotic expansion for the discrete harmonic potential, Electron. J. Probab. 9 (2004), no. 1, 1-17. MR 2041826, https://doi.org/10.1214/EJP.v9-170
  • [37] Gregory F. Lawler, A self-avoiding random walk, Duke Math. J. 47 (1980), no. 3, 655-693. MR 587173
  • [38] Gregory F. Lawler, Subdiffusive fluctuations for internal diffusion limited aggregation, Ann. Probab. 23 (1995), no. 1, 71-86. MR 1330761
  • [39] Gregory F. Lawler, Intersections of random walks, Modern Birkhäuser Classics, Birkhäuser/Springer, New York, 2013. Reprint of the 1996 edition. MR 2985195
  • [40] Gregory F. Lawler, Maury Bramson, and David Griffeath, Internal diffusion limited aggregation, Ann. Probab. 20 (1992), no. 4, 2117-2140. MR 1188055
  • [41] Lionel Levine, Mathav Murugan, Yuval Peres, and Baris Evren Ugurcan, The divisible sandpile at critical density, Ann. Henri Poincaré 17 (2016), no. 7, 1677-1711. MR 3510467, https://doi.org/10.1007/s00023-015-0433-x
  • [42] Lionel Levine, Wesley Pegden, and Charles K. Smart, Apollonian structure in the Abelian sandpile, Geom. Funct. Anal. 26 (2016), no. 1, 306-336. MR 3494492, https://doi.org/10.1007/s00039-016-0358-7
  • [43] Lionel Levine, Wesley Pegden and Charles K. Smart, The Apollonian structure of integer superharmonic matrices, 2013. arXiv:1309.3267
  • [44] Lionel Levine and Yuval Peres, Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile, Potential Anal. 30 (2009), no. 1, 1-27. MR 2465710, https://doi.org/10.1007/s11118-008-9104-6
  • [45] Lionel Levine and Yuval Peres, Scaling limits for internal aggregation models with multiple sources, J. Anal. Math. 111 (2010), 151-219. MR 2747064, https://doi.org/10.1007/s11854-010-0015-2
  • [46] Lionel Levine and Yuval Peres, The looping constant of $ \mathbb{Z}^d$, Random Structures Algorithms 45 (2014), no. 1, 1-13. MR 3231081, https://doi.org/10.1002/rsa.20478
  • [47] Dino J. Lorenzini, Arithmetical graphs, Math. Ann. 285 (1989), no. 3, 481-501. MR 1019714, https://doi.org/10.1007/BF01455069
  • [48] S. N. Majumdar and Deepak Dhar, Height correlations in the Abelian sandpile model, J. Phys. A: Math. Gen. 24 (1991), no. 7, L357.
  • [49] Madhusudan Manjunath and Bernd Sturmfels, Monomials, binomials and Riemann-Roch, J. Algebraic Combin. 37 (2013), no. 4, 737-756. MR 3047017, https://doi.org/10.1007/s10801-012-0386-9
  • [50] Fatemeh Mohammadi and Farbod Shokrieh, Divisors on graphs, connected flags, and syzygies, Int. Math. Res. Not. IMRN 24 (2014), 6839-6905. MR 3291642
  • [51] Paul Meakin and J. M. Deutch, The formation of surfaces by diffusion-limited annihilation, J. Chem. Phys. 85 (1986), 2320.
  • [52] Cristopher Moore and Martin Nilsson, The computational complexity of sandpiles, J. Statist. Phys. 96 (1999), no. 1-2, 205-224. MR 1706761, https://doi.org/10.1023/A:1004524500416
  • [53] Robin Pemantle, Choosing a spanning tree for the integer lattice uniformly, Ann. Probab. 19 (1991), no. 4, 1559-1574. MR 1127715
  • [54] Wesley Pegden and Charles K. Smart, Convergence of the Abelian sandpile, Duke Math. J. 162 (2013), no. 4, 627-642. MR 3039676, https://doi.org/10.1215/00127094-2079677
  • [55] Wesley Pegden, Sandpile galleries. http://www.math.cmu.edu/~wes/sandgallery.html
  • [56] David Perkinson, Jacob Perlman, and John Wilmes, Primer for the algebraic geometry of sandpiles, Tropical and non-Archimedean geometry, Contemp. Math., vol. 605, Amer. Math. Soc., Providence, RI, 2013, pp. 211-256. MR 3204273, https://doi.org/10.1090/conm/605/12117
  • [57] David Perkinson and Bryan Head, SandpilesApp. http://people.reed.edu/~davidp/sand/program/program.html
  • [58] V. S. Poghosyan and V. B. Priezzhev, The problem of predecessors on spanning trees, Acta Polytechnica, 51 (2011), 1, arXiv:1010.5415
  • [59] A. M. Povolotsky, V. B. Priezzhev, and R. R. Shcherbakov, Dynamics of Eulerian walkers, Physical Review E 58 (1998), no. 5, 5449.
  • [60] V. B. Priezzhev, Structure of two dimensional sandpile. I. Height probabilities, J. Stat. Phys., 74 (1994), 955-979.
  • [61] V. B. Priezzhev, Deepak Dhar, Abhishek Dhar and Supriya Krishnamurthy, Eulerian walkers as a model of self-organised criticality, Phys. Rev. Lett. 77 (1996), 5079-5082. arXiv:cond-mat/9611019
  • [62] V. S. Poghosyan, V. B. Priezzhev and P. Ruelle, Return probability for the loop-erased random walk and mean height in the Abelian sandpile model: a proof. Journal of Statistical Mechanics: Theory and Experiment 10 (2011), P10004.
  • [63] James Propp, Random walk and random aggregation, derandomized, 2003. http://research.microsoft.com/apps/video/default.aspx?id=104906.
  • [64] Makoto Sakai, Quadrature domains, Lecture Notes in Mathematics, vol. 934, Springer-Verlag, Berlin-New York, 1982. MR 663007
  • [65] Makoto Sakai, Solutions to the obstacle problem as Green potentials, J. Analyse Math. 44 (1984/85), 97-116. MR 801289, https://doi.org/10.1007/BF02790192
  • [66] Frank Spitzer, Principles of random walk, 2nd ed., Graduate Texts in Mathematics, Vol. 34, Springer-Verlag, New York-Heidelberg, 1976. MR 0388547
  • [67] Kôhei Uchiyama, Green's functions for random walks on $ {\bf Z}^N$, Proc. London Math. Soc. (3) 77 (1998), no. 1, 215-240. MR 1625467, https://doi.org/10.1112/S0024611598000458
  • [68] Israel A. Wagner, Michael Lindenbaum, and Alfred M. Bruckstein, Smell as a computational resource--a lesson we can learn from the ant, Israel Symposium on Theory of Computing and Systems (Jerusalem, 1996) IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 219-230. MR 1436463

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2010): 31C20, 35R35, 60G50, 60K35, 82C24

Retrieve articles in all journals with MSC (2010): 31C20, 35R35, 60G50, 60K35, 82C24


Additional Information

Lionel Levine
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853

Yuval Peres
Affiliation: Microsoft Research, Redmond, Washington 98052

DOI: https://doi.org/10.1090/bull/1573
Keywords: Abelian sandpile, chip-firing, discrete Laplacian, divisible sandpile, Eulerian walkers, internal diffusion limited aggregation, looping constant, obstacle problem, rotor-router model, scaling limit, unicycle, Tutte slope
Received by editor(s): September 23, 2016
Published electronically: April 13, 2017
Additional Notes: The first author was supported by NSF grant \href{http://www.nsf.gov/awardsearch/showAward?AWD_{I}D=1455272}DMS-1455272 and a Sloan Fellowship.
Article copyright: © Copyright 2017 by Lionel Levine and Yuval Peres

American Mathematical Society