×

Laplacian growth, sandpiles, and scaling limits. (English) Zbl 1451.37013

Summary: 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)\).

MSC:

37A50 Dynamical systems and their relations with probability theory and stochastic processes
37A60 Dynamical aspects of statistical mechanics
31C20 Discrete potential theory
35R02 PDEs on graphs and networks (ramified or polygonal spaces)
35R35 Free boundary problems for PDEs
60G50 Sums of independent random variables; random walks
60K35 Interacting random processes; statistical mechanics type models; percolation theory
82C24 Interface problems; diffusion-limited aggregation in time-dependent statistical mechanics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aharonov, Dov; Shapiro, Harold S., Domains on which analytic functions satisfy quadrature identities, J. Analyse Math., 30, 39-73 (1976) · Zbl 0337.30029 · doi:10.1007/BF02786704
[2] Asselah, Amine; Gaudilli\`ere, Alexandre, From logarithmic to subdiffusive polynomial fluctuations for internal DLA and related growth models, Ann. Probab., 41, 3A, 1115-1159 (2013) · Zbl 1283.60117 · doi:10.1214/12-AOP762
[3] Asselah, Amine; Gaudilli\`ere, Alexandre, Sublogarithmic fluctuations for internal DLA, Ann. Probab., 41, 3A, 1160-1179 (2013) · Zbl 1274.60286 · doi:10.1214/11-AOP735
[4] Asselah, Amine; Gaudilli\`ere, Alexandre, Lower bounds on fluctuations for internal DLA, Probab. Theory Related Fields, 158, 1-2, 39-53 (2014) · Zbl 1294.60115 · doi:10.1007/s00440-012-0476-6
[5] Athreya, Siva R.; J\'arai, Antal A., Infinite volume limit for the stationary distribution of abelian sandpile models, Comm. Math. Phys., 249, 1, 197-213 (2004) · Zbl 1085.82005 · doi:10.1007/s00220-004-1080-0
[6] Babai L\'aszl\'o Babai, Lecture notes on the sandpile model. http://people.cs.uchicago.edu/ laci/REU05/#problem · Zbl 0652.05043
[7] Bak, Per; Tang, Chao; Wiesenfeld, Kurt, Self-organized criticality, Phys. Rev. A (3), 38, 1, 364-374 (1988) · Zbl 1230.37103 · doi:10.1103/PhysRevA.38.364
[8] Baker, Matthew; Norine, Serguei, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math., 215, 2, 766-788 (2007) · Zbl 1124.05049 · doi:10.1016/j.aim.2007.04.012
[9] Benjamini, Itai; Lyons, Russell; Peres, Yuval; Schramm, Oded, Uniform spanning forests, Ann. Probab., 29, 1, 1-65 (2001) · Zbl 1016.60009 · doi:10.1214/aop/1008956321
[10] Bj\`“orner, Anders; Lov\'”asz, L\'aszl\'o; Shor, Peter W., Chip-firing games on graphs, European J. Combin., 12, 4, 283-291 (1991) · Zbl 0729.05048 · doi:10.1016/S0195-6698(13)80111-4
[11] Caffarelli, L. A., The obstacle problem revisited, J. Fourier Anal. Appl., 4, 4-5, 383-402 (1998) · Zbl 0928.49030 · doi:10.1007/BF02498216
[12] Cai15 Hannah Cairns, Some halting problems for abelian sandpiles are undecidable in dimension three. \hrefhttp://arxiv.org/abs/1508.00161arXiv:1508.00161 · Zbl 1403.68133
[13] Caracciolo, Sergio; Paoletti, Guglielmo; Sportiello, Andrea, Explicit characterization of the identity configuration in an abelian sandpile model, J. Phys. A, 41, 49, 495003, 17 pp. (2008) · Zbl 1161.82009 · doi:10.1088/1751-8113/41/49/495003
[14] Caracciolo, Sergio; Sportiello, Andrea, Exact integration of height probabilities in the abelian sandpile model, J. Stat. Mech. Theory Exp., 9, P09013, 14 pp. (2012) · Zbl 1456.82100
[15] Cooper, Joshua N.; Spencer, Joel, Simulating a random walk with constant error, Combin. Probab. Comput., 15, 6, 815-822 (2006) · Zbl 1113.60047 · doi:10.1017/S0963548306007565
[16] Dhar, Deepak, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett., 64, 14, 1613-1616 (1990) · Zbl 0943.82553 · doi:10.1103/PhysRevLett.64.1613
[17] Dhar, Deepak, Theoretical studies of self-organized criticality, Phys. A, 369, 1, 29-70 (2006) · doi:10.1016/j.physa.2006.04.004
[18] DSC Deepak Dhar, Tridib Sadhu and Samarth Chandra, Pattern formation in growing sandpiles, Europhys.Lett. 85 (2009), 48002. \hrefhttp://arxiv.org/abs/0808.1732arXiv:0808.1732
[19] DF91 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. · Zbl 0776.60128
[20] Fey, Anne; Meester, Ronald; Redig, Frank, Stabilizability and percolation in the infinite volume sandpile model, Ann. Probab., 37, 2, 654-675 (2009) · Zbl 1165.60033 · doi:10.1214/08-AOP415
[21] range Laura Florescu, Lionel Levine and Yuval Peres, The range of a rotor walk, 2014. \hrefhttp://arxiv.org/abs/1408.5533arXiv:1408.5533 · Zbl 1391.60019
[22] Fukai, Yasunari; Uchiyama, K\^ohei, Potential kernel for two-dimensional random walk, Ann. Probab., 24, 4, 1979-1992 (1996) · Zbl 0879.60068 · doi:10.1214/aop/1041903213
[23] Grimmett, Geoffrey, The random-cluster model, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 333, xiv+377 pp. (2006), Springer-Verlag, Berlin · Zbl 1122.60087 · doi:10.1007/978-3-540-32891-9
[24] Gustafsson, Bj\"orn, Quadrature identities and the Schottky double, Acta Appl. Math., 1, 3, 209-240 (1983) · Zbl 0559.30039 · doi:10.1007/BF00046600
[25] HLMPPW Alexander E. Holroyd, Lionel Levine, Karola M\'esz\'aros, 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\"auser, 2008. \hrefhttp://arxiv.org/abs/0801.3306arXiv:0801.3306 · Zbl 1173.82339
[26] Holroyd, Alexander E.; Propp, James, Rotor walks and Markov chains. Algorithmic probability and combinatorics, Contemp. Math. 520, 105-126 (2010), Amer. Math. Soc., Providence, RI · Zbl 1217.82042 · doi:10.1090/conm/520/10256
[27] Jar14 Antal A. J\'arai, Sandpile models, Cornell probability summer school lecture notes, 2014. \hrefhttp://arxiv.org/abs/1401.0354arXiv:1401.0354
[28] JPR06 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] Jerison, David; Levine, Lionel; Sheffield, Scott, Logarithmic fluctuations for internal DLA, J. Amer. Math. Soc., 25, 1, 271-301 (2012) · Zbl 1237.60037 · doi:10.1090/S0894-0347-2011-00716-9
[30] Jerison, David; Levine, Lionel; Sheffield, Scott, Internal DLA in higher dimensions, Electron. J. Probab., 18, No. 98, 14 pp. (2013) · Zbl 1290.60051 · doi:10.1214/EJP.v18-3137
[31] Jerison, David; Levine, Lionel; Sheffield, Scott, Internal DLA and the Gaussian free field, Duke Math. J., 163, 2, 267-308 (2014) · Zbl 1296.60113 · doi:10.1215/00127094-2430259
[32] Kassel, Adrien, Learning about critical phenomena from scribbles and sandpiles. Mod\'elisation Al\'eatoire et Statistique-Journ\'ees MAS 2014, ESAIM Proc. Surveys 51, 60-73 (2015), EDP Sci., Les Ulis · Zbl 1336.60190 · doi:10.1051/proc/201551004
[33] KW14 Adrien Kassel and David B. Wilson, Looping rate and sandpile density of planar graphs, 2014. \hrefhttp://arxiv.org/abs/1402.4169arXiv:1402.4169 · Zbl 1342.82035
[34] Kenyon, Richard, Spanning forests and the vector bundle Laplacian, Ann. Probab., 39, 5, 1983-2017 (2011) · Zbl 1252.82029 · doi:10.1214/10-AOP596
[35] Kenyon, Richard W.; Wilson, David B., Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs, J. Amer. Math. Soc., 28, 4, 985-1030 (2015) · Zbl 1327.60033 · doi:10.1090/S0894-0347-2014-00819-5
[36] Kozma, Gady; Schreiber, Ehud, An asymptotic expansion for the discrete harmonic potential, Electron. J. Probab., 9, no. 1, 1-17 (2004) · Zbl 1064.60166 · doi:10.1214/EJP.v9-170
[37] Lawler, Gregory F., A self-avoiding random walk, Duke Math. J., 47, 3, 655-693 (1980) · Zbl 0445.60058
[38] Lawler, Gregory F., Subdiffusive fluctuations for internal diffusion limited aggregation, Ann. Probab., 23, 1, 71-86 (1995) · Zbl 0835.60086
[39] Lawler, Gregory F., Intersections of random walks, Modern Birkh\`“auser Classics, iv+223 pp. (2013), Birkh\'”auser/Springer, New York · Zbl 1253.60003 · doi:10.1007/978-1-4614-5972-9
[40] Lawler, Gregory F.; Bramson, Maury; Griffeath, David, Internal diffusion limited aggregation, Ann. Probab., 20, 4, 2117-2140 (1992) · Zbl 0762.60096
[41] Levine, Lionel; Murugan, Mathav; Peres, Yuval; Ugurcan, Baris Evren, The divisible sandpile at critical density, Ann. Henri Poincar\'e, 17, 7, 1677-1711 (2016) · Zbl 1361.60094 · doi:10.1007/s00023-015-0433-x
[42] Levine, Lionel; Pegden, Wesley; Smart, Charles K., Apollonian structure in the Abelian sandpile, Geom. Funct. Anal., 26, 1, 306-336 (2016) · Zbl 1341.60129 · doi:10.1007/s00039-016-0358-7
[43] LPS2 Lionel Levine, Wesley Pegden and Charles K. Smart, The Apollonian structure of integer superharmonic matrices, 2013. \hrefhttp://arxiv.org/abs/1309.3267arXiv:1309.3267 · Zbl 1457.52018
[44] Levine, Lionel; Peres, Yuval, Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile, Potential Anal., 30, 1, 1-27 (2009) · Zbl 1165.82309 · doi:10.1007/s11118-008-9104-6
[45] Levine, Lionel; Peres, Yuval, Scaling limits for internal aggregation models with multiple sources, J. Anal. Math., 111, 151-219 (2010) · Zbl 1210.82031 · doi:10.1007/s11854-010-0015-2
[46] Levine, Lionel; Peres, Yuval, The looping constant of \(\mathbb{Z}^d\), Random Structures Algorithms, 45, 1, 1-13 (2014) · Zbl 1316.60067 · doi:10.1002/rsa.20478
[47] Lorenzini, Dino J., Arithmetical graphs, Math. Ann., 285, 3, 481-501 (1989) · Zbl 0662.14008 · doi:10.1007/BF01455069
[48] MD91 S. N. Majumdar and Deepak Dhar, Height correlations in the Abelian sandpile model, J. Phys. A: Math. Gen. 24 (1991), no. 7, L357.
[49] Manjunath, Madhusudan; Sturmfels, Bernd, Monomials, binomials and Riemann-Roch, J. Algebraic Combin., 37, 4, 737-756 (2013) · Zbl 1272.13017 · doi:10.1007/s10801-012-0386-9
[50] Mohammadi, Fatemeh; Shokrieh, Farbod, Divisors on graphs, connected flags, and syzygies, Int. Math. Res. Not. IMRN, 24, 6839-6905 (2014) · Zbl 1305.05132
[51] MD86 Paul Meakin and J. M. Deutch, The formation of surfaces by diffusion-limited annihilation, J. Chem.Phys. 85 (1986), 2320.
[52] Moore, Cristopher; Nilsson, Martin, The computational complexity of sandpiles, J. Statist. Phys., 96, 1-2, 205-224 (1999) · Zbl 0964.82037 · doi:10.1023/A:1004524500416
[53] Pemantle, Robin, Choosing a spanning tree for the integer lattice uniformly, Ann. Probab., 19, 4, 1559-1574 (1991) · Zbl 0758.60010
[54] Pegden, Wesley; Smart, Charles K., Convergence of the Abelian sandpile, Duke Math. J., 162, 4, 627-642 (2013) · Zbl 1283.60124 · doi:10.1215/00127094-2079677
[55] Pegden Wesley Pegden, Sandpile galleries. http://www.math.cmu.edu/ wes/sandgallery.html · Zbl 1283.60124
[56] Perkinson, David; Perlman, Jacob; Wilmes, John, Primer for the algebraic geometry of sandpiles. Tropical and non-Archimedean geometry, Contemp. Math. 605, 211-256 (2013), Amer. Math. Soc., Providence, RI · Zbl 1320.05060 · doi:10.1090/conm/605/12117
[57] Perkinson David Perkinson and Bryan Head, SandpilesApp. http://people.reed.edu/ davidp/sand/program/program.html
[58] PP11 V. S. Poghosyan and V. B. Priezzhev, The problem of predecessors on spanning trees, Acta Polytechnica, 51 (2011), 1, \hrefhttp://arxiv.org/abs/1010.5415arXiv:1010.5415
[59] PPS98 A. M. Povolotsky, V. B. Priezzhev, and R. R. Shcherbakov, Dynamics of Eulerian walkers, Physical Review E 58 (1998), no. 5, 5449.
[60] Pri94 V. B. Priezzhev, Structure of two dimensional sandpile. I. Height probabilities, J. Stat. Phys., 74 (1994), 955-979.
[61] PDDK96 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. \hrefhttp://arxiv.org/abs/cond-mat/9611019arXiv:cond-mat/9611019
[62] PPR11 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] propp James Propp, Random walk and random aggregation, derandomized, 2003.http://research.microsoft.com/apps/video/default.aspx?id=104906. · Zbl 1090.05003
[64] Sakai, Makoto, Quadrature domains, Lecture Notes in Mathematics 934, i+133 pp. (1982), Springer-Verlag, Berlin-New York · Zbl 0483.30001
[65] Sakai, Makoto, Solutions to the obstacle problem as Green potentials, J. Analyse Math., 44, 97-116 (1984/85) · Zbl 0577.49005 · doi:10.1007/BF02790192
[66] Spitzer, Frank, Principles of random walk, xiii+408 pp. (1976), Graduate Texts in Mathematics, Vol. 34, Springer-Verlag, New York-Heidelberg · Zbl 0979.60002
[67] Uchiyama, K\^ohei, Green’s functions for random walks on \({\bf Z}^N\), Proc. London Math. Soc. (3), 77, 1, 215-240 (1998) · Zbl 0893.60045 · doi:10.1112/S0024611598000458
[68] Wagner, Israel A.; Lindenbaum, Michael; Bruckstein, Alfred M., Smell as a computational resource-a lesson we can learn from the ant. Israel Symposium on Theory of Computing and Systems, Jerusalem, 1996, 219-230 (1996), IEEE Comput. Soc. Press, Los Alamitos, CA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.