Diffusion limited aggregation in the layers model

Alan Frieze; Colin Cooper

arxiv: 2312.12326 · v3 · submitted 2023-12-19 · 🧮 math.PR · math.CO

Diffusion limited aggregation in the layers model

Colin Cooper , Alan Frieze This is my paper

Pith reviewed 2026-05-24 04:47 UTC · model grok-4.3

classification 🧮 math.PR math.CO

keywords diffusion limited aggregationrandom walks on graphsCayley treeslayered graphscluster growthsource-sink modelfinish time

0 comments

The pith

On layered graphs like Cayley trees the DLA process finishes after a number of steps fixed by the structure and the final cluster connects source to sink by an essentially unique path.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies a graph version of diffusion limited aggregation in which particles begin at a source vertex and perform random walks toward a sink, halting at the last unoccupied vertex before hitting the growing cluster. On regular layered graphs such as Cayley trees of branching factor at least two, the authors obtain an exact expression for the number of particles required until the source is occupied. They further prove that the portion of the final cluster that links source to sink consists of essentially one path. A reader would care because the result converts a stochastic aggregation process into a deterministic outcome whose size and shape are fixed by the graph layers alone.

Core claim

The authors determine the finish time of the DLA process on Cayley trees of branching factor at least two with a sink vertex attached to the leaves, and show that the subcomponent of the final cluster linking source to sink is essentially a unique path.

What carries the argument

The attachment rule in which each particle halts at the last unoccupied vertex before its random walk first enters the existing cluster.

If this is right

The finish time equals a closed-form expression determined by the number of layers and the branching factor.
The source-sink linking subcomponent has length equal to the graph distance from source to sink.
Off-path branches may form but do not alter the uniqueness of the main connecting path.
The same exact tracking applies to any layered graph whose attachment probabilities admit a recursive closed form.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The unique-path property may extend to other vertex-transitive graphs if their layer-wise hitting probabilities can be computed exactly.
In the limit of infinite branching or infinite depth the model might recover growth-rate results from classical continuum DLA.
Direct enumeration on small regular trees would confirm the predicted finish time without Monte Carlo sampling.

Load-bearing premise

The layered graph structure permits exact tracking of attachment probabilities without post-hoc adjustments or simulation.

What would settle it

Simulate the process on a small Cayley tree with three layers and branching factor two, then check whether the observed number of steps until the source is occupied equals the closed-form finish time and whether the source-sink connection in the final cluster is a single path.

read the original abstract

In the classical model of Diffusion Limited Aggregation (DLA), introduced by Witten and Sander, the process begins with a single particle cluster placed at the origin of a space, and then, one at a time, particles make a random walk from infinity until they collide with, and stick to, the existing cluster. We consider an analogous version of this process on large but finite graphs with a designated source and sink vertex. Initially the cluster of halted particles contains a single particle at the sink vertex. Starting one at a time from the source, each particle makes a random walk in the direction of the sink vertex. The particle halts at the last unoccupied vertex before the walk enters the cluster for the first time, thus increasing the size of the cluster. This continues until the source vertex becomes occupied, at which point the process ends. We study the DLA process on several classes of layered graphs, including Cayley trees of branching factor at least two with a sink vertex attached to the leaves. We determine the finish time of the process for a given class of graphs and show that the subcomponent of the final cluster linking source to sink is essentially a unique path.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Exact finish times and unique source-sink path for DLA on Cayley trees via layer-count recursion.

read the letter

The core result is a source-sink DLA variant on finite layered graphs where particles walk from source toward sink and attach at the last free vertex before the cluster; on Cayley trees they obtain closed-form finish times and show the final source-sink subcluster is essentially a single path. The layered symmetry lets them track attachment probabilities from vertex counts per layer alone, turning the process into a solvable recursion. That is the actual novelty: classical DLA has almost no exact formulas, so having them for this natural finite-graph family is concrete progress. The proofs appear to rest on direct counting rather than fitting or simulation, which is the right approach for these graphs. The main limitation is narrow scope; the model is tailored to regular layered structures and the random-walk bias toward the sink is defined to exploit that regularity, so the same technique will not transfer immediately to grids or irregular graphs. If the recursion really closes without hidden case splits or renormalization, the claims hold; nothing in the abstract suggests circularity or free parameters. This is useful reading for people working on exactly solvable aggregation models or random processes on trees. A referee should check the walk definition and the induction step carefully, but the paper is worth sending out because the statements are precise and the setting is clean.

Referee Report

1 major / 2 minor

Summary. The paper analyzes a finite-graph variant of diffusion-limited aggregation (DLA) in which particles perform random walks from a designated source toward a sink, attaching at the last unoccupied vertex before first contact with the growing cluster. For Cayley trees of branching factor at least 2 with the sink attached to all leaves, the authors claim an exact closed-form expression for the finish time (the step at which the source is occupied) together with the statement that the source-to-sink subcluster of the final aggregate is essentially a unique path.

Significance. Exact, non-asymptotic results for DLA-type processes remain rare; if the claimed closed-form finish time and path-uniqueness statements are rigorously established via the layered recursion, the work supplies a concrete benchmark family on which more general heuristics can be tested. The structural regularity of the graphs is used to obtain parameter-free expressions, which is a genuine strength when the attachment probabilities factor cleanly.

major comments (1)

[Section deriving the attachment probabilities and finish-time formula for Cayley trees] The central recursion for attachment probabilities (used to derive the finish-time formula) is asserted to depend only on layer occupancies. The manuscript must explicitly verify that the absorbing random-walk dynamics on the tree never produce non-factorizable competition among frontier vertices at the same layer; otherwise the claimed closed form does not follow. This verification is load-bearing for both the finish-time result and the uniqueness claim.

minor comments (2)

Notation for the layered graph families should be introduced with a single consolidated figure or table rather than scattered definitions.
The phrase 'essentially a unique path' requires a precise probabilistic statement (e.g., probability 1-o(1) or probability 1) together with the precise sense in which multiple paths are ruled out.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading, positive assessment of the significance of exact DLA results, and the specific suggestion for strengthening the argument. We address the major comment below.

read point-by-point responses

Referee: [Section deriving the attachment probabilities and finish-time formula for Cayley trees] The central recursion for attachment probabilities (used to derive the finish-time formula) is asserted to depend only on layer occupancies. The manuscript must explicitly verify that the absorbing random-walk dynamics on the tree never produce non-factorizable competition among frontier vertices at the same layer; otherwise the claimed closed form does not follow. This verification is load-bearing for both the finish-time result and the uniqueness claim.

Authors: We agree that an explicit verification of the layer-occupancy dependence is necessary for rigor. In the Cayley tree the regular branching factor and identical subtrees rooted at each vertex of a given layer imply that the hitting distribution of an absorbing random walk (with absorption on the current cluster) is identical for all unoccupied vertices at the same distance from the sink. Consequently, the probability that a new particle attaches to a particular frontier vertex depends only on the number of occupied sites per layer, with no residual dependence on the specific configuration within a layer. We will insert a short lemma (with a symmetry argument based on the automorphism group of the tree) immediately before the recursion in the revised manuscript; this will also cover the uniqueness claim for the source-to-sink path. The change is purely expository and does not alter any stated results. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained combinatorial analysis on layered graphs

full rationale

The paper derives exact finish times and the unique-path property for DLA on Cayley trees (branching factor ≥2) and similar layered graphs by direct recursive tracking of attachment probabilities from layer counts and the absorbing random-walk rule. No equations, fitted parameters, or self-citations are shown that reduce any claimed prediction to a tautology or to the input data by construction. The layered structure is an external graph property that permits closed-form recursion; it is not smuggled in via prior self-work or defined circularly. This is the expected outcome for a rigorous graph-process analysis.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities can be extracted beyond the basic modeling choices stated in the process definition.

axioms (1)

domain assumption Particles perform random walks directed toward the sink and halt at the last unoccupied vertex before first entering the cluster.
This rule is the core definition of the process given in the abstract.

pith-pipeline@v0.9.0 · 5724 in / 1142 out tokens · 24570 ms · 2026-05-24T04:47:16.879130+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Asselah and A

A. Asselah and A. Gaudilliere. Sub-logarithmic ﬂuctuations for inte rnal DLA. The An- nals of Probability, 41(3), 1160-1179 (2013)

work page 2013
[2]

Batty, P

M. Batty, P. Longley and S. Fotheringham. Urban growth and fo rm: scaling, fractal geometry, and diﬀusion-limited aggregation. Environment and Plann ing A, 21, 1447- 1472 (1989)

work page 1989
[3]

Diaconis and W

P. Diaconis and W. Fulton. A growth model, a game, an algebra, lagr ange inversion, and characteristic classes. Rend. Sem. Mat. Univ. Pol. Torino, 49( 1):95–119, (1991)

work page 1991
[4]

A. M. Frieze and W. Pegden. Diﬀusion limited aggregation on the Boo lean lattice, Annals of Applied Probability Vol. 28(6), 3528–3557, (2018)

work page 2018
[5]

T. C. Halsey. Diﬀusion limited aggregation: A model for pattern fo rmation. Physics Today 53 (11), 36–41, (2000)

work page 2000
[6]

M. B. Hastings and T. C. Halsey. High-dimensional diﬀusive growth , Europhys. Lett., 55(5), 679—685 (2001)

work page 2001
[7]

Jerison, L

D. Jerison, L. Levine, and S. Sheﬃeld. Logarithmic ﬂuctuations f or Internal DLA. Jour- nal of the American Mathematical Society Vol. 25(1), pp. 271-301 (2012)

work page 2012
[8]

H. Kesten. How long are the arms in DLA? Journal of Physics A: Ma thematical and General, 20(1), L29–L33, (1987)

work page 1987
[9]

G. F. Lawler, M. Bramson and D. Griﬀeath. Internal Diﬀusion Limit ed Aggregation, Ann. Probab. 20 (4) 2117–2140, (1992)

work page 1992
[10]

G. F. Lawler. Subdiﬀusive ﬂuctuations for internal diﬀusion limite d aggregation. Ann. Probab., 23(1):71–86, (1995)

work page 1995
[11]

Niemeyer, L

L. Niemeyer, L. Pietronero, and H. J. Wiesmann. Fractal dimen sion of dielectric break- down. Phys. Rev. Lett., 52(12):1033–1036, (1984)

work page 1984
[12]

T. A. Witten and L. M. Sander. Diﬀusion-limited aggregation, a kin etic critical phe- nomenon, Physics Review Letters, Vol. 47, No. 19, 1400–1403, (1 981)

work page
[13]

T. A. Witten and L. M. Sander. Diﬀusion-limited aggregation, Phy s. Rev. B 27, 5686– 5697, (1983). 29 Appendix The eﬀect of rounding error in the growing layers model. We examine conditions on d, k which allow us to eﬀectively ignore the rounding error on j∗ in the value of Tf , and show that (log d)/ √ k = O(1) suﬃces. In the case that j∗ is not integer,...

work page 1983

[1] [1]

Asselah and A

A. Asselah and A. Gaudilliere. Sub-logarithmic ﬂuctuations for inte rnal DLA. The An- nals of Probability, 41(3), 1160-1179 (2013)

work page 2013

[2] [2]

Batty, P

M. Batty, P. Longley and S. Fotheringham. Urban growth and fo rm: scaling, fractal geometry, and diﬀusion-limited aggregation. Environment and Plann ing A, 21, 1447- 1472 (1989)

work page 1989

[3] [3]

Diaconis and W

P. Diaconis and W. Fulton. A growth model, a game, an algebra, lagr ange inversion, and characteristic classes. Rend. Sem. Mat. Univ. Pol. Torino, 49( 1):95–119, (1991)

work page 1991

[4] [4]

A. M. Frieze and W. Pegden. Diﬀusion limited aggregation on the Boo lean lattice, Annals of Applied Probability Vol. 28(6), 3528–3557, (2018)

work page 2018

[5] [5]

T. C. Halsey. Diﬀusion limited aggregation: A model for pattern fo rmation. Physics Today 53 (11), 36–41, (2000)

work page 2000

[6] [6]

M. B. Hastings and T. C. Halsey. High-dimensional diﬀusive growth , Europhys. Lett., 55(5), 679—685 (2001)

work page 2001

[7] [7]

Jerison, L

D. Jerison, L. Levine, and S. Sheﬃeld. Logarithmic ﬂuctuations f or Internal DLA. Jour- nal of the American Mathematical Society Vol. 25(1), pp. 271-301 (2012)

work page 2012

[8] [8]

H. Kesten. How long are the arms in DLA? Journal of Physics A: Ma thematical and General, 20(1), L29–L33, (1987)

work page 1987

[9] [9]

G. F. Lawler, M. Bramson and D. Griﬀeath. Internal Diﬀusion Limit ed Aggregation, Ann. Probab. 20 (4) 2117–2140, (1992)

work page 1992

[10] [10]

G. F. Lawler. Subdiﬀusive ﬂuctuations for internal diﬀusion limite d aggregation. Ann. Probab., 23(1):71–86, (1995)

work page 1995

[11] [11]

Niemeyer, L

L. Niemeyer, L. Pietronero, and H. J. Wiesmann. Fractal dimen sion of dielectric break- down. Phys. Rev. Lett., 52(12):1033–1036, (1984)

work page 1984

[12] [12]

T. A. Witten and L. M. Sander. Diﬀusion-limited aggregation, a kin etic critical phe- nomenon, Physics Review Letters, Vol. 47, No. 19, 1400–1403, (1 981)

work page

[13] [13]

T. A. Witten and L. M. Sander. Diﬀusion-limited aggregation, Phy s. Rev. B 27, 5686– 5697, (1983). 29 Appendix The eﬀect of rounding error in the growing layers model. We examine conditions on d, k which allow us to eﬀectively ignore the rounding error on j∗ in the value of Tf , and show that (log d)/ √ k = O(1) suﬃces. In the case that j∗ is not integer,...

work page 1983