Linear variance for tree counts and core-driven limits for multicyclic counts in uniform attachment graphs

Unrefereed research candidate. Proofs of two conjectures of Björklund, Holmgren, Janson and Lo, with the next-order fluctuations of multicyclic counts. Context. In the uniform attachment graph (the random recursive dag; for m = 1 the random recursive tree) vertices arrive one at a time and each new vertex sends m edges to older vertices chosen independently and uniformly at random. Björklund, Holmgren, Janson and Lo (Combinatorics, Probability and Computing 34 (2025), doi:10.1017/S0963548324000294) determined the orders of magnitude of the number WH(n) of copies of a fixed small pattern H and stated two conjectures: (Conjecture 3.8) the count of every tree with at least two edges has variance of exact order n; (Conjecture 3.14) for a pattern with two or more independent cycles, with 2-core C and t pendant vertices, WH(n)/(log n)t converges almost surely to a constant times the eventual number WC(∞) of copies of the core. Main results. (1) Theorem 1.3: every nonzero linear combination of distinct tree counts (trees with at least two edges) has variance of exact order n, with an explicit lower bound; this proves Conjecture 3.8. (2) Theorem 1.4: the leading means and covariances are explicit polynomials in m, the covariance matrix is nonsingular, and tree counts are jointly asymptotically normal, with mixing convergence; at m = 2 the variance constants of the two-edge path, three-edge path and three-leaf star are 12, 1688 and 888. The O(n−1/2) normal-approximation rate for single tree counts is inherited from Theorem 3.7 of Björklund, Holmgren, Janson and Lo. (3) Theorem 1.5: for multicyclic patterns WH(n)/(log n)t → cH,mWC(∞) almost surely and in every Lp, with a hook-length constant cH,m; this proves Conjecture 3.14; every simple cyclic core is absent with positive probability. (4) Theorem 1.6: the error in (3) is of order (log n)t−1/2 and is normal with a random variance fixed by how the core copies share vertices (stable convergence). Supporting results. Finite formulas and exact tables for the tree constants; a chi-square corollary; exact finite-n means; a fixed-root forest law with a Gaussian refinement; moment bounds; transfer of the tree results to the simple graph with parallel edges merged. Limits. Fixed patterns and fixed m only; no rate for the multivariate normal limit; unicyclic patterns, preferential attachment and sampling without replacement are not treated; the multicyclic limit is approached slowly (relative error of order (log n)−1/2, about 0.3 at n = 105); centring tree counts at nμT(m) is noticeably biased at realistic sizes, and exact finite-n means are provided. Contents. The paper (LaTeX source and PDF); exact rational and symbolic computation of the tree constants (variance_constants.py) and an exact check suite (reproduce.py: 29 checks, including a second implementation, complete small-n enumeration and the covariance determinant 215808 at m = 2); scripts for the mean core count, finite-n centring error, a direct-count Monte Carlo check of the constants and a Monte Carlo illustration of the next-order fluctuations, with recorded outputs; the bibliography; a machine-readable index; a research-gate record; a review summary; a replay receipt and SHA-256 sums. Checks exit with status 1 on failure, also under python -O. The computations check formulas and conventions; the proofs carry the mathematical claims. Assurance. Written proofs with exact and Monte Carlo computational checks. Internal AI-assisted review only: five reviewer roles run as Claude subagents, a clean replay, one revision round with extensions, then a re-review and a proof audit of the new Section 6 as Claude subagents. The planned second-model adversarial review did not run because of a usage limit. Not peer review, independent reproduction or formal verification. Creator: Anonymous. Text CC0-1.0; code MIT.

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-16
DOI
https://doi.org/10.5281/zenodo.24282889
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Linear variance for tree counts and core-driven limits for multicyclic counts in uniform attachment graphs

2 links
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Linear variance for tree counts and core-driven limits for multicyclic counts in uniform attachment graphs

preprint en

Abstract

Unrefereed research candidate. Proofs of two conjectures of Björklund, Holmgren, Janson and Lo, with the next-order fluctuations of multicyclic counts. Context. In the uniform attachment graph (the random recursive dag; for m = 1 the random recursive tree) vertices arrive one at a time and each new vertex sends m edges to older vertices chosen independently and uniformly at random. Björklund, Holmgren, Janson and Lo (Combinatorics, Probability and Computing 34 (2025), doi:10.1017/S0963548324000294) determined the orders of magnitude of the number WH(n) of copies of a fixed small pattern H and stated two conjectures: (Conjecture 3.8) the count of every tree with at least two edges has variance of exact order n; (Conjecture 3.14) for a pattern with two or more independent cycles, with 2-core C and t pendant vertices, WH(n)/(log n)t converges almost surely to a constant times the eventual number WC(∞) of copies of the core. Main results. (1) Theorem 1.3: every nonzero linear combination of distinct tree counts (trees with at least two edges) has variance of exact order n, with an explicit lower bound; this proves Conjecture 3.8. (2) Theorem 1.4: the leading means and covariances are explicit polynomials in m, the covariance matrix is nonsingular, and tree counts are jointly asymptotically normal, with mixing convergence; at m = 2 the variance constants of the two-edge path, three-edge path and three-leaf star are 12, 1688 and 888. The O(n−1/2) normal-approximation rate for single tree counts is inherited from Theorem 3.7 of Björklund, Holmgren, Janson and Lo. (3) Theorem 1.5: for multicyclic patterns WH(n)/(log n)t → cH,mWC(∞) almost surely and in every Lp, with a hook-length constant cH,m; this proves Conjecture 3.14; every simple cyclic core is absent with positive probability. (4) Theorem 1.6: the error in (3) is of order (log n)t−1/2 and is normal with a random variance fixed by how the core copies share vertices (stable convergence). Supporting results. Finite formulas and exact tables for the tree constants; a chi-square corollary; exact finite-n means; a fixed-root forest law with a Gaussian refinement; moment bounds; transfer of the tree results to the simple graph with parallel edges merged. Limits. Fixed patterns and fixed m only; no rate for the multivariate normal limit; unicyclic patterns, preferential attachment and sampling without replacement are not treated; the multicyclic limit is approached slowly (relative error of order (log n)−1/2, about 0.3 at n = 105); centring tree counts at nμT(m) is noticeably biased at realistic sizes, and exact finite-n means are provided. Contents. The paper (LaTeX source and PDF); exact rational and symbolic computation of the tree constants (variance_constants.py) and an exact check suite (reproduce.py: 29 checks, including a second implementation, complete small-n enumeration and the covariance determinant 215808 at m = 2); scripts for the mean core count, finite-n centring error, a direct-count Monte Carlo check of the constants and a Monte Carlo illustration of the next-order fluctuations, with recorded outputs; the bibliography; a machine-readable index; a research-gate record; a review summary; a replay receipt and SHA-256 sums. Checks exit with status 1 on failure, also under python -O. The computations check formulas and conventions; the proofs carry the mathematical claims. Assurance. Written proofs with exact and Monte Carlo computational checks. Internal AI-assisted review only: five reviewer roles run as Claude subagents, a clean replay, one revision round with extensions, then a re-review and a proof audit of the new Section 6 as Claude subagents. The planned second-model adversarial review did not run because of a usage limit. Not peer review, independent reproduction or formal verification. Creator: Anonymous. Text CC0-1.0; code MIT.

Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon