A limiting law for maximal persistence in random clique complexes
Give the edges $e$ of the complete graph on $n$ vertices independent labels $U_e$, uniform on $[0, 1]$, and let $X_n(p)$ be the clique complex of the graph of edges with $U_e \le p$, a filtration as $p$ runs over $[0, 1]$. Fix $k \ge 1$. Over the positive-length intervals $[b, d)$ in the degree-$k$ barcode of its persistent homology over $\mathbb{Q}$, let $M_k(n) = \max d/b$, with $M_k(n) = 0$ if there are none, and put $$f_k(n) = n^{1/[k(k+1)]} (\log n)^{1/(k+1)}.$$ Ababneh and Kahle proved that for every function $\omega(n) \to \infty$, with probability tending to one, $$\frac{n^{1/[k(k+1)]}}{\omega(n)} \le M_k(n) \le f_k(n)\, \omega(n),$$ so that $\log M_k(n) / \log n \to 1/[k(k+1)]$ in probability. The upper bound combines Kahle's sharp threshold for the vanishing of rational homology of random clique complexes with Newman's result that the complex collapses to dimension at most $k - 1$ when $p \ll n^{-1/k}$; the lower bound comes from persistent cycles shaped like boundaries of cross-polytopes and holds over any field.
Problem. With $k$ fixed, is there a probability distribution $\mu_k$ on $\mathbb{R}$ and a constant $\lambda_k > 0$ such that $$\frac{M_k(n)}{f_k(n)} \xrightarrow{\mathrm{d}} \mu_k \quad (n \to \infty) \qquad \text{and} \qquad \mu_k([\lambda_k, \infty)) = 1?$$
Source: Ababneh and Kahle (2024), Conjecture 5.2.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- AT, CO
- Keywords
- AIM Open Applied Problems, persistent homology, random clique complexes
References
@article{ababneh2024,
author = {Ababneh, Ayat and Kahle, Matthew},
title = {Maximal persistence in random clique complexes},
journal = {J. Appl. Comput. Topol.},
volume = {8},
number = {6},
year = {2024},
pages = {1449--1463},
doi = {10.1007/s41468-023-00131-y},
eprint = {2209.05713},
archivePrefix = {arXiv},
}
@article{kahle2014,
author = {Kahle, Matthew},
title = {Sharp vanishing thresholds for cohomology of random flag complexes},
journal = {Ann. of Math. (2)},
volume = {179},
number = {3},
year = {2014},
pages = {1085--1107},
doi = {10.4007/annals.2014.179.3.5},
eprint = {1207.0149},
archivePrefix = {arXiv},
}
@misc{aim-random-clique-maximal-persistence-law,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{A limiting law for maximal persistence in random clique complexes}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/638-random-clique-maximal-persistence-law.md},
note = {Entry 638 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00895, "A limiting law for maximal persistence in random clique complexes", clopen.solutions.