Limiting Betti-number distributions in preferential-attachment networks
Fix integers $q \ge 2$ and $m \ge 2q$ and a real $\delta > -m$ with $$x = \frac{m + \delta}{2m + \delta} < \frac{1}{2q}.$$ Start with two vertices joined by $m$ parallel edges. At each time $t \ge 3$ add vertex $t$ and $m$ edges from it, one at a time: given the graph after the first $a - 1$ of them, the old endpoint $v < t$ of edge $a$ is chosen with probability $$\frac{d_{t,a-1}(v) + \delta}{2m(t-2) + (a-1) + (t-1)\delta}, \qquad 1 \le a \le m,$$ where $d_{t,a-1}(v)$ is the current degree of $v$, counting multiplicity; there are no self-loops. Let $X_T$ be the clique complex of the underlying simple graph at time $T$, and $\beta_q(T) = \dim_{\mathbb{Q}} H_q(X_T;\mathbb{Q})$. Siu, Samorodnitsky, Yu and He proved that $\mathbb{E}\beta_q(T)$ is of order $T^{1-2qx}$, and Siu that for every $\omega(T) \to \infty$, with probability tending to one, $T^{1-2qx}/\omega(T) \le \beta_q(T) \le \omega(T)\,T^{1-2qx}$.
Problem. Does $\beta_q(T)/\mathbb{E}\beta_q(T)$ converge in distribution, as $T \to \infty$, to a nondegenerate random variable $W_{q,m,\delta}$, and if so, what is its law? In particular, does $W_{q,m,\delta}$ have a power-law upper tail, for instance a regularly varying one, $$\lim_{z \to \infty} \frac{\Pr(W_{q,m,\delta} > uz)}{\Pr(W_{q,m,\delta} > z)} = u^{-\alpha(q,m,\delta)} \qquad (u > 0)$$ for some $\alpha(q,m,\delta) > 0$, and if so, with what exponent? The expectation is over the random graph, not an empirical average over simulated networks.
Source: Siu (2025), §1.2, who conjectures from simulations that the mean-normalized Betti numbers converge in distribution to a power law; stated in this form, for the regime 2qx < 1, by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- AT, CO
- Keywords
- AIM Open Applied Problems, Betti numbers, clique complexes, preferential attachment
References
@article{siu2025,
author = {Siu, Chunyin},
title = {The topological behavior of preferential attachment graphs},
journal = {SIAM J. Appl. Algebra Geom.},
volume = {9},
number = {2},
year = {2025},
pages = {432--455},
doi = {10.1137/24M1693179},
eprint = {2406.17619},
archivePrefix = {arXiv},
}
@article{siu2025expected,
author = {Siu, Chunyin and Samorodnitsky, Gennady and Yu, Christina Lee and He, Rongyi},
title = {The asymptotics of the expected {B}etti numbers of preferential attachment clique complexes},
journal = {Adv. in Appl. Probab.},
volume = {57},
number = {3},
year = {2025},
pages = {940--968},
doi = {10.1017/apr.2024.66},
eprint = {2305.11259},
archivePrefix = {arXiv},
}
@misc{aim-preferential-attachment-betti-limit,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Limiting Betti-number distributions in preferential-attachment networks}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/529-preferential-attachment-betti-limit.md},
note = {Entry 529 at commit 24edaad, 2026-10-15},
}
Resolution claims
We study the finite clique complexes of sequential affine preferential-attachment graphs. For every $q\ge2$, $m\ge2q$ and $\delta>-m$ with $x=(m+\delta)/(2m+\delta)<1/(2q)$, the $q$th rational Betti number, divided by its expectation, converges to a nondegenerate random variable. We identify its law as a normalized sum of products of attachment weights over induced octahedral subgraphs in an explicit independent-Beta construction. The limit is positive …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Needs verification → Solution claimed | — | Recorded here: AIM @ 24edaad, paper/main.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00824, "Limiting Betti-number distributions in preferential-attachment networks", clopen.solutions.