Vanishing threshold for first path homology of a random digraph
Let $G_n$ be the random digraph on $[n]$ in which each ordered pair $(i, j)$, $i \ne j$, is an edge independently with probability $p_n = n^\alpha$; reciprocal edges are allowed. Over $\mathbb{Q}$, let $\Lambda_k$ be the vector space with basis all vertex sequences $[v_0, \dots, v_k]$, repetitions allowed, with the boundary $$\partial [v_0, \dots, v_k] = \sum_{i=0}^{k} (-1)^i [v_0, \dots, \widehat{v_i}, \dots, v_k],$$ in which no term with repeated consecutive vertices is discarded (the non-regular convention). Let $A_k \subseteq \Lambda_k$ be spanned by the sequences whose successive ordered pairs are edges of $G_n$, put $\Omega_0 = A_0$ and $\Omega_k = A_k \cap \partial^{-1}(A_{k-1})$ for $k \ge 1$, and $$\beta_1^{\mathrm{nr}}(G_n) = \dim_{\mathbb{Q}} \frac{\ker(\partial : \Omega_1 \to \Omega_0)}{\partial \Omega_2},$$ the rank of the integral non-regular first path homology. Chaplin proved that $\beta_1^{\mathrm{nr}}(G_n) = 0$ with probability tending to one if $\alpha < -1$ or $\alpha > -1/3$, and $\beta_1^{\mathrm{nr}}(G_n) > 0$ with probability tending to one if $-1 < \alpha < -2/3$.
Problem. Is it true that, for every fixed $-2/3 < \alpha \le 0$, $$\mathbb{P}\{\beta_1^{\mathrm{nr}}(G_n) = 0\} \longrightarrow 1 \qquad (n \to \infty)?$$
Source: Chaplin (2024), Conjecture B.1, for non-regular and regular path homology. Stated by AIM — Open Applied Problems for non-regular path homology over ℚ.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- AT — Algebraic Topology
- Secondary
- CO, PR
- Keywords
- AIM Open Applied Problems, path homology, random directed graphs
References
@article{chaplin2024,
author = {Chaplin, Thomas},
title = {First {B}etti number of the path homology of random directed graphs},
journal = {J. Appl. Comput. Topol.},
volume = {8},
number = {6},
year = {2024},
pages = {1503--1549},
doi = {10.1007/s41468-022-00108-3},
eprint = {2111.13493},
archivePrefix = {arXiv},
}
@misc{aim-random-digraph-path-homology-vanishing,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Vanishing threshold for first path homology of a random digraph}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/649-random-digraph-path-homology-vanishing.md},
note = {Entry 649 at commit 24edaad, 2026-10-15},
}
Resolution claims
Let $G(n,p)$ be the loop-free random digraph in which every ordered edge is present independently with probability $p$, with reciprocal edges permitted. We prove that its first non-regular path homology over $\Q$ vanishes with probability tending to one if $n^2p^3/\log^4(2n)\to\infty$. Consequently, vanishing holds for $p=n^\alpha$ for every fixed $-2/3<\alpha\leq0$, as conjectured by Chaplin. The proof uses only boundaries of directed …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Needs verification → Solution claimed | — | Recorded here: AIM @ 24edaad, paper/path_homology_vanishing.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00828, "Vanishing threshold for first path homology of a random digraph", clopen.solutions.