The number of cycles in a random 2-factor of a random regular graph
We study the number of cycles $X$ in a uniformly random 2-factor $F$ of a random $d$-regular graph on $n$ vertices (in the pairing model) for any fixed $d\ge 3$. When the pairing $P$ and the 2-factor $F\subseteq P$ are chosen uniformly at random together, the probability generating function of $X$ is $Γ(n+\tfrac u2)Γ(\tfrac12)/\bigl(Γ(n+\tfrac12)Γ(\tfrac u2)\bigr)$, which does not depend on $d$. Consequently, $X$ has mean $\tfrac12\log n+O(1)$ and variance $\tfrac12\log n+O(1)$, satisfies a central limit theorem, and equals $1$ (so that $F$ is a Hamilton cycle) with probability $Θ(n^{-1/2})$. Using an exact formula for the second moment of the cycle generating polynomial together with small subgraph conditioning, we transfer these results to a uniformly random 2-factor of a fixed random regular graph.
Authors
- Katerina Adler (ORCID: https://orcid.org/0000-0001-5769-8284)
- Simi Haber
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.24574
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint