betaFeedback

WorksMathematics

The number of cycles in a random 2-factor of a random regular graph

Abstract

We study the number of cycles XX in a uniformly random 2-factor FF of a random dd-regular graph on nn vertices (in the pairing model) for any fixed d≥3d\ge 3. When the pairing PP and the 2-factor F⊆PF\subseteq P are chosen uniformly at random together, the probability generating function of XX is Γ(n+u2)Γ(12)/(Γ(n+12)Γ(u2))Γ(n+\tfrac u2)Γ(\tfrac12)/\bigl(Γ(n+\tfrac12)Γ(\tfrac u2)\bigr), which does not depend on dd. Consequently, XX has mean 12log⁡n+O(1)\tfrac12\log n+O(1) and variance 12log⁡n+O(1)\tfrac12\log n+O(1), satisfies a central limit theorem, and equals 11 (so that FF is a Hamilton cycle) with probability Θ(n−1/2)Θ(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.

Introduction

A 22-factor of a graph is a spanning 22-regular subgraph: a disjoint union of cycles covering every vertex. In random regular graphs, 22-factors play a special algorithmic role as “almost Hamilton cycles.” The classical route of Frieze, Jerrum, Molloy, Robinson, and Wormald [7] to generating Hamilton cycles in a random dd-regular graph G(n,d)G(n,d) is to sample near-uniform 22-factors repeatedly (via Tutte’s reduction of 22-factors to perfect matchings [19] and a matching algorithm) until a Hamiltonian one appears; their counting argument shows that the number of 22-factors exceeds the number of Hamilton cycles by at most a polynomial factor with high probability, so polynomially many resamplings suffice. Structurally, random regular graphs contain 22-factors with high probability [17], admit 11-factorizations with high probability [16], and in fact decompose with high probability into Hamilton cycles and at most one perfect matching [15]; the contiguity toolbox behind such results is surveyed in [9, 12, 20]. Recently, the cycle structure of random cycle-factors has attracted renewed attention: Christoph, Draganić, Girão, Hurley, Michel, and Müyësser [4] proved that a uniformly random cycle-factor of an arbitrary dd-regular digraph has Θ((nlog⁡d)/d)\Theta((n\log d)/d) cycles in expectation, and Kahn, Lubetzky, and Wormald [13] studied kk-cycle factors of random cubic graphs via renewal theory.

Despite this extensive literature, a natural question appears to have remained unanswered: how many cycles does a uniformly random 2-factor of a random regular graph have? While the counting argument of [7] bounds the ratio of the numbers of 2-factors and Hamilton cycles by a polynomial in nn, it does not determine the typical number of cycles. In this paper, we settle the question exactly for a uniformly random pair (P,F)(P,F) consisting of a pairing PP and a 2-factor F⊆PF\subseteq P, for every nn and every d≥3d\ge3 simultaneously, and find that the distribution of the cycle count does not depend on dd.

Throughout, PP is a pairing of nn vertices of degree d≥3d\ge3, GG is its multigraph (§ 2), F⊆PF\subseteq P is a 2-factor, and X=X(F)X=X(F) is the number of cycles of FF. Unless GG is fixed, the pair (P,F)(P,F) is uniform over all pairs, and E\mathbb{E} and P\mathbb{P} refer to that probability space.

Our first result is that the distribution of XX is explicit and does not depend on dd (Theorem 3.3): for every d≥3d\ge3,

EuX=Γ(n+u2)Γ(12)Γ(n+12)Γ(u2),equivalentlyX=d1+∑j=1n−1Bj,\mathbb{E}u^X=\frac{\Gamma\left(n+\frac{u}{2}\right)\Gamma\left(\frac{1}{2}\right)}{\Gamma\left(n+\frac{1}{2}\right)\Gamma\left(\frac{u}{2}\right)},\qquad\text{equivalently}\qquad X\mathrel{\stackrel{d}{=}}1+\sum_{j=1}^{n-1}B_j,

with Bj∼Bernoulli⁡(12j+1)B_j\sim\operatorname{Bernoulli}\left(\frac{1}{2j+1}\right) independent. Hence EX=12log⁡n+γ2+log⁡2+o(1)\mathbb{E}X=\frac{1}{2}\log n+\frac{\gamma}{2}+\log2+o(1), Var⁡X=12log⁡n+O(1)\operatorname{Var}X=\frac{1}{2}\log n+O(1), and (X−12log⁡n)/12log⁡n⇒N(0,1)(X-\frac{1}{2}\log n)/\sqrt{\frac{1}{2}\log n}\Rightarrow N(0,1) (Corollary 3.4); this is the analogue for 2-factors of the Feller coupling and of Goncharov’s theorem for the cycles of a random permutation [2, 8]. If FF is required to have girth at least 3, which is automatic when GG is simple, the mean shifts by −34-\frac{3}{4} and the variance and limiting distribution are unchanged (Theorem 4.1). In particular (Corollary 4.2), for every d≥3d\ge3,

P(X=1)=12πn(1+o(1)),P(X′=1)=πe3/42n−1/2(1+o(1)),\mathbb{P}(X=1)=\frac{1}{2}\sqrt{\frac{\pi}{n}}(1+o(1)),\qquad\mathbb{P}(X'=1)=\frac{\sqrt{\pi}e^{3/4}}{2}n^{-1/2}(1+o(1)),

where X′X' is the cycle count under the girth restriction: one 2-factor in Θ(n)\Theta(\sqrt{n}) is a Hamilton cycle.

Second, with Z(u,P)=∑FuX(F)Z(u,P)=\sum_F u^{X(F)} denoting the generating polynomial of the 2-factors of PP by number of cycles, Theorem 6.1 gives ∑PZ(u,P)2\sum_P Z(u,P)^2 as an explicit finite double sum for all nn, dd, and uu. Proposition 6.2 (proved in Appendix § 9) shows that EZ(u)2/(EZ(u))2→C(u)\mathbb{E}Z(u)^2/(\mathbb{E}Z(u))^2\to C(u) uniformly on a complex disk about u=1u=1, with C(u)C(u) given in (5); C(1)C(1) is Robalėwska’s constant for 2-factors [17] and C(0+)C(0^+) is the Robinson–Wormald constant for Hamilton cycles [18].

Third, the second moment and small subgraph conditioning [12, 20] transfer these results from the uniform pair to a fixed graph. Let GG be a uniformly random simple dd-regular graph and FF a uniformly random 2-factor of GG, and write μn=12log⁡n+γ2+log⁡2−34\mu_n = \frac{1}{2}\log n + \frac{\gamma}{2} + \log2 - \frac{3}{4} and σn=12log⁡n\sigma_n = \sqrt{\frac{1}{2}\log n}. Then n P(F is a Hamilton cycle∣G)\sqrt{n}\,\mathbb{P}(F\text{ is a Hamilton cycle}\mid G) converges in distribution to a strictly positive, almost surely finite random variable (Proposition 7.1), so the expected number of resamplings in the scheme of [7] is Θp(n)\Theta_p(\sqrt{n}); E[X∣G]−μn\mathbb{E}[X\mid G]-\mu_n converges in distribution to an explicit almost surely finite random variable (Theorem 7.4); the conditional distribution of (X−μn)/σn(X-\mu_n)/\sigma_n given GG converges weakly to N(0,1)N(0,1) in probability (Theorem 7.5); and Var⁡(X∣G)=σn2(1+op(1))\operatorname{Var}(X\mid G)=\sigma_n^2(1+o_p(1)) (Proposition 7.6).

Appendix B compares these formulas with exhaustive enumeration for small nn (for d=3d=3, by listing all perfect-matching complements up to n=80n=80) and, for nn up to 10610^6, with 2-factors produced by the Karp–Sipser algorithm finished by Edmonds’ blossom algorithm [14, 5].

Pairings, 2-factors, and the probability space

Let d≥3d\ge3 be fixed, and let dndn be even. In the pairing model [3, 20], each vertex v∈[n]v\in[n] owns dd points, and a pairing PP is a perfect matching of the dndn points; contracting the points of each vertex projects PP to a dd-regular multigraph. We write

M(2m)=(2m)!m!2mM(2m)=\frac{(2m)!}{m!2^m}

for the number of perfect matchings on 2m2m points.

A 2-factor of the pairing PP is a subset F⊆PF\subseteq P of pairs such that every vertex has exactly two of its points covered by FF. Projected to the multigraph, FF is a spanning 2-regular sub-multigraph: a disjoint union of cycles, where a pair joining two points of the same vertex is a loop (a cycle of length 1) and two pairs joining the same two vertices form a cycle of length 2. Let Zc(P)Z_c(P) denote the number of 2-factors of PP with exactly cc cycles, and let Zc≥3(P)Z_c^{\ge3}(P) count only those of girth at least 3 (no loops, no repeated edges); if the multigraph is simple, all its 2-factors have girth at least 3 automatically. Note that Z1=Z1≥3Z_1=Z_1^{\ge3} counts Hamilton cycles (for n≥3n\ge3).

Let Ωn,d\Omega_{n,d} denote the set of pairs (P,F)(P,F) in which PP is a pairing and F⊆PF\subseteq P is a 2-factor, equipped with the uniform probability P\mathbb{P}. Write Z(P)=∑cZc(P)Z(P)=\sum_c Z_c(P) for the number of 2-factors of PP and

Z(u)=Z(u,P)=∑cZc(P)uc=∑FuX(F)Z(u)=Z(u,P)=\sum_c Z_c(P)u^c=\sum_F u^{X(F)}

for the generating polynomial of the 2-factors of PP by number of cycles, the sum running over the 2-factors FF of PP. Since every 2-factor extends to exactly M((d−2)n)M((d-2)n) full pairings, the marginal distribution of PP under P\mathbb{P} assigns probability proportional to Z(P)Z(P) to each pairing, and the cycle count satisfies P(X=c)=EZc/EZ\mathbb{P}(X=c)=\mathbb{E}Z_c/\mathbb{E}Z, where here and throughout E\mathbb{E} applied to a function of PP alone denotes expectation over a uniformly random pairing PP. Unless we condition on GG, statements about XX refer to this uniform pair. Results for a fixed graph concern the conditional distribution of XX given GG: they are limit theorems, as n→∞n\to\infty, for the random variables P(X=1∣G)\mathbb{P}(X=1\mid G), E[X∣G]\mathbb{E}[X\mid G], and Var⁡(X∣G)\operatorname{Var}(X\mid G), which are functions of GG, and for the conditional distribution of XX given GG, which converges in probability.

Throughout, we use L(x):=log⁡11−x=∑k≥1xkkL(x):=\log\frac{1}{1-x}=\sum_{k\geq1}\frac{x^k}{k}.

The exact distribution of the cycle count

Theorem 3.1. For all nn, d≥3d\geq3, and c≥1c\geq1,

∑PZc(P)=n![xn]1c!(L(x)2)c(d(d−1))nM((d−2)n),\sum_{P} Z_c(P)=n![x^n]\frac{1}{c!}\left(\frac{L(x)}{2}\right)^c(d(d-1))^n M((d-2)n),

where the sum runs over all M(dn)M(dn) pairings. Consequently,

EZc=n![xn](L/2)cc!(d(d−1))nM((d−2)n)M(dn).\mathbb{E}Z_c=n![x^n]\frac{(L/2)^c}{c!}(d(d-1))^n\frac{M((d-2)n)}{M(dn)}.

The same holds for Zc≥3Z_c^{\geq3} with L(x)/2L(x)/2 replaced by

L≥3(x)=L(x)2−x2−x24.L_{\geq3}(x)=\frac{L(x)}{2}-\frac{x}{2}-\frac{x^2}{4}.

References

  1. [1]M. Anastos and A. Frieze, Finding maximum matchings in random regular graphs in linear expected time, Random Structures Algorithms 58 (2021), 390–429.DOI
  2. [2]R. Arratia, A. D. Barbour, and S. Tavaré, Logarithmic combinatorial structures: a probabilistic approach, EMS Monogr. Math., European Mathematical Society, Zürich, 2003.DOI
  3. [3]B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin. 1 (1980), 311–316.DOI
  4. [4]M. Christoph, N. Draganić, A. Girão, E. Hurley, L. Michel, and A. Müyesser, Cycle-factors of regular graphs via entropy, in Proceedings of FOCS 2025; arXiv:2507.19417.arxiv.org/abs/2507.19417
  5. [5]J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965), 449–467.
  6. [6]P. Flajolet and R. Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009.
  7. [7]A. Frieze, M. Jerrum, M. Molloy, R. Robinson, and N. Wormald, Generating and counting Hamilton cycles in random regular graphs, J. Algorithms 21 (1996), 176–198.DOI
  8. [8]V. Goncharov, Du domaine d’analyse combinatoire, Bull. Acad. Sci. USSR Ser. Mat. (Izv. Akad. Nauk SSSR) 8 (1944), 3–48; Amer. Math. Soc. Transl. (2) 19 (1962), 1–46.
  9. [9]C. Greenhill, S. Janson, J. H. Kim, and N. C. Wormald, Permutation pseudographs and contiguity, Combin. Probab. Comput. 11 (2002), 273–298.DOI
  10. [10]A. A. Hagberg, D. A. Schult, and P. J. Swart, Exploring network structure, dynamics, and function using NetworkX, in Proceedings of the 7th Python in Science Conference, 2008, pp. 11–15.
  11. [11]H.-K. Hwang, On convergence rates in the central limit theorems for combinatorial structures, European J. Combin. 19 (1998), 329–343.DOI
  12. [12]S. Janson, Random regular graphs: asymptotic distributions and contiguity, Combin. Probab. Comput. 4 (1995), 369–405.DOI
  13. [13]J. Kahn, E. Lubetzky, and N. Wormald, Cycle factors and renewal theory, Comm. Pure Appl. Math. 70 (2017), 289–339.
  14. [14]R. M. Karp and M. Sipser, Maximum matchings in sparse random graphs, in Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, IEEE, 1981, pp. 364–375.DOI
  15. [15]J. H. Kim and N. C. Wormald, Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs, J. Combin. Theory Ser. B 81 (2001), 20–44.DOI
  16. [16]M. Molloy, H. D. Robalewska, R. W. Robinson, and N. C. Wormald, 1-factorizations of random regular graphs, Random Structures Algorithms 10 (1997), 305–321.doi.org/10.1002/(sici)1098-2418(199705)10:3<305::aid-rsa1>3.0.co;2-#
  17. [17]H. D. Robalewska, 2-factors in random regular graphs, J. Graph Theory 23 (1996), 215–224.doi.org/10.1002/(sici)1097-0118(199611)23:3<215::aid-jgt1>3.0.co;2-v
  18. [18]R. W. Robinson and N. C. Wormald, Almost all regular graphs are Hamiltonian, Random Structures Algorithms 5 (1994), 363–374.DOI
  19. [19]W. T. Tutte, A short proof of the factor theorem for finite graphs, Canad. J. Math. 6 (1954), 347–352.DOI
  20. [20]N. C. Wormald, Models of random regular graphs, in Surveys in Combinatorics, 1999, London Math. Soc. Lecture Note Ser., vol. 267, Cambridge Univ. Press, Cambridge, 1999, pp. 239–298.

Paper details

vlnc:W_dyry2vf2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Gemini 4 Argon (bare), Grok 4.6 (bare), Anthropic Claude (Fable 5.2)

View statement
Looking for related papers…
Contents