Internal aggregation models on comb lattices

Wilfried Huss (Vienna University of Technology)
Ecaterina Sava (Graz University of Technology)


The two-dimensional comb lattice $\mathcal{C}_2$ is a natural spanning tree of the Euclidean lattice  $\mathbb{Z}^2$. We study three related cluster growth models on $\mathcal{C}_2$: internal diffusion limited aggregation (IDLA), in which random walkers move on the vertices of $\mathcal{C}_2$ until reaching an unoccupied  site where they stop; rotor-router aggregation in which particles perform deterministic walks, and stop when reaching a site previously unoccupied; and the divisible sandpile model where at  each vertex there is a pile of sand, for which, at each step, the mass exceeding $1$ is distributed equally among the neighbours. We describe the shape of the divisible sandpile cluster on $\mathcal{C}_2$,  which is then used to give inner bounds for IDLA and rotor-router aggregation.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-21

Publication Date: April 12, 2012

DOI: 10.1214/EJP.v17-1940


  • N. Alon and J. H Spencer. The probabilistic method. With an appendix by Paul Erdős. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1992. xvi+254 pp. ISBN: 0-471-53588-5 MR1140703
  • A. Asselah and A. Gaudillière. A note on fluctuations for internal diffusion limited aggregation, ARXIV1004.4665, (2010).
  • A. Asselah and A. Gaudilliere. From logarithmic to subdiffusive polynomial fluctuations for internal DLA and related growth models, ARXIV1009.2838, (2011).
  • A. Asselah and A. Gaudilliere. Sub-logarithmic fluctuations for internal DLA, ARXIV1011.4592, (2011).
  • D. Bertacchi. Asymptotic behaviour of the simple random walk on the 2-dimensional comb. Electron. J. Probab. 11 (2006), no. 45, 1184--1203 (electronic). MR2268542
  • D. Bertacchi and F. Zucca. Uniform asymptotic estimates of transition probabilities on combs. J. Aust. Math. Soc. 75 (2003), no. 3, 325--353. MR2015321
  • P. Diaconis and W. Fulton. A growth model, a game, an algebra, Lagrange inversion, and characteristic classes. Commutative algebra and algebraic geometry, II (Italian) (Turin, 1990). Rend. Sem. Mat. Univ. Politec. Torino 49 (1991), no. 1, 95--119 (1993). MR1218674
  • H. Duminil-Copin, C. Lucas, A. Yadin, and A. Yehudayoff. Containing Internal Diffusion Limited Aggregation, ARXIV1111.0486, (2011).
  • P. Gerl. Natural spanning trees of ${\bf Z}^ d$ are recurrent. Discrete Math. 61 (1986), no. 2-3, 333--336. MR0855341
  • A. E. Holroyd and J. Propp. Rotor walks and Markov chains. Algorithmic probability and combinatorics, 105--126, Contemp. Math., 520, Amer. Math. Soc., Providence, RI, 2010. MR2681857
  • W. Huss and E. Sava, Rotor-Router Aggregation on the Comb, Electron. J. Combin. 18 (2011), P224.
  • D. Jerison, L. Levine, and S. Sheffield, Internal DLA in higher dimensions, ARXIV1012.3453, (2011).
  • D. Jerison, L. Levine and S. Sheffield, Logarithmic fluctuations for internal DLA. J. Amer. Math. Soc. 25 (2012), no. 1, 271--301. MR2833484
  • W. Kager and L. Levine. Rotor-router aggregation on the layered square lattice. Electron. J. Combin. 17 (2010), P 152, 16 pp. MR2745705
  • M. Krishnapur and Y.Peres. Recurrent graphs where two independent random walks collide finitely often. Electron. Comm. Probab. 9 (2004), 72--81 (electronic). MR2081461
  • I. Landau and L. Levine. The rotor-router model on regular trees. J. Combin. Theory Ser. A 116 (2009), no. 2, 421--433. MR2475025
  • G. Lawler. Intersections of random walks. Probability and its Applications. Birkhäuser Boston, Inc., Boston, MA, 1991. 219 pp. ISBN: 0-8176-3557-2 MR1117680
  • G. Lawler. Subdiffusive fluctuations for internal diffusion limited aggregation. Ann. Probab. 23 (1995), no. 1, 71--86. MR1330761
  • G. Lawler, M. Bramson and D. Griffeath. Internal diffusion limited aggregation. Ann. Probab. 20 (1992), no. 4, 2117--2140. MR1188055
  • L. Levine and Y. Peres. Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile. Potential Anal. 30 (2009), no. 1, 1--27. MR2465710
  • L. Levine and Y. Peres. Scaling limits for internal aggregation models with multiple sources. J. Anal. Math. 111 (2010), 151--219. MR2747064
  • R. Lyons and Y. Peres. Probabilty on trees and networks, preprint.
  • V. B. Priezzhev, D. Dhar, A. Dhar, and Supriya Krishnamurthy. Eulerian walkers as a model of self-organized criticality, Phys. Rev. Lett. 77 (1996), no. 25, 5079--5082.
  • G. H. Weiss and Shlomo Havlin. Some properties of a random walk on a comb structure, Physica A: Statistical and Theoretical Physics 134 (1986), no. 2, 474--482.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.