Finding the root in random nearest neighbor trees

Anna Brandenberger; Cassandra Marcussen; Elchanan Mossel; Madhu Sudan

REVIEW 2 major objections 6 minor 1 cited by

Finding the root in random nearest neighbor trees

T0 review · 2 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For a random nearest neighbor tree on the 1-D torus, an efficient algorithm returns a confidence set of size $\Theta(\log(1/\varepsilon)/\log\log(1/\varepsilon))$ containing the root with probability $1-\varepsilon$, and matching lower…

desk verdict Genuinely new root-finding results for geometric random trees, with a tight 1D story; the d≥2 upper bound currently rests on an unproved structural claim, so the proof needs revision before the result is complete. read the letter →

arxiv 2411.14336 v1 pith:GYRHWEAF submitted 2024-11-21 math.PR cs.DScs.SI

Anna Brandenberger , Cassandra Marcussen , Elchanan Mossel , Madhu Sudan This is my paper · ORCID

classification math.PRcs.DScs.SI MSC 60D0505C8060C05

keywords rootfindingnetworkarchaeologyrandomnearestneighbortreegeometricgraphsconfidencesetsuncoveredverticeslongedgesrecursivetrees

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks whether the geometry of a randomly grown tree reveals which vertex arrived first, and establishes a strong yes for the random nearest neighbor model on the $d$-dimensional torus. It shows that an efficient algorithm given the unlabeled tree together with its embedding, or just its edge lengths, can return a confidence set of size independent of $n$ that contains the root with probability at least $1-\varepsilon$. In one dimension the result is sharp: the required set size is $\Theta(\log(1/\varepsilon)/\log\log(1/\varepsilon))$, exponentially smaller than the known bounds for uniform and preferential attachment trees. In $d \ge 2$ the paper gives an efficient algorithm with subpolynomial-in-$1/\varepsilon$ confidence set size and an information-theoretic lower bound. If correct, geometry turns root finding from a search over a growing tree into a search over a small neighborhood of a few early long edges.

What carries the argument

The load-bearing objects are long edges and the induced subgraph of uncovered vertices. An edge is long when its torus length exceeds a threshold $\ell$ chosen as a function of $\varepsilon$; in $d=1$ an edge covers the interval between its endpoints, and a vertex is uncovered if no edge interval contains it, while in $d \ge 2$ an edge covers a forbidden region of points closer to both endpoints than the edge length, and vertices falling there, or in their subtrees, are covered. The uncovered subgraph always contains the root, is a path in $d=1$, and has maximum degree bounded by a constant depending only on $d$ (Lemma 5.1). The algorithms return the uncovered vertices within graph distance $k$ of an edge longer than $\ell$; the size bound comes from packing disjoint balls around long edges and the bounded degree of the uncovered subgraph, while correctness comes from the high probability that a long edge appears among the first $k$ edges and that the root is close to it. The lower bounds use the MLE posterior over feasible arrival-order permutations on specially constructed path-like tree families.

What would settle it

Simulate 2-NN trees on the unit torus for large $n$ and small $\varepsilon$; among the first $k = \gamma \log(1/\varepsilon)$ edges, find the first edge of length at least $\ell = (C(d)\,\gamma\, e^{1/\gamma} \log(1/\varepsilon))^{-1/d}$ and measure the graph distance in the uncovered subgraph from the earlier endpoint of that edge to vertex 1. If this distance exceeds $7\log k$ with non-negligible probability for some $\varepsilon$, the correctness claim behind Lemma 5.2 fails.

Watch

Extended reading notes

Core claim

The central claim is that geometric information about a random nearest neighbor tree localizes the root almost completely. For $d=1$, the paper proves matching upper and lower bounds: there is an $O(n^2 + \log^2(1/\varepsilon))$-time embedded root finding algorithm returning a confidence set with $|H| \log|H| \le c_1 \log(1/\varepsilon)$, and no algorithm can guarantee $|H| \log|H| < c_2 \log(1/\varepsilon)$; equivalently the optimal set size is $\Theta(\log(1/\varepsilon)/\log\log(1/\varepsilon))$. The upper bound works by showing that with high probability one of the first $k \approx \log(1/\varepsilon)$ edges is long, that the root lies within graph distance $O(\log k)$ of such an edge in the subgraph of uncovered vertices, and that this subgraph has bounded degree, so a radius-$k$ exploration around all long edges has size only subpolynomial in $1/\varepsilon$. For $d \ge 2$ the same long-edge and uncovered-vertex strategy yields an efficient algorithm with confidence set size $\exp(\log(1/\varepsilon)/(\log\log(1/\varepsilon) + d\log\log(1/\varepsilon)))$ and an impossibility result of the form $|H| \log(|H|^{(d-1)/d}) \ge c \log(1/\varepsilon)/d$. The lower bounds rest on families of path-like configurations that occur with probability at least $\varepsilon$ and in which the root has lower posterior probability than at least $K(\varepsilon)$ other vertices, so any $K(\varepsilon)$-sized confidence set must fail.

Load-bearing premise

For the $d \ge 2$ upper bound, the correctness proof relies on the unproved assertion that whenever one of the first $k$ edges is long, the root is within graph distance $7\log k$ of that edge in the bounded-degree uncovered subgraph; if that proximity claim fails, the algorithm's confidence set can miss the root.

Editorial extensions

If this is right

In $d=1$, the confidence set size becomes logarithmic in $1/\varepsilon$ instead of subpolynomial, so geometric information makes root finding exponentially more efficient than in uniform or preferential attachment trees.
The 1-D algorithm runs in $O(n^2 + \log^2(1/\varepsilon))$ time and needs only the unlabeled embedded tree, so it can be applied directly to a snapshot of a growing geometric network without labels or arrival times.
For $d \ge 2$, the paper's algorithm still returns a confidence set whose size is uniformly bounded in $n$ and subpolynomial in $1/\varepsilon$, matching the current best known upper bound for uniform attachment trees.
Metric root finding, using only edge lengths, already gives an $O(n)$-time algorithm with confidence set size at most $2^d/\varepsilon$, and with high probability every returned vertex arrived within the first $\exp(cd)(1/\varepsilon)\log(1/\varepsilon)$ steps.
The $d=1$ bounds carry over to a thin two-dimensional strip of height $O(\varepsilon^5)$, so quasi-one-dimensional geometry is enough to obtain the logarithmic bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the same long-edge heuristic should transfer to other geometric growth models such as geometric preferential attachment, where early edges are also expected to be atypically long, potentially keeping confidence sets small.
Editorial inference: because both the positive algorithms and the lower-bound families use edge lengths or embeddings, the graph root finding variant (adjacency matrix only) may require substantially larger confidence sets or be impossible for geometric models.
Editorial inference: the thin-strip corollary suggests that effective dimension, not ambient dimension, controls the $\log(1/\varepsilon)$ bound; testing strip heights between $O(\varepsilon^5)$ and $O(1)$ could reveal where the one-dimensional behavior breaks down.
Editorial inference: the paper's $d \ge 2$ lower bound uses path-like configurations, but richer geometric families, such as branching or curved paths, might push the lower bound closer to the subpolynomial upper bound.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

You should know two things about arXiv:2411.14336. First, it answers a real open question from Lichev and Mitsche by giving the first root-finding bounds for random nearest neighbor trees, and in d=1 the bounds are tight: Θ(log(1/ε)/log log(1/ε)). Second, the paper as submitted has a genuine gap in the d≥2 upper bound and a smaller sign error in the 1D lower bound; both are fixable, but the d≥2 gap needs real work.

What's new and good: the three problem formulations (embedded, metric, graph) are natural and will likely stick. The metric algorithm that returns endpoints of long edges is simple and gives O(1/ε) size, with a nice early-arrival guarantee. The 1D upper bound uses the uncovered-vertices path structure cleverly, and the lower bound via a family of path-shaped trees is a clean adaptation of Bubeck–Devroye–Lugosi. The writing is clear, and the paper is honest about what remains open.

Soft spots:

1. Section 5 (d≥2). Lemma 5.2's correctness step relies on the claim that, when an early edge is long, the earlier endpoint is within graph distance 7 log k of the root in the induced subgraph of uncovered vertices. This is announced as a “crucial structural component” in §5.1, but no proof or reference is given. Since Algorithm 4 expands only through the uncovered subgraph U_n, the trivial time-index bound does not suffice, and without the missing lemma the confidence set could in principle miss the root. This is load-bearing, not a nit. The assertion may be true, but it needs proof.

2. Section 3.3. The comparison of the family probability 2(K+5)^{-(K+1)} to ε goes the wrong direction: for the family to have probability at least ε you need (K+1)log(K+5) ≤ log(2/ε), not ≥. The final lower bound statement is correct, and the fix is straightforward, but as written it is a sign error.

3. Minor: the statement of the d≥2 lower bound in Theorem 1.2 has an awkward exponent |H|^{(d-1)/d}; the lemma in §5.3 is cleaner and likely the intended form.

Bottom line: the 1D results look right modulo the sign fix, and the metric algorithm is solid. The d≥2 upper bound is the main concern—I would want to see the missing structural lemma proved before trusting Theorem 1.2. This is absolutely worth serious refereeing: it opens a new direction and the core ideas are good. I would recommend conditional acceptance after the authors fill the gap; a desk rejection would be wrong.

For a reading group, this is a good paper to discuss—both for the clever 1D construction and as an example of a missing-load-bearing-lemma situation.

Referee Report

2 major / 6 minor

Summary. The paper studies root finding in random nearest neighbor trees on the d-dimensional torus, where the algorithm receives the unlabeled embedded tree (or metric information) and must return a confidence set containing the root with probability at least 1−ε. The main results are: for d=1, an O(n^2 + log^2(1/ε))-time algorithm with confidence set size Θ(log(1/ε)/log log(1/ε)), matching an information-theoretic lower bound; for d≥2, an algorithm with subpolynomial confidence set size and a polylogarithmic lower bound. The algorithms are based on long edges and the induced subgraph of uncovered vertices, and the lower bounds use maximum-likelihood comparisons on specially constructed path-like families.

Significance. If the results are correct, they establish that geometric information dramatically reduces the root-finding difficulty compared to uniform and preferential attachment trees, where confidence sets must be subpolynomial in 1/ε. The paper also introduces a clean framework (embedded, metric, and graph root finding) and provides explicit algorithms with runtime guarantees as well as information-theoretic lower bounds. However, the significance is conditional on closing the gaps below, particularly the unproved structural assertion underlying the d≥2 upper bound.

major comments (2)

[§5.1, Lemma 5.2] The correctness of Algorithm 4 in Lemma 5.2 depends on the claim, listed in the introduction to Section 5.1, that with high probability the earlier endpoint of an early long edge is within graph distance 7 log k of the root in the induced subgraph of uncovered vertices U_n. This claim is asserted without a proof, a lemma, or a citation, and the subsequent proof of Lemma 5.2 uses it implicitly when it states that if any of the first k edges are long then the algorithm includes the root. Since Algorithm 4 expands only through U_n, the trivial full-tree distance bound of at most k from time indices does not imply that the root is near the edge in U_n. Without a proof of this O(log k) structural bound, the upper bound of Theorem 1.2 is not established. The authors should provide a complete proof or reference for this assertion, and also prove that the root is always uncovered (or otherwise handle the covered case).
[§3.3, claim (ii)] The lower-bound proof for d=1 contains an inequality-direction error. The family F of trees has probability 2(K(ε)+5)^{-(K(ε)+1)}. The text states that this is at least ε when K(ε) satisfies (K(ε)+1)log(K(ε)+5) ≥ log(2/ε), but the reverse inequality is required: one needs (K(ε)+1)log(K(ε)+5) ≤ log(2/ε) for the probability to be at least ε. As written, claim (ii) is false, and the proof does not show that the constructed family is ε-likely. Although the final lower bound in Eq. (8) has the correct direction if the argument is repaired, the current proof is not valid.

minor comments (6)

[§3.2, Lemma 3.3 proof] The line 'to argue that P{1 ̸∈ H(ε, n)} ≥ 1 − ε' should read 'P{1 ∈ H(ε, n)} ≥ 1 − ε' or 'P{1 ̸∈ H(ε, n)} ≤ ε'.
[§3.1, Lemma 3.1] The phrase 'expected size X_{K+1}' should be 'expected time' or 'E[X_{K+1}]', since X_{K+1} is a time index, not a size.
[§5.2, Eq. (14) and Eq. (16)] The treatment of constants is a bit loose: after absorbing factors into a universal constant, the statement should clarify that the constant may depend on the fixed dimension d and does not claim uniformity in d.
[§4.1, Claim 1] The phrase 'all edges added before then are long' is misleading; the claim proves a lower bound L on the projected edge lengths, not that the edges are long in the ε-dependent sense of the algorithm. Please rephrase.
[§5.2, Algorithm 4, Step 1] The direction-assignment procedure for covered vertices is described only informally; a precise iterative or recursive description would help the reader verify termination and consistency of the cover marking.
[§3.2, Lemma 3.3 proof] The sentence 'Therefore, the runtime of Step 2 is bounded above by log^2(1/ε)' should be written as O(log^2(1/ε)) and should clarify why the n-dependence of Step 2 is absorbed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the d≥2 upper bound has an unproved structural assertion, but that is a missing-proof gap, not a circular reduction.

full rationale

The paper's derivation chain is self-contained for the purposes of a circularity analysis. The upper bounds are driven by explicit geometric events: long edges arrive early, uncovered vertices form a bounded-degree subgraph, and the confidence set is built by expanding only through uncovered vertices. The parameters k and ℓ in Algorithms 2 and 4 are chosen so that the union bound P{1∉H} ≤ (k C(d) ℓ^d)^k equals ε (Eq. 15 and the line after Eq. 13); this is standard parameter selection, not fitting a prediction to the target. The lower bounds compare any algorithm against the MLE over explicitly constructed families F and count feasible permutations; they do not import a uniqueness theorem or rename a known result. The only self-citation ([BDG22] for impossibility in Galton-Watson trees) is not load-bearing. One genuine gap exists: in Section 5.1 the paper lists as a 'crucial structural component' the assertion that the earlier endoint of an early long edge is within graph distance 7 log k of the root in the uncovered subgraph, and Lemma 5.2's correctness step ('if any of the first k edges are long ... the algorithm successfully includes the root') relies on it without proof. This is an omitted proof and missing support, not a circular reduction: the assertion is not defined in terms of the conclusion, nor is it a renamed restatement of the algorithm's output. Therefore the circularity score is 0.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The paper has no fitted empirical parameters or invented physical entities. The constants k and ell are chosen as functions of epsilon so that union-bound estimates close, which is normal proof design. The main extra axiom is the unproved d >= 2 assumption that the root is close, after pruning, to an early long edge. Everything else rests on standard probabilistic and geometric background or on the symmetry of the model.

free parameters (3)

1D expansion radius k = k log k = C log(2/epsilon), C > 1 sufficiently large
Algorithm 2 sets this radius to make the failure probability in Lemma 3.3 fit below epsilon/2; it is a proof parameter, not an empirical fit.
1D long-edge cutoff ell = ell = 1/(5k)
Algorithm 2 uses this cutoff to control both the number of long edges and the probability that an early long edge exists.
d >= 2 radius k and cutoff ell = k = gamma log(1/epsilon), gamma = 1/(d log a log log(1/epsilon)), ell = (C(d) gamma e^{1/gamma} log(1/epsilon))^{-1/d}
Algorithm 4 chooses these values so that the union-bound error is at most epsilon and the confidence set is subpolynomial in 1/epsilon.

assumptions (5)

ad hoc to paper For d >= 2, the root is within graph distance k (or 7 log k) of an early long edge in the uncovered subgraph.
Stated in Section 5 as a needed structural component but no proof or formal lemma is provided; the correctness proof of Lemma 5.2 depends on it.
standard math At most a^d unit vectors on S^{d-1} can have pairwise inner product at most cos(pi/3).
Used in Lemma 5.1 to bound the degree of the uncovered subgraph; this is a standard spherical-code packing bound, but the paper does not prove it.
standard math The diameter of a Voronoi cell is bounded by sqrt(2) times the maximum cone distance to a neighboring point.
Invoked as Lemma 2.3 from DGLW17 to show that all returned vertices arrive early in the metric algorithm.
standard math Around every point in R^d, the space can be covered with at most 3^d cones of angle pi/4.
Invoked as Lemma 2.2 from DGL13 to support the Voronoi cell diameter argument.
domain assumption For a fixed embedded unlabeled tree, every feasible arrival permutation has equal probability.
Used in the MLE lower bounds in Section 3.3 and Section 5.3; it follows from i.i.d. uniform positions and the exchangeability of labels, but it is a symmetry assumption about the generative model.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Finding the root in random nearest neighbor trees." pith.science (2026). https://pith.science/paper/GYRHWEAF

@misc{pith2026241114336,
  author       = {Pith},
  title        = {Pith review of: Finding the root in random nearest neighbor trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GYRHWEAF}},
  note         = {Machine review of arXiv:2411.14336}
}

abstract

We study the inference of network archaeology in growing random geometric graphs. We consider the root finding problem for a random nearest neighbor tree in dimension $d \in \mathbb{N}$, generated by sequentially embedding vertices uniformly at random in the $d$-dimensional torus and connecting each new vertex to the nearest existing vertex. More precisely, given an error parameter $\varepsilon > 0$ and the unlabeled tree, we want to efficiently find a small set of candidate vertices, such that the root is included in this set with probability at least $1 - \varepsilon$. We call such a candidate set a $\textit{confidence set}$. We define several variations of the root finding problem in geometric settings -- embedded, metric, and graph root finding -- which differ based on the nature of the type of metric information provided in addition to the graph structure (torus embedding, edge lengths, or no additional information, respectively). We show that there exist efficient root finding algorithms for embedded and metric root finding. For embedded root finding, we derive upper and lower bounds (uniformly bounded in $n$) on the size of the confidence set: the upper bound is subpolynomial in $1/\varepsilon$ and stems from an explicit efficient algorithm, and the information-theoretic lower bound is polylogarithmic in $1/\varepsilon$. In particular, in $d=1$, we obtain matching upper and lower bounds for a confidence set of size $\Theta\left(\frac{\log(1/\varepsilon)}{\log \log(1/\varepsilon)} \right)$.

Figures

Figures reproduced from arXiv: 2411.14336 by the authors.

**Figure 2.** Our algorithm returns uncovered vertices within a graph distance of k of an edge of length at least ℓ, where k and ℓ are defined with respect to ε. In this figure, the vertices highlighted in orange are added to the confidence set since they are uncovered and graph-theoretically near an edge of length at least ℓ. In the figure, uncovered vertices and edges are green and covered vertices and edges are red. We now arg… view at source ↗

**Figure 4.** When the thickness of the strip is small enough, we argue that when projecting to T1 , the uncovered subgraph of π(Tt) up to time t = poly(1/ε) is consistent with the uncovered graph of a 1-NN tree with vertices in the same locations. We can therefore use algorithms from the d = 1 setting over the thin two-dimensional torus. Claim 1. Let Tn be a 2-NN tree over a two-dimensional strip [0, 1] × [0, hε]. With probabili… view at source ↗

**Figure 5.** Simulation of a 2-NN tree of size 10,000. Uncovered edges are labeled as blue and covered edges are labeled as red. The first 20 vertices added are labeled by their time of arrival. Edges that wrap around the torus are dotted. The simulations indicate that the number of uncovered vertices in the tree grows slowly with the number of vertices in the tree [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Subcritical percolation and network archaeology on random recursive tree substrate networks
math.PR 2026-07 accept novelty 5.0 of 10

For random recursive trees with independent Erdős–Rényi shortcut edges, subcritical bond percolation exposes a decorated tree structure on which Jordan centrality recovers the root within a deterministic-size confidence set.

Reference graph

Works this paper leans on

22 extracted references · 19 canonical work pages · cited by 1 Pith paper

[1]

Random partitions of the plane via poissonian coloring and a self-similar process of coalescing planar partitions

David Aldous. Random partitions of the plane via poissonian coloring and a self-similar process of coalescing planar partitions. The Annals of Probability , 46(4):2000--2037, 2018

work page 2000
[2]

Root finding algorithms and persistence of Jordan centrality in growing random trees

Sayan Banerjee and Shankar Bhamidi. Root finding algorithms and persistence of Jordan centrality in growing random trees. The Annals of Applied Probability , 32(3):2180--2210, 2022

work page 2022
[3]

Archaeology of random recursive dags and cooper-frieze random networks

Simon Briend, Francisco Calvillo, and G \'a bor Lugosi. Archaeology of random recursive dags and cooper-frieze random networks. Combinatorics, Probability and Computing , pages 1--15, 2023

work page 2023
[4]

Root estimation in galton--watson trees

Anna M Brandenberger, Luc Devroye, and Marcel K Goh. Root estimation in galton--watson trees. Random Structures & Algorithms , 61(3):520--542, 2022

work page 2022
[5]

Finding Adam in random growing trees

S \'e bastien Bubeck, Luc Devroye, and G \'a bor Lugosi. Finding Adam in random growing trees. Random Structures & Algorithms , 50(2):158--172, 2017

work page 2017
[6]

Estimating the history of a random recursive tree

Simon Briend, Christophe Giraud, G \'a bor Lugosi, and D \'e borah Sulem. Estimating the history of a random recursive tree. arXiv preprint arXiv:2403.09755 , 2024

arXiv 2024
[7]

Degree centrality and root finding in growing random networks

Sayan Banerjee and Xiangying Huang. Degree centrality and root finding in growing random networks. Electronic Journal of Probability , 28:1--39, 2023

work page 2023
[8]

Eve, Adam and the preferential attachment tree

Alice Contat, Nicolas Curien, Perrine Lacroix, Etienne Lasalle, and Vincent Rivoirard. Eve, Adam and the preferential attachment tree. Probability Theory and Related Fields , pages 1--16, 2024

work page 2024

Show all 22 references

[9]

Inference on the history of a randomly growing tree

Harry Crane and Min Xu. Inference on the history of a randomly growing tree. Journal of the Royal Statistical Society Series B: Statistical Methodology , 83(4):639--668, 2021

2021
[10]

A probabilistic theory of pattern recognition , volume 31

Luc Devroye, L \'a szl \'o Gy \"o rfi, and G \'a bor Lugosi. A probabilistic theory of pattern recognition , volume 31. Springer Science & Business Media, 2013

2013
[11]

On the measure of voronoi cells

Luc Devroye, L \'a szl \'o Gy \"o rfi, G \'a bor Lugosi, and Harro Walk. On the measure of voronoi cells. Journal of Applied Probability , 54(2):394--408, 2017

2017
[12]

A geometric preferential attachment model of networks

Abraham D Flaxman, Alan M Frieze, and Juan Vera. A geometric preferential attachment model of networks. Internet Mathematics , 3(2):187--205, 2006

2006
[13]

A spatial preferential attachment model with local clustering

Emmanuel Jacob and Peter M \"o rters. A spatial preferential attachment model with local clustering. In Algorithms and Models for the Web Graph: 10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings 10 , pages 14--25. Springer, 2013

2013
[14]

Phase transitions for random geometric preferential attachment graphs

Jonathan Jordan and Andrew R Wade. Phase transitions for random geometric preferential attachment graphs. Advances in Applied Probability , 47(2):565--588, 2015

2015
[15]

New results for the random nearest neighbor tree

Lyuben Lichev and Dieter Mitsche. New results for the random nearest neighbor tree. Probability Theory and Related Fields , 189(1):229--279, 2024

2024
[16]

Network archaeology: uncovering ancient networks from present-day interactions

Saket Navlakha and Carl Kingsford. Network archaeology: uncovering ancient networks from present-day interactions. PLoS computational biology , 7(4):e1001119, 2011

2011
[17]

Mathew D. Penrose. Multivariate spatial central limit theorems with applications to percolation and spatial graphs . The Annals of Probability , 33(5):1945 -- 1991, 2005

1945
[18]

Limit theory for the random on-line nearest-neighbour graph

MD Penrose and AR Wade. Limit theory for the random on-line nearest-neighbour graph. Random Structures Algorithms , 2006

2006
[19]

Cost of sequential connection for points in space

J Michael Steele. Cost of sequential connection for points in space. Operations Research Letters , 8(3):137--142, 1989

1989
[20]

Quantitative CLTs on the P oisson space via S korohod estimates and p - P oincar\'e inequalities

Tara Trauthwein. Quantitative CLTs on the P oisson space via S korohod estimates and p - P oincar\'e inequalities. arXiv preprint arXiv:2212.03782 , 2022

2022 arXiv
[21]

Explicit laws of large numbers for random nearest-neighbour-type graphs

Andrew R Wade. Explicit laws of large numbers for random nearest-neighbour-type graphs. Advances in Applied Probability , 39(2):326--342, 2007

2007
[22]

Asymptotic theory for the multidimensional random on-line nearest-neighbour graph

Andrew R Wade. Asymptotic theory for the multidimensional random on-line nearest-neighbour graph. Stochastic Processes and their Applications , 119(6):1889--1911, 2009

1911

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Random partitions of the plane via poissonian coloring and a self-similar process of coalescing planar partitions

David Aldous. Random partitions of the plane via poissonian coloring and a self-similar process of coalescing planar partitions. The Annals of Probability , 46(4):2000--2037, 2018

work page 2000

[2] [2]

Root finding algorithms and persistence of Jordan centrality in growing random trees

Sayan Banerjee and Shankar Bhamidi. Root finding algorithms and persistence of Jordan centrality in growing random trees. The Annals of Applied Probability , 32(3):2180--2210, 2022

work page 2022

[3] [3]

Archaeology of random recursive dags and cooper-frieze random networks

Simon Briend, Francisco Calvillo, and G \'a bor Lugosi. Archaeology of random recursive dags and cooper-frieze random networks. Combinatorics, Probability and Computing , pages 1--15, 2023

work page 2023

[4] [4]

Root estimation in galton--watson trees

Anna M Brandenberger, Luc Devroye, and Marcel K Goh. Root estimation in galton--watson trees. Random Structures & Algorithms , 61(3):520--542, 2022

work page 2022

[5] [5]

Finding Adam in random growing trees

S \'e bastien Bubeck, Luc Devroye, and G \'a bor Lugosi. Finding Adam in random growing trees. Random Structures & Algorithms , 50(2):158--172, 2017

work page 2017

[6] [6]

Estimating the history of a random recursive tree

Simon Briend, Christophe Giraud, G \'a bor Lugosi, and D \'e borah Sulem. Estimating the history of a random recursive tree. arXiv preprint arXiv:2403.09755 , 2024

arXiv 2024

[7] [7]

Degree centrality and root finding in growing random networks

Sayan Banerjee and Xiangying Huang. Degree centrality and root finding in growing random networks. Electronic Journal of Probability , 28:1--39, 2023

work page 2023

[8] [8]

Eve, Adam and the preferential attachment tree

Alice Contat, Nicolas Curien, Perrine Lacroix, Etienne Lasalle, and Vincent Rivoirard. Eve, Adam and the preferential attachment tree. Probability Theory and Related Fields , pages 1--16, 2024

work page 2024