The Last Isolated Vertex in Random-Order Uncovering of Cycles and Their Powers: Exact Enumeration and Weibull Limits
Abstract
Let the vertices of a graph be revealed one at a time in a uniformly random order, and let the last-isolation time be the last time at which the induced graph on the revealed vertices contains an isolated vertex. For the cycle C_n, write K_n for the number of vertices still unrevealed at this time. We obtain an exact finite-n tail formula for K_n in terms of Stirling numbers of the second kind, together with a compact bivariate generating function. The enumeration comes from reversing the process. An isolated revealed vertex then corresponds to the cyclic pattern 101, but the tail event requires this pattern to be absent from every earlier prefix, not merely from the final set. This prefix condition forces the final one-blocks to be separated by zero-gaps of length at least two and forces the reveal order inside each one-block to be peakless. Since a block of size m has 2^{m-1} peakless orders, summing over block sizes produces the Stirling numbers. We also prove K_n/sqrt(n) -> R, with P(R>x)=e^{-x^2}, and, for every fixed d>=1, K_{n,d}/n^{1-1/(2d)} -> W_d, with P(W_d>x)=e^{-x^{2d}}. Uniform stretched-exponential tail bounds imply convergence of all fixed positive moments. Thus the ordinary cycle has a Rayleigh limit, while its fixed powers give a Weibull family with shape parameter 2d.
Related
- Enumeration of small vertex-transitive directed strongly regular graphs
- Precise large deviations for the elephant random walk with Weibull-type and lognormal-type random step sizes
- Formally Certifying the Vertex Set of a Polyhedron Faster than Informal Enumeration
- A Pittel-type limit law for the largest component of random d-uniform hypergraphs: enumeration and excursions
- Approximating Distributions on Vertex Degrees in Random Hypergraphs via Stein's Method
BibTeX
@misc{kleiner2026last,
title = {{The Last Isolated Vertex in Random-Order Uncovering of Cycles and Their Powers: Exact Enumeration and Weibull Limits}},
author = {Igor Kleiner},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29488},
eprint = {2609.29488},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29488},
}
RIS
TY - UNPB
TI - The Last Isolated Vertex in Random-Order Uncovering of Cycles and Their Powers: Exact Enumeration and Weibull Limits
AU - Igor Kleiner
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.29488
UR - https://arxiv.org/abs/2609.29488
AB - Let the vertices of a graph be revealed one at a time in a uniformly random order, and let the last-isolation time be the last time at which the induced graph on the revealed vertices contains an isolated vertex. For the cycle C_n, write K_n for the number of vertices still unrevealed at this time. We obtain an exact finite-n tail formula for K_n in terms of Stirling numbers of the second kind, together with a compact bivariate generating function. The enumeration comes from reversing the process. An isolated revealed vertex then corresponds to the cyclic pattern 101, but the tail event requires this pattern to be absent from every earlier prefix, not merely from the final set. This prefix condition forces the final one-blocks to be separated by zero-gaps of length at least two and forces the reveal order inside each one-block to be peakless. Since a block of size m has 2^{m-1} peakless orders, summing over block sizes produces the Stirling numbers. We also prove K_n/sqrt(n) -> R, with P(R>x)=e^{-x^2}, and, for every fixed d>=1, K_{n,d}/n^{1-1/(2d)} -> W_d, with P(W_d>x)=e^{-x^{2d}}. Uniform stretched-exponential tail bounds imply convergence of all fixed positive moments. Thus the ordinary cycle has a Rayleigh limit, while its fixed powers give a Weibull family with shape parameter 2d.
ER -