Topological complexity in the homogeneous medial regime for all sample sizes
Fix $p \in (0, 1)$. For every nonempty $\sigma \subseteq [n]$ choose independently a Bernoulli variable $\xi_\sigma$ with success probability $p$, and let $$X_n = \{\sigma \subseteq [n] : \sigma \ne \varnothing,\ \xi_\tau = 1 \text{ for every nonempty } \tau \subseteq \sigma\}.$$ This is the lower multiparameter model with every probability parameter equal to $p$, the homogeneous medial regime; vertices are sampled as well as higher-dimensional faces. For a path-connected space $Y$, $\operatorname{TC}(Y)$ denotes the reduced topological complexity: the least $k \ge 0$ such that $Y \times Y$ has an open cover by $k + 1$ sets, each admitting a continuous section of the endpoint map $Y^{[0,1]} \to Y \times Y$, $\gamma \mapsto (\gamma(0), \gamma(1))$. Farber proved, for $p = 1/2$, that $\operatorname{TC}(X_n) \le 4$ with probability tending to one, and suggested that $\operatorname{TC} = 2$. Barmak and Farber proved $\operatorname{TC} \le 2$ with probability tending to one in the medial regime, where the probability parameters lie in a fixed interval $[p_-, p_+]$ with $0 < p_- \le p_+ < 1$, and, in the homogeneous medial regime, that $\operatorname{TC}(X_n) = 2$ with probability tending to one as $n \to \infty$ along a set of positive integers of natural density one.
Problem. Is it true, for every fixed $p \in (0, 1)$, that $$\Pr\{\,|X_n| \text{ is path-connected and } \operatorname{TC}(|X_n|) = 2\,\} \longrightarrow 1 \qquad (n \to \infty),$$ with the limit taken over all positive integers $n$?
Source: Barmak and Farber (2026), Section 10, Question 2, after Farber (2024), Remark 8.2. Stated by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- AT — Algebraic Topology
- Secondary
- CO, PR
- Keywords
- AIM Open Applied Problems, random simplicial complexes, topological complexity
References
@misc{barmak2026,
author = {Barmak, Jonathan Ariel and Farber, Michael},
title = {Topology of medial regime random simplicial complexes},
year = {2026},
eprint = {2608.07969},
archivePrefix = {arXiv},
}
@article{farber2024,
author = {Farber, Michael},
title = {Large simplicial complexes: universality, randomness, and ampleness},
journal = {J. Appl. Comput. Topol.},
volume = {8},
number = {6},
year = {2024},
pages = {1551--1574},
doi = {10.1007/s41468-023-00134-9},
eprint = {2301.07404},
archivePrefix = {arXiv},
}
@misc{aim-medial-regime-topological-complexity,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Topological complexity in the homogeneous medial regime for all sample sizes}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/644-medial-regime-topological-complexity.md},
note = {Entry 644 at commit 24edaad, 2026-10-15},
}
Resolution claims
In the lower multiparameter model of random simplicial complexes, a simplex is retained when all its nonempty subfaces pass independent Bernoulli trials. We prove that, when every trial has the same fixed probability in $(0,1)$, the resulting complex is path-connected and has reduced topological complexity two with probability tending to one along all ambient sample sizes. Thus three continuous local …
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-00811, "Topological complexity in the homogeneous medial regime for all sample sizes", clopen.solutions.