Connectivity when the last isolated point disappears in a polytope
Fix $d \ge 3$ and a compact convex polytope $A \subset \mathbb{R}^d$ with nonempty interior, and let $X_1, X_2, \dots$ be independent points uniformly distributed in $A$. For $n \ge 2$ let $G_n(r)$ be the graph on $\{X_1, \dots, X_n\}$ joining two vertices when their Euclidean distance is at most $r$, and put $$L_n = \max_{1 \le i \le n} \min_{j \ne i} \|X_i - X_j\|, \qquad M_n = \inf\{r \ge 0 : G_n(r) \text{ is connected}\}.$$ Thus $L_n$ is the radius at which the last isolated vertex disappears, and $L_n \le M_n$. Penrose, Yang and Higgs proved that $n L_n^d / \log n$ and $n M_n^d / \log n$ converge almost surely to the same limit, determined by the dimensions and angular volumes of the faces of $A$. Exact equality $L_n = M_n$ with probability tending to one was known for the cube $[0,1]^d$ (Penrose), and Penrose and Yang proved it for compact domains with $C^2$ boundary in every dimension $d \ge 2$ and for convex polygons.
Problem. Is it true, for every $d \ge 3$ and every such polytope $A$, that $$\lim_{n \to \infty} \mathbb{P}\{L_n = M_n\} = 1?$$
Source: Penrose, Yang and Higgs (2024), Remark 2.9, who report that their simulations suggest L_n = M_n for large n but do not prove it for general polytopes. Stated by AIM — Open Applied Problems for uniform samples in dimension d ≥ 3.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO, MG
- Keywords
- AIM Open Applied Problems, connectivity threshold, convex polytopes, random geometric graphs
References
@article{penrose2024polytope,
author = {Penrose, Mathew D. and Yang, Xiaochuan and Higgs, Frankie},
title = {Largest nearest-neighbour link and connectivity threshold in a polytopal random sample},
journal = {J. Appl. Comput. Topol.},
volume = {8},
number = {6},
year = {2024},
pages = {1723--1750},
doi = {10.1007/s41468-023-00154-5},
eprint = {2301.02506},
archivePrefix = {arXiv},
}
@article{penrose2025fluctuations,
author = {Penrose, Mathew D. and Yang, Xiaochuan},
title = {Fluctuations of the connectivity threshold and largest nearest-neighbour link},
journal = {Ann. Appl. Probab.},
volume = {35},
number = {6},
year = {2025},
pages = {3906--3941},
doi = {10.1214/25-AAP2210},
eprint = {2406.00647},
archivePrefix = {arXiv},
}
@book{penrose2003,
author = {Penrose, Mathew},
title = {Random Geometric Graphs},
series = {Oxford Studies in Probability},
volume = {5},
publisher = {Oxford University Press},
address = {Oxford},
year = {2003},
doi = {10.1093/acprof:oso/9780198506263.001.0001},
}
@misc{aim-polytopal-connectivity-last-isolated-point,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Connectivity when the last isolated point disappears in a polytope}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/647-polytopal-connectivity-last-isolated-point.md},
note = {Entry 647 at commit 24edaad, 2026-10-15},
}
Resolution claims
Let $X_1,\ldots,X_n$ be independent uniform points in a fixed compact convex polytope $A\subset\R^d$ with nonempty interior, where $d\geq3$. Let $L_n$ be the largest nearest-neighbour distance and let $M_n$ be the connectivity radius of their Euclidean random geometric graph. We prove that $\Pp(L_n=M_n)\to1$. The argument retains the contribution of every face at a deterministic radius slightly below the leading connectivity scale. …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Needs verification → Solution claimed | — | Recorded here: AIM @ 24edaad, paper/connectivity-polytope.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00822, "Connectivity when the last isolated point disappears in a polytope", clopen.solutions.