Introduction
A 2 2 2 -factor of a graph is a spanning 2 2 2 -regular subgraph: a disjoint union of cycles covering every vertex. In random regular graphs, 2 2 2 -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 d d d -regular graph G ( n , d ) G(n,d) G ( n , d ) is to sample near-uniform 2 2 2 -factors repeatedly (via Tutte’s reduction of 2 2 2 -factors to perfect matchings [19 ] and a matching algorithm) until a Hamiltonian one appears; their counting argument shows that the number of 2 2 2 -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 2 2 2 -factors with high probability [17 ] , admit 1 1 1 -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 d d d -regular digraph has Θ ( ( n log d ) / d ) \Theta((n\log d)/d) Θ (( n log d ) / d ) cycles in expectation, and Kahn, Lubetzky, and Wormald [13 ] studied k k k -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 n n n , 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) ( P , F ) consisting of a pairing P P P and a 2-factor F ⊆ P F\subseteq P F ⊆ P , for every n n n and every d ≥ 3 d\ge3 d ≥ 3 simultaneously, and find that the distribution of the cycle count does not depend on d d d .
Throughout, P P P is a pairing of n n n vertices of degree d ≥ 3 d\ge3 d ≥ 3 , G G G is its multigraph (§ 2 ), F ⊆ P F\subseteq P F ⊆ P is a 2-factor, and X = X ( F ) X=X(F) X = X ( F ) is the number of cycles of F F F . Unless G G G is fixed, the pair ( P , F ) (P,F) ( P , F ) is uniform over all pairs, and E \mathbb{E} E and P \mathbb{P} P refer to that probability space.
Our first result is that the distribution of X X X is explicit and does not depend on d d d (Theorem 3.3 ): for every d ≥ 3 d\ge3 d ≥ 3 ,
E u X = Γ ( n + u 2 ) Γ ( 1 2 ) Γ ( n + 1 2 ) Γ ( u 2 ) , equivalently X = d 1 + ∑ j = 1 n − 1 B j , \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, E u X = Γ ( n + 2 1 ) Γ ( 2 u ) Γ ( n + 2 u ) Γ ( 2 1 ) , equivalently X = d 1 + j = 1 ∑ n − 1 B j ,
with B j ∼ Bernoulli ( 1 2 j + 1 ) B_j\sim\operatorname{Bernoulli}\left(\frac{1}{2j+1}\right) B j ∼ Bernoulli ( 2 j + 1 1 ) independent. Hence E X = 1 2 log n + γ 2 + log 2 + o ( 1 ) \mathbb{E}X=\frac{1}{2}\log n+\frac{\gamma}{2}+\log2+o(1) E X = 2 1 log n + 2 γ + log 2 + o ( 1 ) , Var X = 1 2 log n + O ( 1 ) \operatorname{Var}X=\frac{1}{2}\log n+O(1) Var X = 2 1 log n + O ( 1 ) , and ( X − 1 2 log n ) / 1 2 log n ⇒ N ( 0 , 1 ) (X-\frac{1}{2}\log n)/\sqrt{\frac{1}{2}\log n}\Rightarrow N(0,1) ( X − 2 1 log n ) / 2 1 log n ⇒ 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 F F F is required to have girth at least 3, which is automatic when G G G is simple, the mean shifts by − 3 4 -\frac{3}{4} − 4 3 and the variance and limiting distribution are unchanged (Theorem 4.1 ). In particular (Corollary 4.2), for every d ≥ 3 d\ge3 d ≥ 3 ,
P ( X = 1 ) = 1 2 π n ( 1 + o ( 1 ) ) , P ( X ′ = 1 ) = π e 3 / 4 2 n − 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)), P ( X = 1 ) = 2 1 n π ( 1 + o ( 1 )) , P ( X ′ = 1 ) = 2 π e 3/4 n − 1/2 ( 1 + o ( 1 )) ,
where X ′ X' X ′ is the cycle count under the girth restriction: one 2-factor in Θ ( n ) \Theta(\sqrt{n}) Θ ( n ) is a Hamilton cycle.
Second, with Z ( u , P ) = ∑ F u X ( F ) Z(u,P)=\sum_F u^{X(F)} Z ( u , P ) = ∑ F u X ( F ) denoting the generating polynomial of the 2-factors of P P P by number of cycles, Theorem 6.1 gives ∑ P Z ( u , P ) 2 \sum_P Z(u,P)^2 ∑ P Z ( u , P ) 2 as an explicit finite double sum for all n n n , d d d , and u u u . Proposition 6.2 (proved in Appendix § 9 ) shows that E Z ( u ) 2 / ( E Z ( u ) ) 2 → C ( u ) \mathbb{E}Z(u)^2/(\mathbb{E}Z(u))^2\to C(u) E Z ( u ) 2 / ( E Z ( u ) ) 2 → C ( u ) uniformly on a complex disk about u = 1 u=1 u = 1 , with C ( u ) C(u) C ( u ) given in (5) ; C ( 1 ) C(1) C ( 1 ) is Robalėwska’s constant for 2-factors [17 ] and C ( 0 + ) 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 G G G be a uniformly random simple d d d -regular graph and F F F a uniformly random 2-factor of G G G , and write μ n = 1 2 log n + γ 2 + log 2 − 3 4 \mu_n = \frac{1}{2}\log n + \frac{\gamma}{2} + \log2 - \frac{3}{4} μ n = 2 1 log n + 2 γ + log 2 − 4 3 and σ n = 1 2 log n \sigma_n = \sqrt{\frac{1}{2}\log n} σ n = 2 1 log n . Then n P ( F is a Hamilton cycle ∣ G ) \sqrt{n}\,\mathbb{P}(F\text{ is a Hamilton cycle}\mid G) n P ( F is a Hamilton cycle ∣ 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}) Θ p ( n ) ; E [ X ∣ G ] − μ n \mathbb{E}[X\mid G]-\mu_n E [ X ∣ G ] − μ 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 ( X − μ n ) / σ n given G G G converges weakly to N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) in probability (Theorem 7.5 ); and Var ( X ∣ G ) = σ n 2 ( 1 + o p ( 1 ) ) \operatorname{Var}(X\mid G)=\sigma_n^2(1+o_p(1)) Var ( X ∣ G ) = σ n 2 ( 1 + o p ( 1 )) (Proposition 7.6 ).
Appendix B compares these formulas with exhaustive enumeration for small n n n (for d = 3 d=3 d = 3 , by listing all perfect-matching complements up to n = 80 n=80 n = 80 ) and, for n n n up to 10 6 10^6 1 0 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 ≥ 3 d\ge3 d ≥ 3 be fixed, and let d n dn d n be even. In the pairing model [3 , 20 ] , each vertex v ∈ [ n ] v\in[n] v ∈ [ n ] owns d d d points, and a pairing P P P is a perfect matching of the d n dn d n points; contracting the points of each vertex projects P P P to a d d d -regular multigraph. We write
M ( 2 m ) = ( 2 m ) ! m ! 2 m M(2m)=\frac{(2m)!}{m!2^m} M ( 2 m ) = m ! 2 m ( 2 m )!
for the number of perfect matchings on 2 m 2m 2 m points.
A 2-factor of the pairing P P P is a subset F ⊆ P F\subseteq P F ⊆ P of pairs such that every vertex has exactly two of its points covered by F F F . Projected to the multigraph, F F F 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 Z c ( P ) Z_c(P) Z c ( P ) denote the number of 2-factors of P P P with exactly c c c cycles, and let Z c ≥ 3 ( P ) Z_c^{\ge3}(P) Z c ≥ 3 ( 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 Z 1 = Z 1 ≥ 3 Z_1=Z_1^{\ge3} Z 1 = Z 1 ≥ 3 counts Hamilton cycles (for n ≥ 3 n\ge3 n ≥ 3 ).
Let Ω n , d \Omega_{n,d} Ω n , d denote the set of pairs ( P , F ) (P,F) ( P , F ) in which P P P is a pairing and F ⊆ P F\subseteq P F ⊆ P is a 2-factor, equipped with the uniform probability P \mathbb{P} P . Write Z ( P ) = ∑ c Z c ( P ) Z(P)=\sum_c Z_c(P) Z ( P ) = ∑ c Z c ( P ) for the number of 2-factors of P P P and
Z ( u ) = Z ( u , P ) = ∑ c Z c ( P ) u c = ∑ F u X ( F ) Z(u)=Z(u,P)=\sum_c Z_c(P)u^c=\sum_F u^{X(F)} Z ( u ) = Z ( u , P ) = c ∑ Z c ( P ) u c = F ∑ u X ( F )
for the generating polynomial of the 2-factors of P P P by number of cycles, the sum running over the 2-factors F F F of P P P . Since every 2-factor extends to exactly M ( ( d − 2 ) n ) M((d-2)n) M (( d − 2 ) n ) full pairings, the marginal distribution of P P P under P \mathbb{P} P assigns probability proportional to Z ( P ) Z(P) Z ( P ) to each pairing, and the cycle count satisfies P ( X = c ) = E Z c / E Z \mathbb{P}(X=c)=\mathbb{E}Z_c/\mathbb{E}Z P ( X = c ) = E Z c / E Z , where here and throughout E \mathbb{E} E applied to a function of P P P alone denotes expectation over a uniformly random pairing P P P . Unless we condition on G G G , statements about X X X refer to this uniform pair. Results for a fixed graph concern the conditional distribution of X X X given G G G : they are limit theorems, as n → ∞ n\to\infty n → ∞ , for the random variables P ( X = 1 ∣ G ) \mathbb{P}(X=1\mid G) P ( X = 1 ∣ G ) , E [ X ∣ G ] \mathbb{E}[X\mid G] E [ X ∣ G ] , and Var ( X ∣ G ) \operatorname{Var}(X\mid G) Var ( X ∣ G ) , which are functions of G G G , and for the conditional distribution of X X X given G G G , which converges in probability.
Throughout, we use L ( x ) : = log 1 1 − x = ∑ k ≥ 1 x k k L(x):=\log\frac{1}{1-x}=\sum_{k\geq1}\frac{x^k}{k} L ( x ) := log 1 − x 1 = ∑ k ≥ 1 k x k .
The exact distribution of the cycle count
Theorem 3.1. For all n n n , d ≥ 3 d\geq3 d ≥ 3 , and c ≥ 1 c\geq1 c ≥ 1 ,
∑ P Z c ( P ) = n ! [ x n ] 1 c ! ( L ( x ) 2 ) c ( d ( d − 1 ) ) n M ( ( 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), P ∑ Z c ( P ) = n ! [ x n ] c ! 1 ( 2 L ( x ) ) c ( d ( d − 1 ) ) n M (( d − 2 ) n ) , where the sum runs over all M ( d n ) M(dn) M ( d n ) pairings. Consequently,
E Z c = n ! [ x n ] ( L / 2 ) c c ! ( d ( d − 1 ) ) n M ( ( d − 2 ) n ) M ( d n ) . \mathbb{E}Z_c=n![x^n]\frac{(L/2)^c}{c!}(d(d-1))^n\frac{M((d-2)n)}{M(dn)}. E Z c = n ! [ x n ] c ! ( L /2 ) c ( d ( d − 1 ) ) n M ( d n ) M (( d − 2 ) n ) . The same holds for Z c ≥ 3 Z_c^{\geq3} Z c ≥ 3 with L ( x ) / 2 L(x)/2 L ( x ) /2 replaced by
L ≥ 3 ( x ) = L ( x ) 2 − x 2 − x 2 4 . L_{\geq3}(x)=\frac{L(x)}{2}-\frac{x}{2}-\frac{x^2}{4}. L ≥ 3 ( x ) = 2 L ( x ) − 2 x − 4 x 2 .
Proof. Both sides count incidences ( P , F ) (P,F) ( P , F ) where F F F has c c c cycles: a partial pairing F F F covering exactly two points per vertex extends to exactly M ( ( d − 2 ) n ) M((d-2)n) M (( d − 2 ) n ) full pairings, so it suffices to count partial pairings with c c c cycles.
Let a k a_k a k be the number of single-cycle partial pairings on a fixed set of k k k labelled vertices of degree d d d . For k = 1 k=1 k = 1 (a loop), we choose an unordered pair of the d d d points: a 1 = ( d 2 ) = d ( d − 1 ) 2 a_1=\binom{d}{2}=\frac{d(d-1)}{2} a 1 = ( 2 d ) = 2 d ( d − 1 ) . For k = 2 k=2 k = 2 (a double edge), we choose two points at each vertex and one of the two crosswise pairings: a 2 = 2 ( d 2 ) 2 = ( d ( d − 1 ) ) 2 2 a_2=2\binom{d}{2}^2=\frac{(d(d-1))^2}{2} a 2 = 2 ( 2 d ) 2 = 2 ( d ( d − 1 ) ) 2 . For k ≥ 3 k\geq3 k ≥ 3 , there are ( k − 1 ) ! / 2 (k-1)!/2 ( k − 1 )! /2 undirected cyclic orders, and along a fixed traversal, each vertex contributes an ordered choice of (entry point, exit point): a k = ( k − 1 ) ! 2 ( d ( d − 1 ) ) k a_k=\frac{(k-1)!}{2}(d(d-1))^k a k = 2 ( k − 1 )! ( d ( d − 1 ) ) k . In all cases, a k x k k ! = ( d ( d − 1 ) x ) k 2 k a_k\frac{x^k}{k!}=\frac{(d(d-1)x)^k}{2k} a k k ! x k = 2 k ( d ( d − 1 ) x ) k , so the exponential generating function of single cycles is 1 2 L ( d ( d − 1 ) x ) \frac{1}{2}L(d(d-1)x) 2 1 L ( d ( d − 1 ) x ) . By the exponential formula, the number of partial pairings with exactly c c c cycles on [ n ] [n] [ n ] is
n ! [ x n ] 1 c ! ( 1 2 L ( d ( d − 1 ) x ) ) c = ( d ( d − 1 ) ) n n ! [ x n ] ( L ( x ) / 2 ) c c ! . (1) n![x^n]\frac{1}{c!}\left(\frac{1}{2}L(d(d-1)x)\right)^c=(d(d-1))^n n![x^n]\frac{(L(x)/2)^c}{c!}. \tag*{(1)} n ! [ x n ] c ! 1 ( 2 1 L ( d ( d − 1 ) x ) ) c = ( d ( d − 1 ) ) n n ! [ x n ] c ! ( L ( x ) /2 ) c . (1)
Excluding k ∈ { 1 , 2 } k \in\{1,2\} k ∈ { 1 , 2 } removes the terms x / 2 x/2 x /2 and x 2 / 4 x^2/4 x 2 /4 from L / 2 L/2 L /2 , yielding the girth-≥ 3 \ge3 ≥ 3 statement. □ \square □
Corollary 3.2. For all n ≥ 1 n \ge1 n ≥ 1 and d ≥ 3 d \ge3 d ≥ 3 , we have E Z 1 = ( n − 1 ) ! 2 ( d ( d − 1 ) ) n M ( ( d − 2 ) n ) M ( d n ) \mathbb{E}Z_1 = \frac{(n-1)!}{2}(d(d-1))^n\frac{M((d-2)n)}{M(dn)} E Z 1 = 2 ( n − 1 )! ( d ( d − 1 ) ) n M ( d n ) M (( d − 2 ) n ) , which recovers the expected number of Hamilton cycles in [7 ] . Moreover, n ! [ x n ] ( L ( x ) / 2 ) 2 = ( n − 1 ) ! 4 H n − 1 n/2)^2 = \frac{(n-1)!}{4}H_{n-1} n ! [ x n ] ( L ( x ) /2 ) 2 = 4 ( n − 1 )! H n − 1 , where H m = ∑ k = 1 m 1 / k H_m = \sum_{k=1}^{m}1/k H m = ∑ k = 1 m 1/ k is the m m m -th harmonic number, and therefore E Z 2 / E Z 1 = 1 2 H n − 1 \mathbb{E}Z_2/\mathbb{E}Z_1 = \frac{1}{2}H_{n-1} E Z 2 / E Z 1 = 2 1 H n − 1 .
Proof. We have [ x n ] L = 1 / n [x^n]L=1/n [ x n ] L = 1/ n and [ x n ] L 2 = ∑ k = 1 n − 1 1 k ( n − k ) = 2 n H n − 1 [x^n]L^2=\sum_{k=1}^{n-1}\frac{1}{k(n-k)}=\frac{2}{n}H_{n-1} [ x n ] L 2 = ∑ k = 1 n − 1 k ( n − k ) 1 = n 2 H n − 1 . □ \square □
Theorem 3.3. For a uniform pair ( P , F ) (P,F) ( P , F ) and every d ≥ 3 d \ge3 d ≥ 3 ,
E u X = [ y n ] ( 1 − y ) − u / 2 [ y n ] ( 1 − y ) − 1 / 2 = Γ ( n + u / 2 ) Γ ( 1 / 2 ) Γ ( n + 1 / 2 ) Γ ( u / 2 ) = u ∏ j = 1 n − 1 u + 2 j 1 + 2 j . \mathbb{E}u^X = \frac{[y^n](1-y)^{-u/2}}{[y^n](1-y)^{-1/2}} = \frac{\Gamma(n+u/2)\Gamma(1/2)}{\Gamma(n+1/2)\Gamma(u/2)} = u\prod_{j=1}^{n-1}\frac{u+2j}{1+2j}. E u X = [ y n ] ( 1 − y ) − 1/2 [ y n ] ( 1 − y ) − u /2 = Γ ( n + 1/2 ) Γ ( u /2 ) Γ ( n + u /2 ) Γ ( 1/2 ) = u j = 1 ∏ n − 1 1 + 2 j u + 2 j . In particular, the distribution of X = X ( F ) X=X(F) X = X ( F ) does not depend on d d d , and
X = d 1 + ∑ j = 1 n − 1 B j , B j ∼ Bernoulli ( 1 2 j + 1 ) independent . X \mathrel{\mathop{=}^{d}} 1+\sum_{j=1}^{n-1}B_j,\qquad B_j\sim\operatorname{Bernoulli}\left(\frac{1}{2j+1}\right)\text{ independent}. X = d 1 + j = 1 ∑ n − 1 B j , B j ∼ Bernoulli ( 2 j + 1 1 ) independent .
Proof. Multiplying the identity of Theorem 3.1 by u c u^c u c and summing over c ≥ 1 c\ge1 c ≥ 1 , we obtain from ∑ c ≥ 0 ( u L ( x ) / 2 ) c c ! = e u L ( x ) / 2 = ( 1 − x ) − u / 2 \sum_{c\ge0}\frac{(uL(x)/2)^c}{c!}=e^{uL(x)/2}=(1-x)^{-u/2} ∑ c ≥ 0 c ! ( uL ( x ) /2 ) c = e uL ( x ) /2 = ( 1 − x ) − u /2 that
∑ c ≥ 1 u c ∑ P Z c ( P ) = n ! [ x n ] ( 1 − x ) − u / 2 ( d ( d − 1 ) ) n M ( ( d − 2 ) n ) . \sum_{c\ge1}u^c\sum_P Z_c(P)=n^{-u/2}(d(d-1))^nM((d-2)n). c ≥ 1 ∑ u c P ∑ Z c ( P ) = n ! [ x n ] ( 1 − x ) − u /2 ( d ( d − 1 ) ) n M (( d − 2 ) n ) .
Since E u X \mathbb{E}u^X E u X is the ratio of this sum to its value at u = 1 u=1 u = 1 , all factors depending on d d d cancel, which gives the first equality. The second equality follows from the binomial expansion
[ y n ] ( 1 − y ) − u / 2 = ( n + u / 2 − 1 n ) = Γ ( n + u / 2 ) Γ ( u / 2 ) n ! . [y^n](1-y)^{-u/2}=\binom{n+u/2-1}{n}=\frac{\Gamma(n+u/2)}{\Gamma(u/2)n!}. [ y n ] ( 1 − y ) − u /2 = ( n n + u /2 − 1 ) = Γ ( u /2 ) n ! Γ ( n + u /2 ) .
and the product form follows from Γ ( n + u / 2 ) / Γ ( u / 2 ) = ∏ j = 0 n − 1 ( j + u / 2 ) = 2 − n ∏ j = 1 n − 1 ( u + 2 j ) \Gamma(n+u/2)/\Gamma(u/2)=\prod_{j=0}^{n-1}(j+u/2)=2^{-n}\prod_{j=1}^{n-1}(u+2j) Γ ( n + u /2 ) /Γ ( u /2 ) = ∏ j = 0 n − 1 ( j + u /2 ) = 2 − n ∏ j = 1 n − 1 ( u + 2 j ) upon dividing by its value at u = 1 u=1 u = 1 . Finally, the prefactor u u u corresponds to the constant 1 1 1 , and each factor u + 2 j 1 + 2 j \frac{u+2j}{1+2j} 1 + 2 j u + 2 j is the probability generating function of an independent Bernoulli ( 1 2 j + 1 ) \left(\frac{1}{2j+1}\right) ( 2 j + 1 1 ) random variable. □ \square □
Corollary 3.4. For a uniform pair ( P , F ) (P,F) ( P , F ) and every d ≥ 3 d \ge3 d ≥ 3 , we have E X = H 2 n − 1 − 1 2 H n − 1 = 1 2 log n + γ 2 + log 2 + o ( 1 ) \mathbb{E}X=H_{2n-1}-\frac{1}{2}H_{n-1}=\frac{1}{2}\log n+\frac{\gamma}{2}+\log2+o(1) E X = H 2 n − 1 − 2 1 H n − 1 = 2 1 log n + 2 γ + log 2 + o ( 1 ) , Var X = 1 2 log n + O ( 1 ) \operatorname{Var}X=\frac{1}{2}\log n+O(1) Var X = 2 1 log n + O ( 1 ) , and
X − 1 2 log n 1 2 log n ⟹ N ( 0 , 1 ) . \frac{X-\frac{1}{2}\log n}{\sqrt{\frac{1}{2}\log n}}\Longrightarrow N(0,1). 2 1 log n X − 2 1 log n ⟹ N ( 0 , 1 ) .
Proof. The mean and variance follow immediately from the decomposition of X X X into independent Bernoulli variables in Theorem 3.3 , and the central limit theorem follows from Lindeberg’s condition, just as in Goncharov’s theorem for the number of cycles of a random permutation [2 , 8 ] .
Corollary 3.5. Fix d ≥ 3 d \ge3 d ≥ 3 and ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . Let
m n : = E X = H 2 n − 1 − 1 2 H n − 1 = 1 2 log n + γ 2 + log 2 + o ( 1 ) , m_n := \mathbb{E}X = H_{2n-1} - \frac{1}{2}H_{n-1} = \frac{1}{2}\log n + \frac{\gamma}{2} + \log2 + o(1), m n := E X = H 2 n − 1 − 2 1 H n − 1 = 2 1 log n + 2 γ + log 2 + o ( 1 ) , v n : = Var X = ∑ j = 1 n − 1 2 j ( 2 j + 1 ) 2 = 1 2 log n + O ( 1 ) v_n := \operatorname{Var} X = \sum_{j=1}^{n-1} \frac{2j}{(2j+1)^2} = \frac{1}{2}\log n + O(1) v n := Var X = j = 1 ∑ n − 1 ( 2 j + 1 ) 2 2 j = 2 1 log n + O ( 1 ) *be the exact pairing mean and variance from Corollary 3.4, so that m n = μ n p a i r + o ( 1 ) m_n = \mu_n^{\mathrm{pair}} + o(1) m n = μ n pair + o ( 1 ) and v n = σ n 2 + O ( 1 ) v_n = \sigma_n^2 + O(1) v n = σ n 2 + O ( 1 ) , where μ n p a i r = 1 2 log n + γ 2 + log 2 \mu_n^{\mathrm{pair}} = \frac{1}{2}\log n + \frac{\gamma}{2} + \log2 μ n pair = 2 1 log n + 2 γ + log 2 and σ n = 1 2 log n \sigma_n = \sqrt{\frac{1}{2}\log n} σ n = 2 1 log n . Then, uniformly for s ∈ C s \in\mathbb{C} s ∈ C with ∣ s ∣ ≤ ε |s| \le\varepsilon ∣ s ∣ ≤ ε , we have
E Z ( e s ) E Z ( 1 ) = exp ( m n s + 1 2 v n s 2 + O ( ∣ s ∣ 3 log n ) ) . (2) \frac{\mathbb{E}Z(e^s)}{\mathbb{E}Z(1)} = \exp\left(m_n s + \frac{1}{2}v_n s^2 + O(|s|^3 \log n)\right). \tag*{(2)} E Z ( 1 ) E Z ( e s ) = exp ( m n s + 2 1 v n s 2 + O ( ∣ s ∣ 3 log n ) ) . (2) In terms of the additive parameter t = u − 1 t = u-1 t = u − 1 , all coefficients beyond the linear term are O ( 1 ) O(1) O ( 1 ) :
E Z ( 1 + t ) E Z ( 1 ) = exp ( m n t − π 2 16 t 2 + O ( ∣ t ∣ 3 ) ) . \frac{\mathbb{E}Z(1+t)}{\mathbb{E}Z(1)} = \exp\left(m_n t - \frac{\pi^2}{16}t^2 + O(|t|^3)\right). E Z ( 1 ) E Z ( 1 + t ) = exp ( m n t − 16 π 2 t 2 + O ( ∣ t ∣ 3 ) ) . In particular, at u = e i t / σ n u=e^{it/\sigma_n} u = e i t / σ n the characteristic function of X X X for a uniform pair satisfies the Gaussian expansion of Hwang’s quasi-power theorem [11 ] .
Proof. Since every 2-factor extends to M ( ( d − 2 ) n ) M((d-2)n) M (( d − 2 ) n ) pairings, E Z ( u ) / E Z ( 1 ) = E u X = Γ ( n + u / 2 ) Γ ( 1 / 2 ) Γ ( n + 1 / 2 ) Γ ( u / 2 ) \mathbb{E}Z(u)/\mathbb{E}Z(1) = \mathbb{E}u^X = \frac{\Gamma(n+u/2)\Gamma(1/2)}{\Gamma(n+1/2)\Gamma(u/2)} E Z ( u ) / E Z ( 1 ) = E u X = Γ ( n + 1/2 ) Γ ( u /2 ) Γ ( n + u /2 ) Γ ( 1/2 ) by Theorem 3.3 . Equivalently, X = d 1 + ∑ j = 1 n − 1 B j X \overset{d}{=} 1+\sum_{j=1}^{n-1}B_j X = d 1 + ∑ j = 1 n − 1 B j with independent B j ∼ Bernoulli ( 1 / ( 2 j + 1 ) ) B_j \sim\operatorname{Bernoulli}(1/(2j+1)) B j ∼ Bernoulli ( 1/ ( 2 j + 1 )) , so the cumulant generating function in s = log u s=\log u s = log u is
log E e s X = s + ∑ j = 1 n − 1 log ( 1 − p j + p j e s ) , p j = 1 2 j + 1 . \log\mathbb{E}e^{sX} = s+\sum_{j=1}^{n-1}\log(1-p_j+p_j e^s), \qquad p_j=\frac{1}{2j+1}. log E e s X = s + j = 1 ∑ n − 1 log ( 1 − p j + p j e s ) , p j = 2 j + 1 1 .
For ∣ s ∣ ≤ ε |s|\le\varepsilon ∣ s ∣ ≤ ε , we have the uniform expansion log ( 1 − p j + p j e s ) = p j s + 1 2 p j ( 1 − p j ) s 2 + O ( p j ∣ s ∣ 3 ) \log(1-p_j+p_j e^s)=p_js+\frac{1}{2}p_j(1-p_j)s^2+O(p_j|s|^3) log ( 1 − p j + p j e s ) = p j s + 2 1 p j ( 1 − p j ) s 2 + O ( p j ∣ s ∣ 3 ) . Summing over 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 gives Eq. (2) , since E X = 1 + ∑ j p j = m n \mathbb{E}X=1+\sum_jp_j=m_n E X = 1 + ∑ j p j = m n , Var X = ∑ j p j ( 1 − p j ) = v n \operatorname{Var}X=\sum_jp_j(1-p_j)=v_n Var X = ∑ j p j ( 1 − p j ) = v n , and ∑ j < n p j = O ( log n ) \sum_{j<n}p_j=O(\log n) ∑ j < n p j = O ( log n ) (the third cumulant of X X X is ∑ j p j ( 1 − p j ) ( 1 − 2 p j ) ∼ 1 2 log n \sum_jp_j(1-p_j)(1-2p_j)\sim\frac{1}{2}\log n ∑ j p j ( 1 − p j ) ( 1 − 2 p j ) ∼ 2 1 log n ). In terms of t = u − 1 t=u-1 t = u − 1 , differentiating log E Z ( u ) \log\mathbb{E}Z(u) log E Z ( u ) twice at u = 1 u=1 u = 1 gives ∂ u u log E Z ( u ) ∣ u = 1 = 1 4 ψ ′ ( n + 1 2 ) − 1 4 ψ ′ ( 1 2 ) = − π 2 8 + O ( n − 1 ) \left.\partial_{uu}\log\mathbb{E}Z(u)\right|_{u=1}=\frac{1}{4}\psi'(n+\frac{1}{2})-\frac{1}{4}\psi'(\frac{1}{2})=-\frac{\pi^2}{8}+O(n^{-1}) ∂ uu log E Z ( u ) ∣ u = 1 = 4 1 ψ ′ ( n + 2 1 ) − 4 1 ψ ′ ( 2 1 ) = − 8 π 2 + O ( n − 1 ) because ψ ′ ( 1 / 2 ) = π 2 / 2 \psi'(1/2)=\pi^2/2 ψ ′ ( 1/2 ) = π 2 /2 , which yields the coefficient − π 2 / 16 -\pi^2/16 − π 2 /16 of t 2 t^2 t 2 .
Remark 3.6. The independence of d d d in Theorem 3.3 has a direct combinatorial explanation: once we specify which two of the d d d points at each vertex belong to the 2-factor, the remaining ( d − 2 ) n (d-2)n ( d − 2 ) n points can be paired in M ( ( d − 2 ) n ) M((d-2)n) M (( d − 2 ) n ) ways regardless of how the 2 n 2n 2 n chosen points are paired. Consequently, under the uniform distribution on pairs ( P , F ) (P,F) ( P , F ) , the induced factor F F F is a uniformly random pairing of 2 n 2n 2 n points with two points at each vertex, and its cycle structure is that of a random 2-regular multigraph on [ n ] [n] [ n ] .
Girth at least three, and the probability of a Hamilton cycle
A simple host graph has no loops or digons, so all of its 2-factors have girth at least 3. The girth-≥ 3 \ge3 ≥ 3 distribution below is therefore the one relevant to simple G ( n , d ) G(n,d) G ( n , d ) ; Lemma 5.3 makes this precise.
Theorem 4.1. Let X ′ X' X ′ be the number of cycles of F F F when ( P , F ) (P,F) ( P , F ) is uniform over the pairs in which F F F has girth at least 3. Then, uniformly for u u u in compact subsets of C ∖ { 0 , − 2 , − 4 , … } \mathbb{C} \setminus\{0,-2,-4,\ldots\} C ∖ { 0 , − 2 , − 4 , … } ,
E X ′ = [ y n ] e − u ( y / 2 + y 2 / 4 ) ( 1 − y ) − u / 2 [ y n ] e − ( y / 2 + y 2 / 4 ) ( 1 − y ) − 1 / 2 = e − 3 ( u − 1 ) 4 n u − 1 2 Γ ( 1 / 2 ) Γ ( u / 2 ) ( 1 + o ( 1 ) ) . \mathbb{E}X' = \frac{[y^n]e^{-u(y/2+y^2/4)}(1-y)^{-u/2}}{[y^n]e^{-(y/2+y^2/4)}(1-y)^{-1/2}} = e^{-\frac{3(u-1)}{4}}n^{\frac{u-1}{2}}\frac{\Gamma(1/2)}{\Gamma(u/2)}(1+o(1)). E X ′ = [ y n ] e − ( y /2 + y 2 /4 ) ( 1 − y ) − 1/2 [ y n ] e − u ( y /2 + y 2 /4 ) ( 1 − y ) − u /2 = e − 4 3 ( u − 1 ) n 2 u − 1 Γ ( u /2 ) Γ ( 1/2 ) ( 1 + o ( 1 )) . Consequently, E X ′ = 1 2 log n + γ 2 + log 2 − 3 4 + o ( 1 ) \mathbb{E}X' = \frac{1}{2}\log n + \frac{\gamma}{2} + \log2 - \frac{3}{4} + o(1) E X ′ = 2 1 log n + 2 γ + log 2 − 4 3 + o ( 1 ) , Var X ′ = 1 2 log n + O ( 1 ) \operatorname{Var} X' = \frac{1}{2}\log n + O(1) Var X ′ = 2 1 log n + O ( 1 ) , and X ′ X' X ′ satisfies the same central limit theorem as X X X .
Proof. The first equality follows from Theorem 3.1 summed against u c u^c u c , with e u L ≥ 3 ( x ) = e − u ( x / 2 + x 2 / 4 ) ( 1 − x ) − u / 2 e^{uL_{\geq3}(x)}=e^{-u(x/2+x^2/4)}(1-x)^{-u/2} e u L ≥ 3 ( x ) = e − u ( x /2 + x 2 /4 ) ( 1 − x ) − u /2 . Since e − u ( y / 2 + y 2 / 4 ) e^{-u(y/2+y^2/4)} e − u ( y /2 + y 2 /4 ) is entire, standard singularity analysis [6 Ch. VI] yields [ y n ] e − u ( y / 2 + y 2 / 4 ) ( 1 − y ) − u / 2 = e − 3 u / 4 n u / 2 − 1 / Γ ( u / 2 ) ( 1 + O ( 1 / n ) ) [y^n]e^{-u(y/2+y^2/4)}(1-y)^{-u/2}=e^{-3u/4}n^{u/2-1}/\Gamma(u/2)(1+O(1/n)) [ y n ] e − u ( y /2 + y 2 /4 ) ( 1 − y ) − u /2 = e − 3 u /4 n u /2 − 1 /Γ ( u /2 ) ( 1 + O ( 1/ n )) , uniformly on compact subsets of C ∖ { 0 , − 2 , − 4 , … } \mathbb{C} \setminus\{0,-2,-4,\ldots\} C ∖ { 0 , − 2 , − 4 , … } , and in particular on a complex neighbourhood of u = 1 u=1 u = 1 (multiplying the expansions of Corollary 3.5 by e − 3 ( u − 1 ) / 4 e^{-3(u-1)/4} e − 3 ( u − 1 ) /4 ). The moment asymptotics and the CLT then follow from the quasi-power theorem of Hwang [11 ] .
Corollary 4.2. For a uniform pair ( P , F ) (P,F) ( P , F ) ,
P ( X = 1 ) = 2 2 n − 1 n ! ( n − 1 ) ! ( 2 n ) ! = 1 2 π n ( 1 + o ( 1 ) ) , \mathbb{P}(X=1)=\frac{2^{2n-1}n!(n-1)!}{(2n)!}=\frac{1}{2}\sqrt{\frac{\pi}{n}}(1+o(1)), P ( X = 1 ) = ( 2 n )! 2 2 n − 1 n ! ( n − 1 )! = 2 1 n π ( 1 + o ( 1 )) , P ( X ′ = 1 ) = π e 3 / 4 2 n − 1 / 2 ( 1 + o ( 1 ) ) , \mathbb{P}(X'=1)=\frac{\sqrt{\pi}e^{3/4}}{2}n^{-1/2}(1+o(1)), P ( X ′ = 1 ) = 2 π e 3/4 n − 1/2 ( 1 + o ( 1 )) , for every d ≥ 3 d\geq3 d ≥ 3 . More generally, for each fixed c c c , P ( X ′ = c ) = π e 3 / 4 2 n λ c − 1 ( c − 1 ) ! ( 1 + o ( 1 ) ) \mathbb{P}(X'=c)=\frac{\sqrt{\pi}e^{3/4}}{2\sqrt{n}}\frac{\lambda^{c-1}}{(c-1)!}(1+o(1)) P ( X ′ = c ) = 2 n π e 3/4 ( c − 1 )! λ c − 1 ( 1 + o ( 1 )) with λ = 1 2 log n \lambda=\frac{1}{2}\log n λ = 2 1 log n .
Proof. By Theorem 3.3 , we have P ( X = 1 ) = ∏ j = 1 n − 1 2 j 2 j + 1 = 2 2 n − 1 n ! ( n − 1 ) ! ( 2 n ) ! \mathbb{P}(X=1)=\prod_{j=1}^{n-1}\frac{2j}{2j+1}=\frac{2^{2n-1}n!(n-1)!}{(2n)!} P ( X = 1 ) = ∏ j = 1 n − 1 2 j + 1 2 j = ( 2 n )! 2 2 n − 1 n ! ( n − 1 )! , and Stirling’s formula gives the asymptotic estimate. For X ′ X' X ′ , we have P ( X ′ = c ) = N c / ∑ c N c \mathbb{P}(X'=c)=N_c/\sum_c N_c P ( X ′ = c ) = N c / ∑ c N c , where N c = n ! [ x n ] L ≥ 3 ( x ) c / c ! N_c=n![x^n]L_{\geq3}(x)^c/c! N c = n ! [ x n ] L ≥ 3 ( x ) c / c ! ; singularity analysis yields N c ∼ ( n − 1 ) ! 2 ( 1 2 log n ) c − 1 ( c − 1 ) ! N_c\sim\frac{(n-1)!}{2}\frac{(\frac{1}{2}\log n)^{c-1}}{(c-1)!} N c ∼ 2 ( n − 1 )! ( c − 1 )! ( 2 1 l o g n ) c − 1 for fixed c c c and ∑ c N c = n ! [ x n ] e L ≥ 3 ( x ) ∼ n ! e − 3 / 4 / π n \sum_cN_c=n![x^n]e^{L_{\geq3}(x)}\sim n!e^{-3/4}/\sqrt{\pi n} ∑ c N c = n ! [ x n ] e L ≥ 3 ( x ) ∼ n ! e − 3/4 / π n .
Remark 4.3. Corollary 4.2 states that, on average, one in Θ ( n ) \Theta(\sqrt{n}) Θ ( n ) uniform 2-factors is Hamiltonian, with the explicit constant 2 π \frac{2}{\sqrt{\pi}} π 2 in the ratio ∑ c E Z c / E Z 1 = 2 π n ( 1 + o ( 1 ) ) \sum_c\mathbb{E}Z_c/\mathbb{E}Z_1=\frac{2}{\sqrt{\pi}}\sqrt{n}(1+o(1)) ∑ c E Z c / E Z 1 = π 2 n ( 1 + o ( 1 )) . Combining the bounds Z ≤ n E Z Z\leq n\mathbb{E}Z Z ≤ n E Z (by Markov’s inequality) and Z 1 ≥ E Z 1 / n Z_1\geq\mathbb{E}Z_1/n Z 1 ≥ E Z 1 / n (via small subgraph conditioning [12 , 20 ] ), as in [7 ] , gives P ( F Hamiltonian ∣ G ) = Ω ( n − 5 / 2 ) \mathbb{P}(F\text{ Hamiltonian}\mid G)=\Omega(n^{-5/2}) P ( F Hamiltonian ∣ G ) = Ω ( n − 5/2 ) with high probability. Proposition 7.1 sharpens this bound to P ( F Hamiltonian ∣ G ) = ( Λ / n ) ( 1 + o p ( 1 ) ) = Θ p ( n − 1 / 2 ) \mathbb{P}(F\text{ Hamiltonian}\mid G)=(\Lambda/\sqrt{n})(1+o_p(1))=\Theta_p(n^{-1/2}) P ( F Hamiltonian ∣ G ) = ( Λ/ n ) ( 1 + o p ( 1 )) = Θ p ( n − 1/2 ) , showing that for a uniformly random simple G G G the expected number of uniform 2-factor resamplings needed to obtain a Hamilton cycle is 1 / P ( F Hamiltonian ∣ G ) = n / Λ ( 1 + o p ( 1 ) ) = Θ p ( n ) 1/\mathbb{P}(F\text{ Hamiltonian}\mid G)=\sqrt{n}/\Lambda(1+o_p(1))=\Theta_p(\sqrt{n}) 1/ P ( F Hamiltonian ∣ G ) = n /Λ ( 1 + o p ( 1 )) = Θ p ( n ) .
Short cycles of G and transfer to simple graphs
Let X i = X i ( G ) X_i=X_i(G) X i = X i ( G ) denote the number of i i i -cycles of the host multigraph G G G (not to be confused with X = X ( F ) X=X(F) X = X ( F ) , the cycle count of the 2-factor). In the pairing model, the variables X i X_i X i converge in distribution to independent Poisson variables with means λ i = ( d − 1 ) i / ( 2 i ) \lambda_i=(d-1)^i/(2i) λ i = ( d − 1 ) i / ( 2 i ) [3 , 20 ] . Small subgraph conditioning [12 ] states that for a count Y Y Y of spanning structures satisfying E [ Y X i ] / E Y → λ i ( 1 + δ i ) \mathbb{E}[YX_i]/\mathbb{E}Y\to\lambda_i(1+\delta_i) E [ Y X i ] / E Y → λ i ( 1 + δ i ) together with E Y 2 / ( E Y ) 2 → exp ( ∑ i ≥ 1 λ i δ i 2 ) \mathbb{E}Y^2/(\mathbb{E}Y)^2\to\exp(\sum_{i\geq1}\lambda_i\delta_i^2) E Y 2 / ( E Y ) 2 → exp ( ∑ i ≥ 1 λ i δ i 2 ) , one has
Y E Y ⟶ W Y = ∏ i ≥ 1 ( 1 + δ i ) X i e − λ i δ i \frac{Y}{\mathbb{E}Y}\longrightarrow W_Y=\prod_{i\geq1}(1+\delta_i)^{X_i}e^{-\lambda_i\delta_i} E Y Y ⟶ W Y = i ≥ 1 ∏ ( 1 + δ i ) X i e − λ i δ i
in the sense that the ratio ( Y / E Y ) / W Y (Y/\mathbb{E}Y)/W_Y ( Y / E Y ) / W Y converges to 1 in probability. The two basic counts we need are Z 1 Z_1 Z 1 (Hamilton cycles; Robinson–Wormald [18 ] , cf. [7 , 12 ] ) and Z = ∑ c Z c Z=\sum_c Z_c Z = ∑ c Z c (2-factors; Robalewska [17 ] ). The corresponding parameters δ i \delta_i δ i , as well as their extension to the generating polynomial Z ( u ) = ∑ F u X ( F ) Z(u)=\sum_Fu^{X(F)} Z ( u ) = ∑ F u X ( F ) , admit a unified derivation. (For real u > 0 u>0 u > 0 , the ratio E [ Z ( u ) f ] / E Z ( u ) \mathbb{E}[Z(u)f]/\mathbb{E}Z(u) E [ Z ( u ) f ] / E Z ( u ) is the expectation of f ( P ) f(P) f ( P ) when ( P , F ) ∈ Ω n , d (P,F)\in\Omega_{n,d} ( P , F ) ∈ Ω n , d is drawn with probability proportional to u X ( F ) u^{X(F)} u X ( F ) .)
Lemma 5.1. For a uniform pair ( P , F ) ∈ Ω n , d (P,F)\in\Omega_{n,d} ( P , F ) ∈ Ω n , d , conditioning on F F F leaves P = F ∪ R P=F\cup R P = F ∪ R , where R R R is a uniformly random pairing of the remaining ( d − 2 ) n (d-2)n ( d − 2 ) n points, and the expected number of i i i -cycles of the resulting multigraph satisfies
E X i ( F ∪ R ) ⟶ ( d − 1 ) i + ( − 1 ) i 2 i , hence δ i 2 F = ( − 1 ) i ( d − 1 ) i . \mathbb{E}X_i(F\cup R)\longrightarrow\frac{(d-1)^i+(-1)^i}{2i},\qquad\text{hence}\qquad\delta_i^{2F}=\frac{(-1)^i}{(d-1)^i}. E X i ( F ∪ R ) ⟶ 2 i ( d − 1 ) i + ( − 1 ) i , hence δ i 2 F = ( d − 1 ) i ( − 1 ) i .
If F F F is constrained to be a single Hamilton cycle, the all-F F F contribution (an i i i -cycle that forms a component of F F F ) vanishes, yielding
δ i H = ( − 1 ) i − 1 ( d − 1 ) i , \delta_i^{\mathrm{H}} = \frac{(-1)^i-1}{(d-1)^i}, δ i H = ( d − 1 ) i ( − 1 ) i − 1 ,
which vanishes for even i i i , recovering the well-known fact that only odd short cycles affect Hamilton cycle counts [18 ] . More generally, for fixed i ≥ 1 i \ge1 i ≥ 1 ,
E [ Z ( u ) X i ] E Z ( u ) ⟶ λ i ( 1 + δ i ( u ) ) , δ i ( u ) = u − 1 + ( − 1 ) i ( d − 1 ) i . (3) \frac{\mathbb{E}[Z(u)X_i]}{\mathbb{E}Z(u)} \longrightarrow\lambda_i(1+\delta_i(u)), \qquad\delta_i(u)=\frac{u-1+(-1)^i}{(d-1)^i}. \tag*{(3)} E Z ( u ) E [ Z ( u ) X i ] ⟶ λ i ( 1 + δ i ( u )) , δ i ( u ) = ( d − 1 ) i u − 1 + ( − 1 ) i . (3)
with λ i = ( d − 1 ) i / ( 2 i ) \lambda_i=(d-1)^i/(2i) λ i = ( d − 1 ) i / ( 2 i ) . In particular, δ i ( 1 ) = δ i 2 F \delta_i(1)=\delta_i^{2F} δ i ( 1 ) = δ i 2 F and δ i ( u ) → δ i H \delta_i(u)\to\delta_i^{\mathrm{H}} δ i ( u ) → δ i H as u → 0 + u\to0^+ u → 0 + .
Proof. For a uniform pair, conditioning on F F F leaves R R R as a uniform pairing of the remaining ( d − 2 ) n (d-2)n ( d − 2 ) n points, so G = F ∪ R G=F\cup R G = F ∪ R . Fix i ≥ 1 i\ge1 i ≥ 1 and consider the expected number of directed closed walks of length i i i that project to undirected i i i -cycles of G G G , then divide by 2 i 2i 2 i .
Classify each edge of a prospective i i i -cycle as an F F F -edge or an R R R -edge. At a vertex whose two incident cycle edges are both of F F F -type, the ordered choice of (entry, exit) points contributes a factor of 2 2 2 ; when both are of R R R -type, the factor is ( d − 2 ) ( d − 3 ) (d-2)(d-3) ( d − 2 ) ( d − 3 ) ; and in the mixed case, it is 2 ( d − 2 ) 2(d-2) 2 ( d − 2 ) . Each F F F -edge has pairing probability ∼ 1 / ( 2 n ) \sim1/(2n) ∼ 1/ ( 2 n ) among the 2 n 2n 2 n points assigned to F F F , and each R R R -edge has pairing probability ∼ 1 / ( ( d − 2 ) n ) \sim1/((d-2)n) ∼ 1/ (( d − 2 ) n ) among the remaining points. Recording the sequence of edge types around the cycle via the 2 × 2 2\times2 2 × 2 transition matrix
T = ( 1 2 ( d − 2 ) 2 ( d − 2 ) d − 3 ) , T=\begin{pmatrix}
1 & \sqrt{2(d-2)}\\
\sqrt{2(d-2)} & d-3
\end{pmatrix}, T = ( 1 2 ( d − 2 ) 2 ( d − 2 ) d − 3 ) ,
we find that the eigenvalues of T T T are d − 1 d-1 d − 1 and − 1 -1 − 1 , so
E X i ( F ∪ R ) ⟶ tr ( T i ) 2 i = ( d − 1 ) i + ( − 1 ) i 2 i . \mathbb{E}X_i(F\cup R)\longrightarrow\frac{\operatorname{tr}(T^i)}{2i}=\frac{(d-1)^i+(-1)^i}{2i}. E X i ( F ∪ R ) ⟶ 2 i tr ( T i ) = 2 i ( d − 1 ) i + ( − 1 ) i .
Dividing by λ i = ( d − 1 ) i / ( 2 i ) \lambda_i=(d-1)^i/(2i) λ i = ( d − 1 ) i / ( 2 i ) yields 1 + δ i 2 F 1+\delta_i^{2F} 1 + δ i 2 F .
When F F F is conditioned to be a Hamilton cycle, the configuration in which the entire i i i -cycle lies in F F F is precluded (a Hamilton cycle consists of a single component of length n n n ). Removing that contribution subtracts 1 / ( 2 i ) 1/(2i) 1/ ( 2 i ) from the limit, yielding
( d − 1 ) i + ( − 1 ) i − 1 2 i = λ i ( 1 + δ i H ) , \frac{(d-1)^i+(-1)^i-1}{2i}=\lambda_i(1+\delta_i^{\mathrm{H}}), 2 i ( d − 1 ) i + ( − 1 ) i − 1 = λ i ( 1 + δ i H ) ,
in agreement with [7 Lemma 2] .
When each 2 2 2 -factor F F F is weighted by u X ( F ) u^{X(F)} u X ( F ) , any i i i -cycle that uses at least one edge of R R R intersects F F F in proper paths, constraining only O ( 1 ) O(1) O ( 1 ) points and leaving the expected weight of the completion of F F F unchanged up to a factor of 1 + O ( i / n ) 1+O(i/n) 1 + O ( i / n ) . By contrast, an i i i -cycle contained entirely in F F F forms an additional component of F F F and is multiplied by the weight u u u . Hence E [ Z ( u ) X i ] / E Z ( u ) \mathbb{E}[Z(u)X_i]/\mathbb{E}Z(u) E [ Z ( u ) X i ] / E Z ( u ) converges to
( d − 1 ) i + ( − 1 ) i − 1 + u 2 i = λ i ( 1 + δ i ( u ) ) , \frac{(d-1)^i+(-1)^i-1+u}{2i}=\lambda_i(1+\delta_i(u)), 2 i ( d − 1 ) i + ( − 1 ) i − 1 + u = λ i ( 1 + δ i ( u )) ,
which proves (3) .
Lemma 5.2. Fix d ≥ 3 d\ge3 d ≥ 3 , let i 1 , … , i m ≥ 1 i_1,\ldots,i_m\ge1 i 1 , … , i m ≥ 1 and r 1 , … , r m ≥ 1 r_1,\ldots,r_m\ge1 r 1 , … , r m ≥ 1 be integers, and write ( x ) r = x ( x − 1 ) ⋯ ( x − r + 1 ) (x)_r=x(x-1)\cdots(x-r+1) ( x ) r = x ( x − 1 ) ⋯ ( x − r + 1 ) . Then
E [ Z ( u ) ∏ j = 1 m ( X i j ) r j ] E Z ( u ) ⟶ ∏ j = 1 m λ i j r j ( 1 + δ i j ( u ) ) r j . \frac{\mathbb{E}\left[Z(u)\prod_{j=1}^{m}(X_{i_j})_{r_j}\right]}{\mathbb{E}Z(u)}
\longrightarrow\prod_{j=1}^{m}\lambda_{i_j}^{r_j}(1+\delta_{i_j}(u))^{r_j}. E Z ( u ) E [ Z ( u ) ∏ j = 1 m ( X i j ) r j ] ⟶ j = 1 ∏ m λ i j r j ( 1 + δ i j ( u ) ) r j . uniformly for u u u in a sufficiently small complex neighbourhood of 1 1 1 (and in particular along every sequence u n → 1 u_n\to1 u n → 1 ). In particular, for each fixed i i i and r ≥ 1 r\ge1 r ≥ 1 ,
E [ Z ( u ) ( X i ) r ] E Z ( u ) ⟶ λ i r ( 1 + δ i ( u ) ) r . \frac{\mathbb{E}\left[Z(u)(X_i)_r\right]}{\mathbb{E}Z(u)}
\longrightarrow\lambda_i^r(1+\delta_i(u))^r. E Z ( u ) E [ Z ( u ) ( X i ) r ] ⟶ λ i r ( 1 + δ i ( u ) ) r . Proof. As in Lemma 5.1, G = F ∪ R G=F\cup R G = F ∪ R . The falling factorial ( X i ) r (X_i)_r ( X i ) r enumerates ordered r r r -tuples of distinct i i i -cycles of G G G . For fixed i i i and r r r , mark r r r vertex-disjoint directed i i i -cycles and determine their contribution by the same transition-matrix computation: each marked cycle contributes a factor of λ i ( 1 + δ i ( u ) ) \lambda_i(1+\delta_i(u)) λ i ( 1 + δ i ( u )) in the limit, because (i) a cycle using at least one edge of R R R constrains only proper paths of F F F , and the underlying Gamma ratios Γ ( n − k + u / 2 ) n ! / ( Γ ( n + u / 2 ) ( n − k ) ! ) \Gamma(n-k+u/2)n!/\bigl(\Gamma(n+u/2)(n-k)!\bigr) Γ ( n − k + u /2 ) n ! / ( Γ ( n + u /2 ) ( n − k )! ) converge to 1 1 1 uniformly on a complex neighbourhood of u = 1 u=1 u = 1 up to an error of O ( i / n ) O(i/n) O ( i / n ) , and (ii) a short cycle contained entirely in F F F is weighted by u u u , as in the case r = 1 r=1 r = 1 of Lemma 5.1. Configurations in which two marked cycles share a vertex contribute O ( n − 1 ) O(n^{-1}) O ( n − 1 ) after normalisation by E Z ( u ) \mathbb{E}Z(u) E Z ( u ) : the union of two distinct i i i -cycles with a common vertex has v ≤ 2 i − 1 v\le2i-1 v ≤ 2 i − 1 vertices and e ≥ v + 1 e\ge v+1 e ≥ v + 1 edges, and every such configuration carries weight O ( n v − e ) O(n^{v-e}) O ( n v − e ) (a factor O ( n ) O(n) O ( n ) per vertex label, O ( 1 ) O(1) O ( 1 ) per point choice, and O ( 1 / n ) O(1/n) O ( 1/ n ) per pair), whence
E [ Z ( u ) # { ordered pairs of distinct i -cycles sharing a vertex } ] E Z ( u ) = ∑ v ≤ 2 i − 1 ∑ e ≥ v + 1 O ( n v − e ) = O ( n − 1 ) . \frac{\mathbb{E}\left[Z(u)\#\{\text{ordered pairs of distinct }i\text{-cycles sharing a vertex}\}\right]}{\mathbb{E}Z(u)}=\sum_{v\le2i-1}\sum_{e\ge v+1}O(n^{v-e})=O(n^{-1}). E Z ( u ) E [ Z ( u ) # { ordered pairs of distinct i -cycles sharing a vertex } ] = v ≤ 2 i − 1 ∑ e ≥ v + 1 ∑ O ( n v − e ) = O ( n − 1 ) . Thus, the contributions of the r r r marked cycles multiply, yielding λ i r ( 1 + δ i ( u ) ) r \lambda_i^r(1+\delta_i(u))^r λ i r ( 1 + δ i ( u ) ) r .
For several lengths i 1 , … , i m i_1,\ldots,i_m i 1 , … , i m , mark r j r_j r j cycles of each length i j i_j i j . As long as the total number of marked vertices remains O ( 1 ) O(1) O ( 1 ) , the same computation applies simultaneously: cross-terms in which distinct marked cycles share vertices are negligible, and the exponential formula factorises the contributions, yielding the product on the right-hand side. This extends Robalewska’s first-moment asymptotic E [ Z X i ] / E Z → λ i ( 1 + δ i ) \mathbb{E}[Z X_i]/\mathbb{E}Z \to\lambda_i(1+\delta_i) E [ Z X i ] / E Z → λ i ( 1 + δ i ) [17 Lemma 1, Corollary 1] from a single short cycle to falling factorials and general u u u .
Lemma 5.3. Fix d ≥ 3 d \ge3 d ≥ 3 . Conditioning the pairing model on the underlying multigraph being simple transfers every event of pairing-probability o ( 1 ) o(1) o ( 1 ) to an event of simple-graph probability o ( 1 ) o(1) o ( 1 ) . When the underlying multigraph is simple, every 2 2 2 -factor has girth at least 3 3 3 , so X = X ′ X=X^\prime X = X ′ . Consequently, conditioned on simplicity, the distribution of X X X for a uniform pair is asymptotically the girth-≥ 3 \ge3 ≥ 3 distribution of Theorem 4.1 :
E [ u X ∣ s i m p l e ] = e − 3 ( u − 1 ) / 4 E u X ( 1 + o ( 1 ) ) \mathbb{E}[u^X \mid\mathrm{simple}] = e^{-3(u-1)/4}\mathbb{E}u^X(1+o(1)) E [ u X ∣ simple ] = e − 3 ( u − 1 ) /4 E u X ( 1 + o ( 1 )) uniformly for u u u in a neighbourhood of 1 1 1 , where E u X \mathbb{E}u^X E u X is the generating function of Theorem 3.3 . In particular, the mean, variance, and central limit theorem of a uniformly random 2 2 2 -factor of a uniformly random simple d d d -regular graph are those of Theorem 4.1 , not those of Corollary 3.4.
Proof. By the classical enumeration of regular graphs [3 , 20 ] , P ( s i m p l e ) → c d ∈ ( 0 , 1 ) \mathbb{P}(\mathrm{simple}) \to c_d \in(0,1) P ( simple ) → c d ∈ ( 0 , 1 ) , a constant depending only on d d d . Hence, for any event A n A_n A n with P ( A n ) → 0 \mathbb{P}(A_n)\to0 P ( A n ) → 0 under the unconditioned pairing model,
P ( A n ∣ s i m p l e ) = P ( A n ∩ s i m p l e ) P ( s i m p l e ) ≤ P ( A n ) c d − o ( 1 ) ⟶ 0. \mathbb{P}(A_n\mid\mathrm{simple})=\frac{\mathbb{P}(A_n\cap\mathrm{simple})}{\mathbb{P}(\mathrm{simple})}\le\frac{\mathbb{P}(A_n)}{c_d-o(1)}\longrightarrow0. P ( A n ∣ simple ) = P ( simple ) P ( A n ∩ simple ) ≤ c d − o ( 1 ) P ( A n ) ⟶ 0.
This suffices for all subsequent conditional o p ( 1 ) o_p(1) o p ( 1 ) statements.
For the distribution of X X X , a simple host graph has no loops or digons, so every 2 2 2 -factor has girth at least 3 3 3 and X = X ′ X=X^\prime X = X ′ (which gives the generating-function asymptotic directly for complex u u u by Theorem 4.1 ). From the short-cycle perspective for real u > 0 u>0 u > 0 , simplicity of the pairing is the event { X 1 ( G ) = X 2 ( G ) = 0 } \{X_1(G)=X_2(G)=0\} { X 1 ( G ) = X 2 ( G ) = 0 } . By Lemma 5.1, E [ Z ( u ) X i ] / E Z ( u ) → λ i ( 1 + δ i ( u ) ) \mathbb{E}[Z(u)X_i]/\mathbb{E}Z(u)\to\lambda_i(1+\delta_i(u)) E [ Z ( u ) X i ] / E Z ( u ) → λ i ( 1 + δ i ( u )) for i = 1 , 2 i=1,2 i = 1 , 2 , with λ i = ( d − 1 ) i / ( 2 i ) \lambda_i=(d-1)^i/(2i) λ i = ( d − 1 ) i / ( 2 i ) and δ i ( u ) = ( u − 1 + ( − 1 ) i ) / ( d − 1 ) i \delta_i(u)=(u-1+(-1)^i)/(d-1)^i δ i ( u ) = ( u − 1 + ( − 1 ) i ) / ( d − 1 ) i ; the corresponding factorial moments (Lemma 5.2 ) imply that under the Z ( u ) Z(u) Z ( u ) -weighted pairing distribution, ( X 1 , X 2 ) (X_1,X_2) ( X 1 , X 2 ) converge in distribution to independent Poisson variables with means λ i ( 1 + δ i ( u ) ) \lambda_i(1+\delta_i(u)) λ i ( 1 + δ i ( u )) . Therefore,
E [ Z ( u ) 1 s i m p l e ] E Z ( u ) ⟶ exp ( − λ 1 ( 1 + δ 1 ( u ) ) − λ 2 ( 1 + δ 2 ( u ) ) ) , \frac{\mathbb{E}[Z(u)\mathbf{1}_{\mathrm{simple}}]}{\mathbb{E}Z(u)}
\longrightarrow\exp\bigl(-\lambda_1(1+\delta_1(u))-\lambda_2(1+\delta_2(u))\bigr), E Z ( u ) E [ Z ( u ) 1 simple ] ⟶ exp ( − λ 1 ( 1 + δ 1 ( u )) − λ 2 ( 1 + δ 2 ( u )) ) ,
and the conditional generating function is
E [ u X ∣ s i m p l e ] = E [ Z ( u ) 1 s i m p l e ] E [ Z ( 1 ) 1 s i m p l e ] = E Z ( u ) E Z ( 1 ) exp ( − ∑ i = 1 , 2 λ i ( δ i ( u ) − δ i ( 1 ) ) ) ( 1 + o ( 1 ) ) . \mathbb{E}\!\left[u^X \mid\mathrm{simple}\right]
=
\frac{\mathbb{E}\!\left[Z(u)\mathbf{1}_{\mathrm{simple}}\right]}{\mathbb{E}\!\left[Z(1)\mathbf{1}_{\mathrm{simple}}\right]}
=
\frac{\mathbb{E}Z(u)}{\mathbb{E}Z(1)}
\exp\left(-\sum_{i=1,2}\lambda_i\left(\delta_i(u)-\delta_i(1)\right)\right)(1+o(1)). E [ u X ∣ simple ] = E [ Z ( 1 ) 1 simple ] E [ Z ( u ) 1 simple ] = E Z ( 1 ) E Z ( u ) exp ( − i = 1 , 2 ∑ λ i ( δ i ( u ) − δ i ( 1 ) ) ) ( 1 + o ( 1 )) .
The exponent is λ 1 ( δ 1 ( u ) − δ 1 ( 1 ) ) + λ 2 ( δ 2 ( u ) − δ 2 ( 1 ) ) = ( u − 1 ) / 2 + ( u − 1 ) / 4 = 3 ( u − 1 ) / 4 \lambda_1(\delta_1(u)-\delta_1(1))+\lambda_2(\delta_2(u)-\delta_2(1))=(u-1)/2+(u-1)/4=3(u-1)/4 λ 1 ( δ 1 ( u ) − δ 1 ( 1 )) + λ 2 ( δ 2 ( u ) − δ 2 ( 1 )) = ( u − 1 ) /2 + ( u − 1 ) /4 = 3 ( u − 1 ) /4 , matching the multiplicative factor e − 3 ( u − 1 ) / 4 e^{-3(u-1)/4} e − 3 ( u − 1 ) /4 of Theorem 4.1 .
The second moment of Z ( u ) Z(u) Z ( u )
For 2-factors — unlike Hamilton cycles — the second moment admits an exact finite-n formula, because the overlap of two 2-factors requires no connectivity accounting. Write ( q ) m = q ( q + 1 ) ⋯ ( q + m − 1 ) (q)_m=q(q+1)\cdots(q+m-1) ( q ) m = q ( q + 1 ) ⋯ ( q + m − 1 ) , and recall Z ( u ) = Z ( u , P ) = ∑ F u X ( F ) Z(u)=Z(u,P)=\sum_F u^{X(F)} Z ( u ) = Z ( u , P ) = ∑ F u X ( F ) from § 2 .
Theorem 6.1. For all n n n , d ≥ 3 d\ge3 d ≥ 3 , and u u u , with a = d ( d − 1 ) a=d(d-1) a = d ( d − 1 ) , b = ( d − 2 ) ( d − 3 ) b=(d-2)(d-3) b = ( d − 2 ) ( d − 3 ) , and c e = d ( d − 1 ) ( d − 2 ) c_e=d(d-1)(d-2) c e = d ( d − 1 ) ( d − 2 ) ,
∑ P Z ( u , P ) 2 = n ! ∑ n 0 , p ≥ 0 ( ( u 2 ) n 0 + p ) 2 ( a b ) n 0 4 p n 0 ! p ! [ x n − n 0 ] ( e u 2 2 L ( a x ) π ^ ( x ) p ) M ( ( d − 4 ) n + 2 s ) , \sum_P Z(u,P)^2
=
n!\sum_{n_0,p\ge0}
\frac{\left(\left(\frac{u}{2}\right)_{n_0+p}\right)^2(ab)^{n_0}4^p}{n_0!\,p!}
\left[x^{n-n_0}\right]
\left(e^{\frac{u^2}{2}L(ax)}\widehat{\pi}(x)^p\right)
M\left((d-4)n+2s\right), P ∑ Z ( u , P ) 2 = n ! n 0 , p ≥ 0 ∑ n 0 ! p ! ( ( 2 u ) n 0 + p ) 2 ( ab ) n 0 4 p [ x n − n 0 ] ( e 2 u 2 L ( a x ) π ( x ) p ) M ( ( d − 4 ) n + 2 s ) , where π ^ ( x ) = c e 2 x 2 2 ( 1 − a x ) \widehat{\pi}(x)=\frac{c_e^2x^2}{2(1-ax)} π ( x ) = 2 ( 1 − a x ) c e 2 x 2 and s = n − n 0 − p s=n-n_0-p s = n − n 0 − p .
Proof. We count triples ( P , F 1 , F 2 ) (P,F_1,F_2) ( P , F 1 , F 2 ) weighted by u X ( F 1 ) + X ( F 2 ) u^{X(F_1)+X(F_2)} u X ( F 1 ) + X ( F 2 ) . Colour the pairs of F 1 ∖ F 2 F_1\setminus F_2 F 1 ∖ F 2 red, the pairs of F 2 ∖ F 1 F_2\setminus F_1 F 2 ∖ F 1 blue, and the shared pairs F 1 ∩ F 2 F_1\cap F_2 F 1 ∩ F 2 purple. The purple pairs form vertex-disjoint purple paths and cycles (corresponding to Robalewska’s classification of R 1 ∩ R 2 R_1\cap R_2 R 1 ∩ R 2 into paths, cycles, and crosses [17 §2] , where our free vertices are her crosses). Since every point of the pairing has a unique partner, sharing a point is equivalent to sharing a pair, so the red (F 1 F_1 F 1 -only) and blue (F 2 F_2 F 2 -only) edges use disjoint point sets and can never coincide. Each vertex is of one of four types, with the indicated number of ways to assign roles to its points: free (two red points and two blue points, all distinct: d ( d − 1 ) ( d − 2 ) ( d − 3 ) = a b d(d-1)(d-2)(d-3)=ab d ( d − 1 ) ( d − 2 ) ( d − 3 ) = ab ), a purple-path endpoint (one purple, one red, and one blue point: c e c_e c e ), or a purple-path interior or purple-cycle vertex (two purple points: a a a ). Figure 1 displays the local configurations in the pairing: a purple path versus a purple cycle, followed by the endpoint split and the free cross.
Figure 1. Overlap of two 2-factors F 1 F_1 F 1 (red) and F 2 F_2 F 2 (blue) of the same pairing P P P . Shared pairs F 1 ∩ F 2 F_1 \cap F_2 F 1 ∩ F 2 are drawn in purple and form vertex-disjoint paths and cycles. (a) A cycle of F 1 F_1 F 1 and a cycle of F 2 F_2 F 2 may share a purple path without coinciding. (b) If every pair of a cycle lies in both factors, that cycle is purple (weight u 2 u^2 u 2 ). (c) At a purple-path endpoint, one purple pair meets one red (F 1 F_1 F 1 -only) pair and one blue (F 2 F_2 F 2 -only) pair. (d) A free vertex (Robalewska’s “cross”, for d ≥ 4 d \ge4 d ≥ 4 ) lies on two red pairs and two blue pairs.
Purple cycles are cycles shared by both factors and carry weight u 2 u^2 u 2 each; by the computation in the proof of Theorem 3.1, their exponential generating function is exp ( u 2 2 L ( a x ) ) \exp\left(\frac{u^2}{2}L(ax)\right) exp ( 2 u 2 L ( a x ) ) . A purple path with j ≥ 1 j \ge1 j ≥ 1 edges spans j + 1 j+1 j + 1 vertices (ordered up to reversal) and admits c a 2 a j − 1 c_a^2a^{j-1} c a 2 a j − 1 choices of points, yielding the generating function π ^ ( x ) \widehat{\pi}(x) π ( x ) per path.
Given the purple structure, contract each purple path to a single vertex equipped with two unpaired red (F 1 F_1 F 1 ) points and two unpaired blue (F 2 F_2 F 2 ) points (one at each endpoint, with a factor of 2 for the traversal orientation in each colour). The red completion is then a u u u -weighted 2-regular pairing on the n 0 + p n_0+p n 0 + p vertices, each cycle of which expands to a single cycle of F 1 F_1 F 1 ; the same holds for the blue completion of F 2 F_2 F 2 , independently, since the two colours draw from disjoint sets of points. For n 0 n_0 n 0 vertices of weight α \alpha α and p p p vertices of weight β \beta β , the exponential formula yields
∑ 2-regular pairings σ u X ( σ ) = n 0 ! p ! [ y n 0 ζ p ] ( 1 − α y − β ζ ) − u / 2 = ( u / 2 n 0 + p ) α n 0 β p . \sum_{\text{2-regular pairings }\sigma}u^{X(\sigma)}=n_0!p^{-u/2}=\binom{u/2}{n_0+p}\alpha^{n_0}\beta^p. 2-regular pairings σ ∑ u X ( σ ) = n 0 ! p ! [ y n 0 ζ p ] ( 1 − α y − β ζ ) − u /2 = ( n 0 + p u /2 ) α n 0 β p .
with ( α , β ) = ( a , 2 ) (\alpha,\beta)=(a,2) ( α , β ) = ( a , 2 ) for the red completion and ( b , 2 ) (b,2) ( b , 2 ) for the blue completion (the vertex factor a b ab ab of a free vertex splitting as a ⋅ b a\cdot b a ⋅ b between the two colours). Finally, F 1 ∪ F 2 F_1\cup F_2 F 1 ∪ F 2 covers 4 n − 2 s 4n-2s 4 n − 2 s points, where s = w + e = n − n 0 − p s=w+e=n-n_0-p s = w + e = n − n 0 − p is the number of purple pairs (w w w purple-cycle vertices and e e e purple-path edges), so it extends to M ( ( d − 4 ) n + 2 s ) M((d-4)n+2s) M (( d − 4 ) n + 2 s ) complete pairings. Assembling these factors and summing over vertex-set partitions via the exponential formula yields the stated expression. For d = 3 d=3 d = 3 , we have b = 0 b=0 b = 0 , which forces n 0 = 0 n_0=0 n 0 = 0 , as a cubic vertex cannot accommodate four distinct points. (In exact arithmetic, Theorem 6.1 agrees integer-for-integer with brute-force enumeration of all M ( 12 ) = 10,395 M(12)=10{,}395 M ( 12 ) = 10 , 395 pairings for ( n , d ) = ( 4 , 3 ) (n,d)=(4,3) ( n , d ) = ( 4 , 3 ) and ( 3 , 4 ) (3,4) ( 3 , 4 ) at u ∈ { 1 2 , 1 , 2 } u\in\left\{\frac{1}{2},1,2\right\} u ∈ { 2 1 , 1 , 2 } .) □ \square □
Write M ( 2 m ) = ( 2 m ) ! / ( m ! 2 m ) M(2m)=(2m)!/(m!2^m) M ( 2 m ) = ( 2 m )! / ( m ! 2 m ) and E Z ( u ) = ∑ P Z ( u , P ) / M ( d n ) \mathbb{E}Z(u)=\sum_P Z(u,P)/M(dn) E Z ( u ) = ∑ P Z ( u , P ) / M ( d n ) . From
Theorem 3.1.
E Z ( u ) = n ! [ x n ] ( 1 − x ) − u / 2 ( d ( d − 1 ) ) n M ( ( d − 2 ) n ) M ( d n ) (4) \mathbb{E}Z(u)=n^{-u/2}(d(d-1))^n\frac{M((d-2)n)}{M(dn)} \tag*{(4)} E Z ( u ) = n ! [ x n ] ( 1 − x ) − u /2 ( d ( d − 1 ) ) n M ( d n ) M (( d − 2 ) n ) (4) in the multigraph (pairing) model; the girth-≥ 3 \ge3 ≥ 3 version replaces ( 1 − x ) − u / 2 (1-x)^{-u/2} ( 1 − x ) − u /2 with e − u ( x / 2 + x 2 / 4 ) ( 1 − x ) − u / 2 e^{-u(x/2+x^2/4)}(1-x)^{-u/2} e − u ( x /2 + x 2 /4 ) ( 1 − x ) − u /2 as in Theorem 4.1 . Lemma 5.1 therefore predicts the small-subgraph-conditioning second-moment ratio
E Z ( u ) 2 ( E Z ( u ) ) 2 ⟶ C ( u ) = exp ( ∑ i ≥ 1 λ i δ i ( u ) 2 ) = ( d − 1 d − 2 ) 1 + ( u − 1 ) 2 2 ( d − 1 d ) u − 1 . (5) \frac{\mathbb{E}Z(u)^2}{(\mathbb{E}Z(u))^2}\longrightarrow C(u)=\exp\left(\sum_{i\ge1}\lambda_i\delta_i(u)^2\right)=\left(\frac{d-1}{d-2}\right)^{\frac{1+(u-1)^2}{2}}\left(\frac{d-1}{d}\right)^{u-1}. \tag*{(5)} ( E Z ( u ) ) 2 E Z ( u ) 2 ⟶ C ( u ) = exp ( i ≥ 1 ∑ λ i δ i ( u ) 2 ) = ( d − 2 d − 1 ) 2 1 + ( u − 1 ) 2 ( d d − 1 ) u − 1 . (5)
Two consistency checks follow immediately: C ( u ) C(u) C ( u ) is the constant for the pairing model , where the product runs over all i ≥ 1 i\ge1 i ≥ 1 . At u = 1 u=1 u = 1 , we have C ( 1 ) = ( d − 1 ) / ( d − 2 ) C(1)=\sqrt{(d-1)/(d-2)} C ( 1 ) = ( d − 1 ) / ( d − 2 ) , and removing the factors for i = 1 , 2 i=1,2 i = 1 , 2 (the effect of conditioning on simplicity) yields
exp ( ∑ i ≥ 3 λ i ( δ i F H ) 2 ) = e − ( 2 d − 1 ) / ( 4 ( d − 1 ) 2 ) ( d − 1 ) / ( d − 2 ) , \exp\left(\sum_{i\ge3}\lambda_i(\delta_i^{\mathrm{FH}})^2\right)=e^{-(2d-1)/(4(d-1)^2)}\sqrt{(d-1)/(d-2)}, exp ( i ≥ 3 ∑ λ i ( δ i FH ) 2 ) = e − ( 2 d − 1 ) / ( 4 ( d − 1 ) 2 ) ( d − 1 ) / ( d − 2 ) ,
recovering the second-moment constant of Theorem 1 of Robalewska for simple G ( n , d ) G(n,d) G ( n , d ) [17 ] , whose Theorem 3 accordingly features the product over i ≥ 3 i\ge3 i ≥ 3 . As u → 0 + u\to0^+ u → 0 + , C ( 0 + ) = d / ( d − 2 ) C(0^+)=d/(d-2) C ( 0 + ) = d / ( d − 2 ) is the pairing Hamilton-cycle constant; the corresponding value for simple graphs is C ( 0 + ) e − λ 1 ( δ 1 H ) 2 = d d − 2 e − 2 / ( d − 1 ) C(0^+)e^{-\lambda_1(\delta_1^{\mathrm{H}})^2}=\frac{d}{d-2}e^{-2/(d-1)} C ( 0 + ) e − λ 1 ( δ 1 H ) 2 = d − 2 d e − 2/ ( d − 1 ) , cf. [7 , 18 ] .
Proposition 6.2. Fix d ≥ 3 d\ge3 d ≥ 3 . There exists ε = ε ( d ) > 0 \varepsilon=\varepsilon(d)>0 ε = ε ( d ) > 0 such that, in the pairing model ,
R n ( u ) : = E Z ( u ) 2 ( E Z ( u ) ) 2 ⟶ C ( u ) R_n(u):=\frac{\mathbb{E}Z(u)^2}{(\mathbb{E}Z(u))^2}\longrightarrow C(u) R n ( u ) := ( E Z ( u ) ) 2 E Z ( u ) 2 ⟶ C ( u ) as n → ∞ n\to\infty n → ∞ , uniformly for u u u in the closed disk D ‾ ( 1 , ε ) = { u ∈ C : ∣ u − 1 ∣ ≤ ε } \overline{D}(1,\varepsilon)=\{u\in\mathbb{C}:|u-1|\le\varepsilon\} D ( 1 , ε ) = { u ∈ C : ∣ u − 1∣ ≤ ε } , where C ( u ) C(u) C ( u ) is the entire function (5) . In particular, the convergence holds uniformly on the real interval [ 1 − ε , 1 + ε ] [1-\varepsilon,1+\varepsilon] [ 1 − ε , 1 + ε ] .
The full proof of Proposition 6.2 is given in Appendix § 9 ; we summarise the main steps here. In terms of the rescaled variables α = n 0 / n \alpha=n_0/n α = n 0 / n and β = p / n \beta=p/n β = p / n (the proportions of free vertices and purple paths), Stirling’s formula shows that each interior summand of R n ( u ) R_n(u) R n ( u ) has the form n − 1 exp ( n η ( α , β ) + Ψ u ( α , β ) + o ( 1 ) ) n^{-1}\exp(n\eta(\alpha,\beta)+\Psi_u(\alpha,\beta)+o(1)) n − 1 exp ( n η ( α , β ) + Ψ u ( α , β ) + o ( 1 )) , where σ = 1 − α − β \sigma=1-\alpha-\beta σ = 1 − α − β and γ ^ = 1 − α − 2 β \hat{\gamma}=1-\alpha-2\beta γ ^ = 1 − α − 2 β . The leading exponent η \eta η does not depend on u u u , because u u u enters only through shifts in the arguments of Gamma functions and hence only through the O ( 1 ) O(1) O ( 1 ) term Ψ u \Psi_u Ψ u . As a result, η \eta η attains its unique global maximum on the domain of summation at
α ∗ = ( d − 2 ) ( d − 3 ) d ( d − 1 ) , β ∗ = 2 ( d − 2 ) d ( d − 1 ) , σ ∗ = 2 d . \alpha^*=\frac{(d-2)(d-3)}{d(d-1)},\qquad\beta^*=\frac{2(d-2)}{d(d-1)},\qquad\sigma^*=\frac{2}{d}. α ∗ = d ( d − 1 ) ( d − 2 ) ( d − 3 ) , β ∗ = d ( d − 1 ) 2 ( d − 2 ) , σ ∗ = d 2 .
with negative-definite Hessian H = D 2 η ( α ∗ , β ∗ ) H = D^2\eta(\alpha^*,\beta^*) H = D 2 η ( α ∗ , β ∗ ) independent of u u u , and the tail bounds outside a neighbourhood of ( α ∗ , β ∗ ) (\alpha^*,\beta^*) ( α ∗ , β ∗ ) are likewise uniform in u u u , while u ↦ Ψ u ( α ∗ , β ∗ ) u \mapsto\Psi_u(\alpha^*,\beta^*) u ↦ Ψ u ( α ∗ , β ∗ ) is holomorphic. The maximiser ( α ∗ , β ∗ ) (\alpha^*,\beta^*) ( α ∗ , β ∗ ) coincides with the point c = ( d − 2 ) ( d − 3 ) n / ( d ( d − 1 ) ) c=(d-2)(d-3)n/(d(d-1)) c = ( d − 2 ) ( d − 3 ) n / ( d ( d − 1 )) , k = 2 ( d − 2 ) n / ( d ( d − 1 ) ) k=2(d-2)n/(d(d-1)) k = 2 ( d − 2 ) n / ( d ( d − 1 )) about which Robalewska expands her second-moment sum [17 ] , and the Gaussian integral at ( α ∗ , β ∗ ) (\alpha^*,\beta^*) ( α ∗ , β ∗ ) evaluates to C ( u ) C(u) C ( u ) . (For d = 3 d=3 d = 3 , where b = 0 b=0 b = 0 forces n 0 = 0 n_0=0 n 0 = 0 , the sum is one-dimensional with β ∗ = 1 / 3 \beta^*=1/3 β ∗ = 1/3 .)
Lemma 6.3. Fix d ≥ 3 d \ge3 d ≥ 3 and let ε = ε ( d ) > 0 \varepsilon=\varepsilon(d)>0 ε = ε ( d ) > 0 be as in Proposition 6.2 . For u , v ∈ D ‾ ( 1 , ε ) u,v \in\overline{D}(1,\varepsilon) u , v ∈ D ( 1 , ε ) ,
R n ( u , v ) : = E [ Z ( u ) Z ( v ) ] E Z ( u ) E Z ( v ) ⟶ exp ( ∑ i ≥ 1 λ i δ i ( u ) δ i ( v ) ) (6) R_n(u,v) := \frac{\mathbb{E}[Z(u)Z(v)]}{\mathbb{E}Z(u)\mathbb{E}Z(v)} \longrightarrow\exp\left(\sum_{i\ge1}\lambda_i\delta_i(u)\delta_i(v)\right) \tag*{(6)} R n ( u , v ) := E Z ( u ) E Z ( v ) E [ Z ( u ) Z ( v )] ⟶ exp ( i ≥ 1 ∑ λ i δ i ( u ) δ i ( v ) ) (6) uniformly on the product of disks. In particular, for every u ∈ D ‾ ( 1 , ε ) u \in\overline{D}(1,\varepsilon) u ∈ D ( 1 , ε ) ,
E ∣ Z ( u ) ∣ 2 ∣ E Z ( u ) ∣ 2 ⟶ exp ( ∑ i ≥ 1 λ i ∣ δ i ( u ) ∣ 2 ) . (7) \frac{\mathbb{E}|Z(u)|^2}{|\mathbb{E}Z(u)|^2} \longrightarrow\exp\left(\sum_{i\ge1}\lambda_i|\delta_i(u)|^2\right). \tag*{(7)} ∣ E Z ( u ) ∣ 2 E ∣ Z ( u ) ∣ 2 ⟶ exp ( i ≥ 1 ∑ λ i ∣ δ i ( u ) ∣ 2 ) . (7)
Proof. The proof of Theorem 6.1 adapts verbatim to the bilinear weight u X ( F 1 ) v X ( F 2 ) u^{X(F_1)}v^{X(F_2)} u X ( F 1 ) v X ( F 2 ) : purple cycles contribute u v uv uv instead of u 2 u^2 u 2 , and the two monochromatic completions contribute Pochhammer factors ( u / 2 ) n 0 + p (u/2)_{n_0+p} ( u /2 ) n 0 + p and ( v / 2 ) n 0 + p (v/2)_{n_0+p} ( v /2 ) n 0 + p instead of a square. The exponent η \eta η remains unchanged, while the O ( 1 ) O(1) O ( 1 ) term becomes
Ψ u , v ( α , β ) = − log ( 2 π ) − 1 2 log ( α β γ ^ ) + u + v − 2 2 log ( α + β ) + u v − 1 2 log ( σ / β ) . (8) \Psi_{u,v}(\alpha,\beta)=-\log(2\pi)-\frac{1}{2}\log(\alpha\beta\widehat{\gamma})+\frac{u+v-2}{2}\log(\alpha+\beta)+\frac{uv-1}{2}\log(\sigma/\beta). \tag*{(8)} Ψ u , v ( α , β ) = − log ( 2 π ) − 2 1 log ( α β γ ) + 2 u + v − 2 log ( α + β ) + 2 uv − 1 log ( σ / β ) . (8)
where α \alpha α , β \beta β , σ \sigma σ , γ ^ \widehat{\gamma} γ are the proportions defined in Appendix § 9 , cf. (15) ; Ψ u , v \Psi_{u,v} Ψ u , v is jointly holomorphic for ∣ u − 1 ∣ , ∣ v − 1 ∣ ≤ ε |u-1|,|v-1|\le\varepsilon ∣ u − 1∣ , ∣ v − 1∣ ≤ ε and coincides with Ψ u \Psi_u Ψ u on the diagonal v = u v=u v = u . At the maximiser (21) , one has α ∗ + β ∗ = ( d − 2 ) / d \alpha^*+\beta^*=(d-2)/d α ∗ + β ∗ = ( d − 2 ) / d and σ ∗ / β ∗ = ( d − 1 ) / ( d − 2 ) \sigma^*/\beta^*=(d-1)/(d-2) σ ∗ / β ∗ = ( d − 1 ) / ( d − 2 ) , so
e Ψ u , v ( α ∗ , β ∗ ) 2 π det ( − H ) = C ( 1 ) ( d − 2 d ) ( u + v − 2 ) / 2 ( d − 1 d − 2 ) ( u v − 1 ) / 2 = exp ( ∑ i ≥ 1 λ i δ i ( u ) δ i ( v ) ) . \begin{aligned}
e^{\Psi_{u,v}(\alpha^*,\beta^*)}\frac{2\pi}{\sqrt{\det(-H)}}=C(1)\left(\frac{d-2}{d}\right)^{(u+v-2)/2}\left(\frac{d-1}{d-2}\right)^{(uv-1)/2} \\
&= \exp\left(\sum_{i\ge1}\lambda_i\delta_i(u)\delta_i(v)\right).
\end{aligned} e Ψ u , v ( α ∗ , β ∗ ) det ( − H ) 2 π = C ( 1 ) ( d d − 2 ) ( u + v − 2 ) /2 ( d − 2 d − 1 ) ( uv − 1 ) /2 = exp ( i ≥ 1 ∑ λ i δ i ( u ) δ i ( v ) ) .
which proves (6) . (The second equality is the polarisation of the identity e Ψ u ∗ 2 π / det ( − H ) = C ( u ) e^{\Psi_u^*}2\pi/\sqrt{\det(-H)}=C(u) e Ψ u ∗ 2 π / det ( − H ) = C ( u ) established in Appendix § 9 ; for d = 3 d=3 d = 3 , the same evaluation holds with the one-dimensional leading factor established there.) For (7) , set v = u ‾ v=\overline{u} v = u . Since δ i ( u ‾ ) = δ i ( u ) ‾ \delta_i(\overline{u})=\overline{\delta_i(u)} δ i ( u ) = δ i ( u ) , the exponent becomes ∑ i λ i ∣ δ i ( u ) ∣ 2 \sum_i\lambda_i|\delta_i(u)|^2 ∑ i λ i ∣ δ i ( u ) ∣ 2 . Furthermore, Z ( u ‾ ) = Z ( u ) ‾ Z(\overline{u})=\overline{Z(u)} Z ( u ) = Z ( u ) (the cycle counts being real), which yields E Z ( u ) Z ( u ‾ ) = E ∣ Z ( u ) ∣ 2 \mathbb{E}Z(u)Z(\overline{u})=\mathbb{E}|Z(u)|^2 E Z ( u ) Z ( u ) = E ∣ Z ( u ) ∣ 2 .
The conditional distribution of X X X given G G G
We now pass from a uniform pair ( P , F ) (P,F) ( P , F ) to the conditional distribution of X X X given G G G , that is, to a uniformly random 2-factor of a fixed graph G G G , where G G G is itself a uniformly random simple d d d -regular graph. The argument uses small subgraph conditioning [12 , 20 ] , following Robalewska’s analysis of 2-factors [17 ] . We first determine the conditional probability of Hamiltonicity (§ 7.1 ) and establish small subgraph conditioning for the generating polynomial Z ( u ) Z(u) Z ( u ) at real u u u near 1. In § 7.2 we extend this convergence to a complex disk around u = 1 u=1 u = 1 by a normal-family compactness argument; differentiating at u = 1 u=1 u = 1 via Cauchy’s estimate then gives the conditional mean, and evaluating at u = e i t / σ n u=e^{it/\sigma_n} u = e i t / σ n gives the conditional central limit theorem (§ 7.3 ). The required second moment is the one computed in § 6 .
The conditional probability of a Hamilton cycle
Proposition 7.1. Fix d ≥ 3 d \ge3 d ≥ 3 , and let G G G be a uniformly random simple d d d -regular graph on n n n vertices. Then, as n → ∞ n \to\infty n → ∞ ,
n Z 1 ( G ) Z ( G ) ⟹ Λ = π e 3 / 4 2 ∏ i ≥ 3 ( 1 + δ i H 1 + δ i 2 F ) ξ i e λ i ( δ i 2 F − δ i H ) , \sqrt{n}\frac{Z_1(G)}{Z(G)} \mathrel{\Longrightarrow} \Lambda= \frac{\sqrt{\pi}e^{3/4}}{2}\prod_{i\ge3}\left(\frac{1+\delta_i^{\mathrm{H}}}{1+\delta_i^{2\mathrm{F}}}\right)^{\xi_i}e^{\lambda_i(\delta_i^{2\mathrm{F}}-\delta_i^{\mathrm{H}})}, n Z ( G ) Z 1 ( G ) ⟹ Λ = 2 π e 3/4 i ≥ 3 ∏ ( 1 + δ i 2 F 1 + δ i H ) ξ i e λ i ( δ i 2 F − δ i H ) , a strictly positive, almost surely finite random variable, where ( ξ i ) i ≥ 3 (\xi_i)_{i\ge3} ( ξ i ) i ≥ 3 are independent Poisson( λ i ) (\lambda_i) ( λ i ) random variables (the distributional limits of the short-cycle counts ( X i ) i ≥ 3 (X_i)_{i\ge3} ( X i ) i ≥ 3 ) and δ i H \delta_i^{\mathrm{H}} δ i H , δ i 2 F \delta_i^{2\mathrm{F}} δ i 2 F are given by Lemma 5.1. In particular, for a uniformly random 2-factor F F F of G G G ,
P ( F Hamiltonian ∣ G ) = Θ p ( n − 1 / 2 ) . \mathbb{P}(F\text{ Hamiltonian}\mid G)=\Theta_p(n^{-1/2}). P ( F Hamiltonian ∣ G ) = Θ p ( n − 1/2 ) .
Proof. By small subgraph conditioning in the pairing model, Z 1 / E Z 1 ⇒ W 1 Z_1/\mathbb{E}Z_1 \Rightarrow W_1 Z 1 / E Z 1 ⇒ W 1 (Robinson–Wormald [18 ] ) and Z / E Z ⇒ W Z/\mathbb{E}Z \Rightarrow W Z / E Z ⇒ W (Robalewska [17 ] ; re-proved below as the u = 1 u=1 u = 1 case of Lemma 7.2), both jointly with the short-cycle counts ( X i ) (X_i) ( X i ) in the sense of Janson [12 Theorem 1] , where W Y = ∏ i ≥ 1 ( 1 + δ i Y ) X i e − λ i δ i Y W_Y=\prod_{i\ge1}(1+\delta_i^Y)^{X_i}e^{-\lambda_i\delta_i^Y} W Y = ∏ i ≥ 1 ( 1 + δ i Y ) X i e − λ i δ i Y is evaluated at the cycle counts of the same graph. Hence
Z 1 Z = E Z 1 E Z ⋅ W 1 W ( 1 + o p ( 1 ) ) , \frac{Z_1}{Z}=\frac{\mathbb{E}Z_1}{\mathbb{E}Z}\cdot\frac{W_1}{W}(1+o_p(1)), Z Z 1 = E Z E Z 1 ⋅ W W 1 ( 1 + o p ( 1 )) ,
with expectations taken under the pairing model, and E Z 1 / E Z = P ( X = 1 ) = 1 2 π / n ( 1 + o ( 1 ) ) \mathbb{E}Z_1/\mathbb{E}Z=\mathbb{P}(X=1)=\frac{1}{2}\sqrt{\pi/n}(1+o(1)) E Z 1 / E Z = P ( X = 1 ) = 2 1 π / n ( 1 + o ( 1 )) by Corollary 4.2. Conditioning on simplicity corresponds to conditioning on X 1 = X 2 = 0 X_1=X_2=0 X 1 = X 2 = 0 , an event of limiting probability e − λ 1 − λ 2 > 0 e^{-\lambda_1-\lambda_2}>0 e − λ 1 − λ 2 > 0 ; thus, the o p ( 1 ) o_p(1) o p ( 1 ) term is preserved (Lemma 5.3), and the factors for i = 1 , 2 i=1,2 i = 1 , 2 in W 1 / W W_1/W W 1 / W become deterministic:
e − λ 1 δ 1 H − λ 2 δ 2 H e − λ 1 δ 1 2 F − λ 2 δ 2 2 F = e 1 e 1 / 2 e − 1 / 4 = e 3 / 4 . \frac{e^{-\lambda_1\delta_1^{\mathrm{H}}-\lambda_2\delta_2^{\mathrm{H}}}}{e^{-\lambda_1\delta_1^{2\mathrm{F}}-\lambda_2\delta_2^{2\mathrm{F}}}}
=\frac{e^1}{e^{1/2}e^{-1/4}}=e^{3/4}. e − λ 1 δ 1 2 F − λ 2 δ 2 2 F e − λ 1 δ 1 H − λ 2 δ 2 H = e 1/2 e − 1/4 e 1 = e 3/4 .
using λ 1 δ 1 H = − 1 \lambda_1\delta_1^{\mathrm{H}}=-1 λ 1 δ 1 H = − 1 , δ 2 H = 0 \delta_2^{\mathrm{H}}=0 δ 2 H = 0 , λ 1 δ 1 2 F = − 1 2 \lambda_1\delta_1^{2\mathrm{F}}=-\frac{1}{2} λ 1 δ 1 2 F = − 2 1 , and λ 2 δ 2 2 F = 1 4 \lambda_2\delta_2^{2\mathrm{F}}=\frac{1}{4} λ 2 δ 2 2 F = 4 1 . This converts 1 2 π / n \frac{1}{2}\sqrt{\pi/n} 2 1 π / n into the girth-≥ 3 \ge3 ≥ 3 constant π e 3 / 4 2 n − 1 / 2 \frac{\sqrt{\pi e^3/4}}{2}n^{-1/2} 2 π e 3 /4 n − 1/2 of Corollary 4.2 and leaves the product over i ≥ 3 i\ge3 i ≥ 3 . Since ( X i ) i ≥ 3 (X_i)_{i\ge3} ( X i ) i ≥ 3 converges in distribution to ( ξ i ) i ≥ 3 (\xi_i)_{i\ge3} ( ξ i ) i ≥ 3 , that product converges in distribution to the product in the definition of Λ \Lambda Λ . To see that Λ ∈ ( 0 , ∞ ) \Lambda\in(0,\infty) Λ ∈ ( 0 , ∞ ) almost surely, note that 1 + δ i H > 0 1+\delta_i^{\mathrm{H}}>0 1 + δ i H > 0 and 1 + δ i 2 F > 0 1+\delta_i^{2\mathrm{F}}>0 1 + δ i 2 F > 0 for all i ≥ 3 i\ge3 i ≥ 3 and d ≥ 3 d\ge3 d ≥ 3 . With ρ i = log ( ( 1 + δ i H ) / ( 1 + δ i 2 F ) ) = − ( d − 1 ) − i + O ( ( d − 1 ) − 2 i ) \rho_i=\log((1+\delta_i^{\mathrm{H}})/(1+\delta_i^{2\mathrm{F}}))=-(d-1)^{-i}+O((d-1)^{-2i}) ρ i = log (( 1 + δ i H ) / ( 1 + δ i 2 F )) = − ( d − 1 ) − i + O (( d − 1 ) − 2 i ) , the summands of ∑ i ≥ 3 ( ξ i ρ i − λ i ( δ i H − δ i 2 F ) ) \sum_{i\ge3}(\xi_i\rho_i-\lambda_i(\delta_i^{\mathrm{H}}-\delta_i^{2\mathrm{F}})) ∑ i ≥ 3 ( ξ i ρ i − λ i ( δ i H − δ i 2 F )) are independent with expectations O ( i − 1 ( d − 1 ) − i ) O(i^{-1}(d-1)^{-i}) O ( i − 1 ( d − 1 ) − i ) and variances λ i ρ i 2 = O ( i − 1 ( d − 1 ) − i ) \lambda_i\rho_i^2=O(i^{-1}(d-1)^{-i}) λ i ρ i 2 = O ( i − 1 ( d − 1 ) − i ) , so the series converges almost surely by Kolmogorov’s two-series theorem.
Note the cancellation implicit in Λ \Lambda Λ : individually, ∑ i λ i ( δ i 2 F − δ i H ) = ∑ i 1 2 i = ∞ \sum_i\lambda_i(\delta_i^{2\mathrm{F}}-\delta_i^{\mathrm{H}})=\sum_i\frac{1}{2i}=\infty ∑ i λ i ( δ i 2 F − δ i H ) = ∑ i 2 i 1 = ∞ , but each divergent centering term is cancelled by the expectation of the corresponding ξ i \xi_i ξ i -term, by the same mechanism that separates the multigraph and girth-≥ 3 \ge3 ≥ 3 constants in Theorem 4.1 . What Proposition 7.1 does not establish is the conditional mean or the central limit theorem for the full cycle count; to obtain those, we apply small subgraph conditioning to the generating polynomial Z ( u ) = ∑ c u c Z c ( G ) Z(u)=\sum_c u^c Z_c(G) Z ( u ) = ∑ c u c Z c ( G ) for u u u near 1 1 1 , whose first moment is given by Theorem 3.3 and whose second moment is given by Theorem 6.1.
Small subgraph conditioning for Z ( u ) Z(u) Z ( u ) on a complex disk
Lemma 7.2. Fix d ≥ 3 d\ge3 d ≥ 3 and let u ∈ [ 1 − ε , 1 + ε ] u\in[1-\varepsilon,1+\varepsilon] u ∈ [ 1 − ε , 1 + ε ] be as in Proposition 6.2 . Let ( ξ i ) i ≥ 1 (\xi_i)_{i\ge1} ( ξ i ) i ≥ 1 be independent Poisson( λ i ) (\lambda_i) ( λ i ) variables (the distributional limits of the short-cycle counts ( X i ) i ≥ 1 (X_i)_{i\ge1} ( X i ) i ≥ 1 ), and define
W ( u ) = W ( u ; ξ ) = ∏ i ≥ 1 ( 1 + δ i ( u ) ) ξ i e − λ i δ i ( u ) . W(u)=W(u;\xi)=\prod_{i\ge1}(1+\delta_i(u))^{\xi_i}e^{-\lambda_i\delta_i(u)}. W ( u ) = W ( u ; ξ ) = i ≥ 1 ∏ ( 1 + δ i ( u ) ) ξ i e − λ i δ i ( u ) . Then in the pairing model, jointly in distribution,
( Z ( u ) E Z ( u ) , ( X i ) i ≥ 1 ) ⟹ ( W ( u ) , ( ξ i ) i ≥ 1 ) . \left(\frac{Z(u)}{\mathbb{E}Z(u)},(X_i)_{i\ge1}\right)\Longrightarrow(W(u),(\xi_i)_{i\ge1}). ( E Z ( u ) Z ( u ) , ( X i ) i ≥ 1 ) ⟹ ( W ( u ) , ( ξ i ) i ≥ 1 ) . In particular, Z ( u ) / E Z ( u ) ⟹ W ( u ) Z(u)/\mathbb{E}Z(u)\Longrightarrow W(u) Z ( u ) / E Z ( u ) ⟹ W ( u ) in distribution, with E W ( u ) = 1 \mathbb{E}W(u)=1 E W ( u ) = 1 and W ( u ) > 0 W(u)>0 W ( u ) > 0 almost surely. The family { W ( u ) } \{W(u)\} { W ( u )} is defined jointly on the sequence of independent Poisson variables ( ξ i ) i ≥ 1 (\xi_i)_{i\ge1} ( ξ i ) i ≥ 1 , and the map u ↦ W ( u ) u\mapsto W(u) u ↦ W ( u ) is almost surely C 1 C^1 C 1 on the interval.
Proof. Proposition 6.2 gives
E Z ( u ) 2 ( E Z ( u ) ) 2 ⟶ C ( u ) = exp ( ∑ i λ i δ i ( u ) 2 ) . \frac{\mathbb{E}Z(u)^2}{(\mathbb{E}Z(u))^2}\longrightarrow C(u)=\exp\left(\sum_i\lambda_i\delta_i(u)^2\right). ( E Z ( u ) ) 2 E Z ( u ) 2 ⟶ C ( u ) = exp ( i ∑ λ i δ i ( u ) 2 ) . Lemma 5.1 gives E [ Z ( u ) X i ] / E Z ( u ) → λ i ( 1 + δ i ( u ) ) \mathbb{E}[Z(u)X_i]/\mathbb{E}Z(u)\to\lambda_i(1+\delta_i(u)) E [ Z ( u ) X i ] / E Z ( u ) → λ i ( 1 + δ i ( u )) , and Lemma 5.2 provides the complete factorial-moment hierarchy
E [ Z ( u ) ( X i ) r ] E Z ( u ) ⟶ λ i r ( 1 + δ i ( u ) ) r \frac{\mathbb{E}[Z(u)(X_i)_r]}{\mathbb{E}Z(u)}\longrightarrow\lambda_i^r(1+\delta_i(u))^r E Z ( u ) E [ Z ( u ) ( X i ) r ] ⟶ λ i r ( 1 + δ i ( u ) ) r
together with the joint moments across finitely many cycle lengths. Since u > 0 u>0 u > 0 , the quantity Y = Z ( u ) = ∑ c u c Z c Y=Z(u)=\sum_c u^c Z_c Y = Z ( u ) = ∑ c u c Z c is nonnegative, δ i ( u ) > − 1 \delta_i(u)>-1 δ i ( u ) > − 1 for all i i i , and ∑ i λ i δ i ( u ) 2 < ∞ \sum_i\lambda_i\delta_i(u)^2<\infty ∑ i λ i δ i ( u ) 2 < ∞ ; these are precisely hypotheses (A1)–(A4) of Janson’s small subgraph conditioning theorem [12 Theorem 1] , whose conclusion is the stated joint convergence.
To verify the regularity of W ( u ) W(u) W ( u ) , note that δ i ( u ) = ( u − 1 + ( − 1 ) i ) / ( d − 1 ) i \delta_i(u)=(u-1+(-1)^i)/(d-1)^i δ i ( u ) = ( u − 1 + ( − 1 ) i ) / ( d − 1 ) i is affine in u u u , and for u u u near 1 one has 1 + δ i ( u ) > 0 1+\delta_i(u)>0 1 + δ i ( u ) > 0 uniformly in i ≥ 1 i\ge1 i ≥ 1 for d ≥ 3 d\ge3 d ≥ 3 . We may therefore write log W ( u ) = ∑ i [ ( ξ i − λ i ) δ i ( u ) + ξ i ( log ( 1 + δ i ( u ) ) − δ i ( u ) ) ] \log W(u)=\sum_i\left[(\xi_i-\lambda_i)\delta_i(u)+\xi_i\left(\log(1+\delta_i(u))-\delta_i(u)\right)\right] log W ( u ) = ∑ i [ ( ξ i − λ i ) δ i ( u ) + ξ i ( log ( 1 + δ i ( u )) − δ i ( u ) ) ] . The first series decomposes as ( u − 1 ) ∑ i ( ξ i − λ i ) ( d − 1 ) − i + ∑ i ( ξ i − λ i ) ( − 1 ) i ( d − 1 ) − i (u-1)\sum_i(\xi_i-\lambda_i)(d-1)^{-i}+\sum_i(\xi_i-\lambda_i)(-1)^i(d-1)^{-i} ( u − 1 ) ∑ i ( ξ i − λ i ) ( d − 1 ) − i + ∑ i ( ξ i − λ i ) ( − 1 ) i ( d − 1 ) − i , which are two almost surely convergent random series (with variances ∑ i λ i ( d − 1 ) − 2 i < ∞ \sum_i\lambda_i(d-1)^{-2i}<\infty ∑ i λ i ( d − 1 ) − 2 i < ∞ ) multiplied by entire functions of u u u ; the second series converges absolutely and locally uniformly in u u u , since ∣ log ( 1 + δ ) − δ ∣ ≤ ∣ δ ∣ 2 |\log(1+\delta)-\delta|\le|\delta|^2 ∣ log ( 1 + δ ) − δ ∣ ≤ ∣ δ ∣ 2 and E ∑ i ξ i ∣ δ i ( u ) ∣ 2 < ∞ \mathbb{E}\sum_i\xi_i|\delta_i(u)|^2<\infty E ∑ i ξ i ∣ δ i ( u ) ∣ 2 < ∞ . Hence, u ↦ log W ( u ) u\mapsto\log W(u) u ↦ log W ( u ) is almost surely real-analytic near 1, and
∂ u log W ( u ) = ∑ i ≥ 1 ( ξ i δ i ′ ( u ) 1 + δ i ( u ) − λ i δ i ′ ( u ) ) , δ i ′ ( u ) = ( d − 1 ) − i , \partial_u\log W(u)=\sum_{i\ge1}\left(\xi_i\frac{\delta_i'(u)}{1+\delta_i(u)}-\lambda_i\delta_i'(u)\right),\qquad\delta_i'(u)=(d-1)^{-i}, ∂ u log W ( u ) = i ≥ 1 ∑ ( ξ i 1 + δ i ( u ) δ i ′ ( u ) − λ i δ i ′ ( u ) ) , δ i ′ ( u ) = ( d − 1 ) − i ,
which is an almost surely convergent series, as for Λ \Lambda Λ in Proposition 7.1 . □
We next extend Lemma 7.2 to uniform convergence on a complex disk centered at u = 1 u=1 u = 1 and deduce Theorems 7.4 and 7.5 . Small subgraph conditioning itself is invoked only for real u > 0 u>0 u > 0 , where Z ( u ) Z(u) Z ( u ) is nonnegative; the passage to complex u u u is a compactness argument for random holomorphic functions, whose only additional input is the uniform bound on the complex second moment provided by Lemma 6.3. The conditional mean then follows from Cauchy’s estimate for the derivative at u = 1 u=1 u = 1 , and the CLT requires only u n = e i t / σ n → 1 u_n=e^{it/\sigma_n}\to1 u n = e i t / σ n → 1 .
Lemma 7.3. Fix d ≥ 3 d\ge3 d ≥ 3 , and choose ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) small enough that the conclusion of Proposition 6.2 holds and 1 + δ i ( u ) ≠ 0 1+\delta_i(u)\ne0 1 + δ i ( u ) = 0 for all i ≥ 1 i\ge1 i ≥ 1 and ∣ u − 1 ∣ ≤ ε |u-1|\le\varepsilon ∣ u − 1∣ ≤ ε . Let D ′ = D ( 1 , ε / 2 ) D'=D(1,\varepsilon/2) D ′ = D ( 1 , ε /2 ) and let H ( D ′ ) \mathcal{H}(D') H ( D ′ ) denote the space of holomorphic functions on D ′ D' D ′ endowed with the topology of locally uniform convergence. Set Y ^ n ( u ) = Z ( u ) / E Z ( u ) \widehat{Y}_n(u)=Z(u)/\mathbb{E}Z(u) Y n ( u ) = Z ( u ) / E Z ( u ) . With ( ξ i ) (\xi_i) ( ξ i ) and W ( u ) = W ( u ; ξ ) W(u)=W(u;\xi) W ( u ) = W ( u ; ξ ) as in Lemma 7.2 , the function u ↦ W ( u ) u\mapsto W(u) u ↦ W ( u ) extends almost surely to a zero-free holomorphic function on D ′ D' D ′ satisfying W ( 1 ) > 0 W(1)>0 W ( 1 ) > 0 , and in the pairing model we have
( Y ^ n , ( X i ) i ≥ 1 ) ⟹ ( W , ( ξ i ) i ≥ 1 ) in distribution on H ( D ′ ) × Z ≥ 0 N . (9) (\widehat{Y}_n,(X_i)_{i\ge1})\Longrightarrow(W,(\xi_i)_{i\ge1})\quad\text{in distribution on }\mathcal{H}(D')\times\mathbb{Z}_{\ge0}^{\mathbb{N}}. \tag*{(9)} ( Y n , ( X i ) i ≥ 1 ) ⟹ ( W , ( ξ i ) i ≥ 1 ) in distribution on H ( D ′ ) × Z ≥ 0 N . (9) In particular, sup ∣ u − 1 ∣ ≤ ε / 4 ∣ Y ^ n ( u ) ∣ \sup_{|u-1|\le\varepsilon/4}|\widehat{Y}_n(u)| sup ∣ u − 1∣ ≤ ε /4 ∣ Y n ( u ) ∣ and sup ∣ u − 1 ∣ ≤ ε / 4 ∣ Y ^ n ′ ( u ) ∣ \sup_{|u-1|\le\varepsilon/4}|\widehat{Y}_n'(u)| sup ∣ u − 1∣ ≤ ε /4 ∣ Y n ′ ( u ) ∣ are O p ( 1 ) O_p(1) O p ( 1 ) , Y ^ n ( 1 ) ⇒ W ( 1 ) > 0 \widehat{Y}_n(1)\Rightarrow W(1)>0 Y n ( 1 ) ⇒ W ( 1 ) > 0 , and Y ^ n ( u n ) − Y ^ n ( 1 ) = O p ( ∣ u n − 1 ∣ ) \widehat{Y}_n(u_n)-\widehat{Y}_n(1)=O_p(|u_n-1|) Y n ( u n ) − Y n ( 1 ) = O p ( ∣ u n − 1∣ ) for every deterministic sequence u n → 1 u_n\to1 u n → 1 .
Proof. Note first that since ∣ δ i ( u ) − δ i ( 1 ) ∣ ≤ ∣ u − 1 ∣ ( d − 1 ) − i |\delta_i(u)-\delta_i(1)|\le|u-1|(d-1)^{-i} ∣ δ i ( u ) − δ i ( 1 ) ∣ ≤ ∣ u − 1∣ ( d − 1 ) − i and 1 + δ i ( 1 ) ≥ 1 − ( d − 1 ) − 1 > 0 1+\delta_i(1)\ge1-(d-1)^{-1}>0 1 + δ i ( 1 ) ≥ 1 − ( d − 1 ) − 1 > 0 , choosing ε > 0 \varepsilon>0 ε > 0 sufficiently small ensures 1 + δ i ( u ) ≠ 0 1+\delta_i(u)\ne0 1 + δ i ( u ) = 0 for all i ≥ 1 i\ge1 i ≥ 1 and ∣ u − 1 ∣ ≤ ε |u-1|\le\varepsilon ∣ u − 1∣ ≤ ε . The limit. As in the proof of Lemma 7.2 , log W ( u ) = ( u − 1 ) A + B + ∑ i ξ i ( log ( 1 + δ i ( u ) ) − δ i ( u ) ) \log W(u)=(u-1)A+B+\sum_i \xi_i(\log(1+\delta_i(u))-\delta_i(u)) log W ( u ) = ( u − 1 ) A + B + ∑ i ξ i ( log ( 1 + δ i ( u )) − δ i ( u )) , where A = ∑ i ( ξ i − λ i ) ( d − 1 ) − i A=\sum_i(\xi_i-\lambda_i)(d-1)^{-i} A = ∑ i ( ξ i − λ i ) ( d − 1 ) − i and B = ∑ i ( ξ i − λ i ) ( − 1 ) i ( d − 1 ) − i B=\sum_i(\xi_i-\lambda_i)(-1)^i(d-1)^{-i} B = ∑ i ( ξ i − λ i ) ( − 1 ) i ( d − 1 ) − i converge almost surely, and the remaining series converges absolutely and uniformly on D ‾ ( 1 , ε ) \overline{D}(1,\varepsilon) D ( 1 , ε ) (using principal logarithms; ∣ δ i ( u ) ∣ ≤ ( 1 + ε ) ( d − 1 ) − i ≤ 1 2 |\delta_i(u)|\leq(1+\varepsilon)(d-1)^{-i}\leq\frac{1}{2} ∣ δ i ( u ) ∣ ≤ ( 1 + ε ) ( d − 1 ) − i ≤ 2 1 for i ≥ 2 i\geq2 i ≥ 2 after shrinking ε \varepsilon ε , and the term i = 1 i=1 i = 1 is a single holomorphic function). Hence, W = e log W W=e^{\log W} W = e l o g W is almost surely holomorphic and zero-free on D ′ D' D ′ , and W ( 1 ) > 0 W(1)>0 W ( 1 ) > 0 .
Tightness. By Lemma 6.3, sup ∣ u − 1 ∣ ≤ ε E ∣ Y ^ n ( u ) ∣ 2 ≤ M \sup_{|u-1|\leq\varepsilon}\mathbb{E}|\widehat{Y}_n(u)|^2\leq M sup ∣ u − 1∣ ≤ ε E ∣ Y n ( u ) ∣ 2 ≤ M for all sufficiently large n n n , where M = M ( d , ε ) < ∞ M=M(d,\varepsilon)<\infty M = M ( d , ε ) < ∞ . For z ∈ D ′ z\in D' z ∈ D ′ , the disk D ( z , ε / 2 ) D(z,\varepsilon/2) D ( z , ε /2 ) is contained in D ‾ ( 1 , ε ) \overline{D}(1,\varepsilon) D ( 1 , ε ) , so the mean-value property of the holomorphic function Y ^ n \widehat{Y}_n Y n yields
∣ Y ^ n ( z ) ∣ ≤ 4 π ε 2 ∫ D ( z , ε / 2 ) ∣ Y ^ n ∣ d A ≤ 4 π ε 2 ∫ D ( 1 , ε ) ∣ Y ^ n ∣ d A . |\widehat{Y}_n(z)|\leq\frac{4}{\pi\varepsilon^2}\int_{D(z,\varepsilon/2)}|\widehat{Y}_n|\,dA\leq\frac{4}{\pi\varepsilon^2}\int_{D(1,\varepsilon)}|\widehat{Y}_n|\,dA. ∣ Y n ( z ) ∣ ≤ π ε 2 4 ∫ D ( z , ε /2 ) ∣ Y n ∣ d A ≤ π ε 2 4 ∫ D ( 1 , ε ) ∣ Y n ∣ d A .
hence
E sup z ∈ D ′ ∣ Y ^ n ( z ) ∣ ≤ 4 M . \mathbb{E}\sup_{z\in D'}|\widehat{Y}_n(z)|\leq4\sqrt{M}. E z ∈ D ′ sup ∣ Y n ( z ) ∣ ≤ 4 M .
By Markov’s inequality and Montel’s theorem (a locally bounded family is relatively compact in H ( D ′ ) \mathcal{H}(D') H ( D ′ ) ), the sequence of distributions of Y ^ n \widehat{Y}_n Y n is tight in H ( D ′ ) \mathcal{H}(D') H ( D ′ ) ; the distributions of ( X i ) i ≥ 1 (X_i)_{i\geq1} ( X i ) i ≥ 1 are tight in Z ≥ 0 N \mathbb{Z}_{\geq0}^{\mathbb{N}} Z ≥ 0 N since each coordinate converges. Thus, by Prohorov’s theorem, every subsequence of ( Y ^ n , ( X i ) ) (\widehat{Y}_n,(X_i)) ( Y n , ( X i )) possesses a further subsequence converging in distribution to some limit ( Y ^ ∞ , ( ξ i ) ) (\widehat{Y}_\infty,(\xi_i)) ( Y ∞ , ( ξ i )) , where the variables ( ξ i ) (\xi_i) ( ξ i ) are independent Poisson ( λ i ) \operatorname{Poisson}(\lambda_i) Poisson ( λ i ) by the classical short-cycle limit.
Identification of the limit. Fix a real u ∈ ( 1 − ε / 2 , 1 + ε / 2 ) u\in(1-\varepsilon/2,1+\varepsilon/2) u ∈ ( 1 − ε /2 , 1 + ε /2 ) . Evaluation at u u u is a continuous functional on H ( D ′ ) \mathcal{H}(D') H ( D ′ ) , so along the chosen subsequence, ( Y ^ n ( u ) , ( X i ) ) ⇒ ( Y ^ ∞ ( u ) , ( ξ i ) ) (\widehat{Y}_n(u),(X_i))\Rightarrow(\widehat{Y}_\infty(u),(\xi_i)) ( Y n ( u ) , ( X i )) ⇒ ( Y ∞ ( u ) , ( ξ i )) . On the other hand, Lemma 7.2 asserts that ( Y ^ n ( u ) , ( X i ) ) ⇒ ( W ( u ; ξ ) , ( ξ i ) ) (\widehat{Y}_n(u),(X_i))\Rightarrow(W(u;\xi),(\xi_i)) ( Y n ( u ) , ( X i )) ⇒ ( W ( u ; ξ ) , ( ξ i )) along the full sequence. The two limit distributions therefore coincide, and W ( u ; ξ ) W(u;\xi) W ( u ; ξ ) is a measurable function of ( ξ i ) (\xi_i) ( ξ i ) ; applying the equality of distributions to the bounded functional min { 1 , ∣ y − W ( u ; x ) ∣ } \min\{1,|y-W(u;x)|\} min { 1 , ∣ y − W ( u ; x ) ∣ } of ( y , x ) (y,x) ( y , x ) gives E min { 1 , ∣ Y ^ ∞ ( u ) − W ( u ; ξ ) ∣ } = 0 \mathbb{E}\min\{1,|\widehat{Y}_\infty(u)-W(u;\xi)|\}=0 E min { 1 , ∣ Y ∞ ( u ) − W ( u ; ξ ) ∣ } = 0 , that is, Y ^ ∞ ( u ) = W ( u ; ξ ) \widehat{Y}_\infty(u)=W(u;\xi) Y ∞ ( u ) = W ( u ; ξ ) almost surely. Taking u u u in a countable dense subset of the real interval, the almost surely holomorphic function Y ^ ∞ − W ( ⋅ ; ξ ) \widehat{Y}_\infty-W(\cdot;\xi) Y ∞ − W ( ⋅ ; ξ ) vanishes on a set having an accumulation point in D ′ D' D ′ , and thus vanishes identically on D ′ D' D ′ by the identity theorem. Consequently, every subsequential limit is ( W , ( ξ i ) ) (W,(\xi_i)) ( W , ( ξ i )) , which establishes (9) .
Consequences. The functionals f ↦ sup ∣ u − 1 ∣ ≤ ε / 4 ∣ f ∣ f\mapsto\sup_{|u-1|\leq\varepsilon/4}|f| f ↦ sup ∣ u − 1∣ ≤ ε /4 ∣ f ∣ , f ↦ sup ∣ u − 1 ∣ ≤ ε / 4 ∣ f ′ ∣ f\mapsto\sup_{|u-1|\leq\varepsilon/4}|f'| f ↦ sup ∣ u − 1∣ ≤ ε /4 ∣ f ′ ∣ , and f ↦ f ( 1 ) f\mapsto f(1) f ↦ f ( 1 ) are continuous on H ( D ′ ) \mathcal{H}(D') H ( D ′ ) (by Cauchy’s estimate for the second); hence, by the continuous mapping theorem, these three quantities converge in distribution to the corresponding almost surely finite functionals of W W W . Convergence in distribution to a finite limit implies tightness, that is, boundedness in probability O p ( 1 ) O_p(1) O p ( 1 ) . Finally, ∣ Y ^ n ( u n ) − Y ^ n ( 1 ) ∣ ≤ ∣ u n − 1 ∣ sup ∣ u − 1 ∣ ≤ ε / 4 ∣ Y ^ n ′ ( u ) ∣ |\widehat{Y}_n(u_n)-\widehat{Y}_n(1)|\leq|u_n-1|\sup_{|u-1|\leq\varepsilon/4}|\widehat{Y}_n'(u)| ∣ Y n ( u n ) − Y n ( 1 ) ∣ ≤ ∣ u n − 1∣ sup ∣ u − 1∣ ≤ ε /4 ∣ Y n ′ ( u ) ∣ as soon as ∣ u n − 1 ∣ ≤ ε / 4 |u_n-1|\leq\varepsilon/4 ∣ u n − 1∣ ≤ ε /4 . ▫
Conditional mean, central limit theorem, and variance
Theorem 7.4. Fix d ≥ 3 d \ge3 d ≥ 3 . Let G G G be a uniformly random simple d d d -regular graph on n n n vertices, and let X X X be the number of cycles of a uniformly random 2 2 2 -factor of G G G . With μ n p a i r = 1 2 log n + γ 2 + log 2 \mu_n^{\mathrm{pair}} = \frac{1}{2}\log n + \frac{\gamma}{2} + \log2 μ n pair = 2 1 log n + 2 γ + log 2 as in Corollary 3.5 , write
μ n = μ n p a i r − 3 4 = 1 2 log n + γ 2 + log 2 − 3 4 . \mu_n = \mu_n^{\mathrm{pair}} - \frac{3}{4} = \frac{1}{2}\log n + \frac{\gamma}{2} + \log2 - \frac{3}{4}. μ n = μ n pair − 4 3 = 2 1 log n + 2 γ + log 2 − 4 3 . Let ( ξ i ) i ≥ 3 (\xi_i)_{i\ge3} ( ξ i ) i ≥ 3 be independent Poisson( λ i ) (\lambda_i) ( λ i ) variables, the distributional limits of ( X i ) i ≥ 3 (X_i)_{i\ge3} ( X i ) i ≥ 3 , and let W ≥ 3 ( u ) = ∏ i ≥ 3 ( 1 + δ i ( u ) ) ξ i e − λ i δ i ( u ) W_{\ge3}(u) = \prod_{i\ge3}(1+\delta_i(u))^{\xi_i}e^{-\lambda_i\delta_i(u)} W ≥ 3 ( u ) = ∏ i ≥ 3 ( 1 + δ i ( u ) ) ξ i e − λ i δ i ( u ) be the product of Lemma 7.2 truncated at i ≥ 3 i \ge3 i ≥ 3 . Then
E [ X ∣ G ] − μ n ⟹ ∂ u log W ≥ 3 ( u ) ∣ u = 1 in distribution. \mathbb{E}[X \mid G] - \mu_n \ \Longrightarrow\ \left.\partial_u \log W_{\ge3}(u)\right|_{u=1}
\qquad\text{in distribution.} E [ X ∣ G ] − μ n ⟹ ∂ u log W ≥ 3 ( u ) ∣ u = 1 in distribution. The right-hand side equals
∑ i ≥ 3 ( ξ i ( d − 1 ) − i 1 + ( − 1 ) i ( d − 1 ) − i − 1 2 i ) . \sum_{i\ge3}\left(\xi_i\frac{(d-1)^{-i}}{1+(-1)^i(d-1)^{-i}}-\frac{1}{2i}\right). i ≥ 3 ∑ ( ξ i 1 + ( − 1 ) i ( d − 1 ) − i ( d − 1 ) − i − 2 i 1 ) . The series converges almost surely and has finite variance
∑ i ≥ 3 λ i δ i ′ ( 1 ) 2 ( 1 + δ i ( 1 ) ) 2 = ∑ i ≥ 3 ( d − 1 ) − i 2 i 1 ( 1 + ( − 1 ) i ( d − 1 ) − i ) 2 < ∞ . (10) \sum_{i\ge3}\lambda_i\frac{\delta_i'(1)^2}{(1+\delta_i(1))^2}
=
\sum_{i\ge3}\frac{(d-1)^{-i}}{2i}\frac{1}{\left(1+(-1)^i(d-1)^{-i}\right)^2}
<\infty. \tag*{(10)} i ≥ 3 ∑ λ i ( 1 + δ i ( 1 ) ) 2 δ i ′ ( 1 ) 2 = i ≥ 3 ∑ 2 i ( d − 1 ) − i ( 1 + ( − 1 ) i ( d − 1 ) − i ) 2 1 < ∞. (10) In particular, E [ X ∣ G ] = 1 2 log n + γ 2 + log 2 − 3 4 + O p ( 1 ) \mathbb{E}[X\mid G]=\frac{1}{2}\log n+\frac{\gamma}{2}+\log2-\frac{3}{4}+O_p(1) E [ X ∣ G ] = 2 1 log n + 2 γ + log 2 − 4 3 + O p ( 1 ) : for every ϵ > 0 \epsilon>0 ϵ > 0 , there exists C = C ( d , ϵ ) < ∞ C=C(d,\epsilon)<\infty C = C ( d , ϵ ) < ∞ such that
P ( ∣ E [ X ∣ G ] − μ n ∣ ≤ C ) ≥ 1 − ϵ (11) \mathbb{P}\left(\left|\mathbb{E}[X\mid G]-\mu_n\right|\le C\right)\ge1-\epsilon \tag*{(11)} P ( ∣ E [ X ∣ G ] − μ n ∣ ≤ C ) ≥ 1 − ϵ (11) for all sufficiently large $n.
Proof. Under the conditional distribution of a uniform 2-factor of the fixed graph G G G ,
E [ u X ∣ G ] = Z ( u ) Z ( 1 ) . \mathbb{E}[u^X\mid G]=\frac{Z(u)}{Z(1)}. E [ u X ∣ G ] = Z ( 1 ) Z ( u ) .
E [ X ∣ G ] = ∂ u log Z ( u ) ∣ u = 1 = ∂ u log E Z ( u ) ∣ u = 1 + Y ^ n ′ ( 1 ) Y ^ n ( 1 ) , \mathbb{E}[X\mid G]=\left.\partial_u\log Z(u)\right|_{u=1}
=\left.\partial_u\log\mathbb{E}Z(u)\right|_{u=1}+\frac{\widehat{Y}_n'(1)}{\widehat{Y}_n(1)}, E [ X ∣ G ] = ∂ u log Z ( u ) ∣ u = 1 = ∂ u log E Z ( u ) ∣ u = 1 + Y n ( 1 ) Y n ′ ( 1 ) ,
with Y ^ n ( u ) = Z ( u ) / E Z ( u ) \widehat{Y}_n(u)=Z(u)/\mathbb{E}Z(u) Y n ( u ) = Z ( u ) / E Z ( u ) as defined in Lemma 7.3 ; the final identity follows from log Z ( u ) = log E Z ( u ) + log Y ^ n ( u ) \log Z(u)=\log\mathbb{E}Z(u)+\log\widehat{Y}_n(u) log Z ( u ) = log E Z ( u ) + log Y n ( u ) , valid near u = 1 u=1 u = 1 where Y ^ n ( 1 ) = Z / E Z > 0 \widehat{Y}_n(1)=Z/\mathbb{E}Z>0 Y n ( 1 ) = Z / E Z > 0 . In the pairing model, E Z ( u ) / E Z ( 1 ) = E u X \mathbb{E}Z(u)/\mathbb{E}Z(1)=\mathbb{E}_{u}X E Z ( u ) / E Z ( 1 ) = E u X is the generating function given by Theorem 3.3 , so that
∂ u log E Z ( u ) ∣ u = 1 = E X = μ n p a i r + o ( 1 ) . (12) \left.\partial_u\log\mathbb{E}Z(u)\right|_{u=1}
=\mathbb{E}X=\mu_n^{\mathrm{pair}}+o(1). \tag*{(12)} ∂ u log E Z ( u ) ∣ u = 1 = E X = μ n pair + o ( 1 ) . (12)
Pairing model. The map Φ ( f ) = f ′ ( 1 ) / f ( 1 ) \Phi(f)=f'(1)/f(1) Φ ( f ) = f ′ ( 1 ) / f ( 1 ) is continuous on the open subset { f ( 1 ) ≠ 0 } \{f(1)\ne0\} { f ( 1 ) = 0 } of H ( D ′ ) \mathcal{H}(D') H ( D ′ ) , and W ( 1 ) > 0 W(1)>0 W ( 1 ) > 0 almost surely. By (9) and the continuous mapping theorem,
( E [ X ∣ G ] − μ n p a i r , ( X i ) i ≥ 1 ) ⟹ ( ∂ u log W ( u ) ∣ u = 1 , ( ξ i ) i ≥ 1 ) , \left(\mathbb{E}[X\mid G]-\mu_n^{\mathrm{pair}},(X_i)_{i\ge1}\right)
\Longrightarrow
\left(\left.\partial_u\log W(u)\right|_{u=1},(\xi_i)_{i\ge1}\right), ( E [ X ∣ G ] − μ n pair , ( X i ) i ≥ 1 ) ⟹ ( ∂ u log W ( u ) ∣ u = 1 , ( ξ i ) i ≥ 1 ) ,
∂ u log W ( 1 ) = ∑ i ≥ 1 ( ξ i δ i ′ ( 1 ) 1 + δ i ( 1 ) − λ i δ i ′ ( 1 ) ) . \partial_u\log W(1)=\sum_{i\ge1}\left(\xi_i\frac{\delta_i'(1)}{1+\delta_i(1)}-\lambda_i\delta_i'(1)\right). ∂ u log W ( 1 ) = i ≥ 1 ∑ ( ξ i 1 + δ i ( 1 ) δ i ′ ( 1 ) − λ i δ i ′ ( 1 ) ) .
Simple graphs. Conditioning the pairing on simplicity corresponds to conditioning on the event { X 1 = X 2 = 0 } \{X_1=X_2=0\} { X 1 = X 2 = 0 } , which is determined by two discrete coordinates of the second component and has limiting probability e − λ 1 − λ 2 > 0 e^{-\lambda_1-\lambda_2}>0 e − λ 1 − λ 2 > 0 . The joint convergence in distribution therefore transfers to the conditional distributions: conditionally on simplicity, E [ X ∣ G ] − μ n p a i r \mathbb{E}[X\mid G]-\mu_n^{\mathrm{pair}} E [ X ∣ G ] − μ n pair converges in distribution to ∂ u log W ( 1 ) \partial_u\log W(1) ∂ u log W ( 1 ) conditioned on ξ 1 = ξ 2 = 0 \xi_1=\xi_2=0 ξ 1 = ξ 2 = 0 . On this event, the terms for i = 1 , 2 i=1,2 i = 1 , 2 are deterministic,
− λ 1 δ 1 ′ ( 1 ) − λ 2 δ 2 ′ ( 1 ) = − 1 2 − 1 4 = − 3 4 , -\lambda_1\delta_1'(1)-\lambda_2\delta_2'(1)=-\frac{1}{2}-\frac{1}{4}=-\frac{3}{4}, − λ 1 δ 1 ′ ( 1 ) − λ 2 δ 2 ′ ( 1 ) = − 2 1 − 4 1 = − 4 3 ,
and the remaining sum is ∂ u log W ≥ 3 ( 1 ) \partial_u\log W_{\ge3}(1) ∂ u log W ≥ 3 ( 1 ) , whose summands involve only ( ξ i ) i ≥ 3 (\xi_i)_{i\ge3} ( ξ i ) i ≥ 3 and are independent of ( ξ 1 , ξ 2 ) (\xi_1,\xi_2) ( ξ 1 , ξ 2 ) . Since μ n = μ n p a i r − 3 4 \mu_n=\mu_n^{\mathrm{pair}}-\frac{3}{4} μ n = μ n pair − 4 3 , this establishes the convergence in distribution.
The limit. The series converges almost surely and has variance (10) by the calculation in Lemma 7.2, as the summands are independent with Var ( ξ i ) = λ i \operatorname{Var}(\xi_i)=\lambda_i Var ( ξ i ) = λ i . Convergence in distribution to an almost surely finite limit implies tightness, which yields (11) with C = C ( d , ϵ ) C=C(d,\epsilon) C = C ( d , ϵ ) chosen as any constant exceeding the ( 1 − ϵ / 2 ) (1-\epsilon/2) ( 1 − ϵ /2 ) -quantile of the absolute value of the series. Because ξ 3 \xi_3 ξ 3 is unbounded, the series is likewise unbounded, so no deterministic constant C C C can hold with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) : the fluctuation of E [ X ∣ G ] \mathbb{E}[X\mid G] E [ X ∣ G ] about μ n \mu_n μ n is of order one and is governed by the short cycles of G G G .
Theorem 7.5. Fix d ≥ 3 d\ge3 d ≥ 3 and let G G G be a uniformly random simple d d d -regular graph on n n n vertices. If X X X is the number of cycles of a uniformly random 2 2 2 -factor of G G G , then
X − μ n σ n ∣ G ⟹ N ( 0 , 1 ) \left.\frac{X-\mu_n}{\sigma_n}\right|G\Longrightarrow N(0,1) σ n X − μ n G ⟹ N ( 0 , 1 ) in probability (that is, for every bounded continuous function h h h , E [ h ( ( X − μ n ) / σ n ) ∣ G ] → E h ( N ) \mathbb{E}[h((X-\mu_n)/\sigma_n)\mid G]\to\mathbb{E}h(N) E [ h (( X − μ n ) / σ n ) ∣ G ] → E h ( N ) in probability over G G G , where N ∼ N ( 0 , 1 ) N\sim N(0,1) N ∼ N ( 0 , 1 ) ), with
μ n = 1 2 log n + γ 2 + log 2 − 3 4 , σ n = 1 2 log n . \mu_n=\frac{1}{2}\log n+\frac{\gamma}{2}+\log2-\frac{3}{4},\qquad\sigma_n=\sqrt{\frac{1}{2}\log n}. μ n = 2 1 log n + 2 γ + log 2 − 4 3 , σ n = 2 1 log n .
Proof. We work in the pairing model with the exact centering m n = E X m_n=\mathbb{E}X m n = E X for a uniform pair from Corollary 3.5; the transfer to simple graphs G ( n , d ) G(n,d) G ( n , d ) and to the centering m n m_n m n is carried out at the end. Fix t ∈ R t \in\mathbb{R} t ∈ R and set u n = exp ( i t / σ n ) u_n=\exp(it/\sigma_n) u n = exp ( i t / σ n ) , so that ∣ u n − 1 ∣ = O ( 1 / σ n ) → 0 |u_n-1|=O(1/\sigma_n)\to0 ∣ u n − 1∣ = O ( 1/ σ n ) → 0 . The conditional characteristic function given G G G is
ϕ G ( t ) : = E [ exp ( i t ( X − m n ) σ n ) | G ] = e − i t m n / σ n Z ( u n ) Z ( 1 ) = [ e − i t m n / σ n E Z ( u n ) E Z ( 1 ) ] ⋅ Y ^ n ( u n ) Y ^ n ( 1 ) . (13) \begin{aligned}
\phi_G(t):=\mathbb{E}\left[\exp\left(\frac{it(X-m_n)}{\sigma_n}\right)\,\middle|\,G\right] \\
&=e^{-itm_n/\sigma_n}\frac{Z(u_n)}{Z(1)} \\
&=\left[e^{-itm_n/\sigma_n}\frac{\mathbb{E}Z(u_n)}{\mathbb{E}Z(1)}\right]\cdot\frac{\widehat{Y}_n(u_n)}{\widehat{Y}_n(1)}. \tag*{(13)}
\end{aligned} ϕ G ( t ) := E [ exp ( σ n i t ( X − m n ) ) G ] = e − i t m n / σ n Z ( 1 ) Z ( u n ) = [ e − i t m n / σ n E Z ( 1 ) E Z ( u n ) ] ⋅ Y n ( 1 ) Y n ( u n ) . (13)
The bracketed factor is the characteristic function of ( X − m n ) / σ n (X-m_n)/\sigma_n ( X − m n ) / σ n for a uniform pair; by (2) with s = i t / σ n s=it/\sigma_n s = i t / σ n , it equals
exp ( − 1 2 v n t 2 / σ n 2 + O ( ∣ t ∣ 2 σ n − 3 log n ) ) ⟶ e − t 2 / 2 , \exp\left(-\frac{1}{2}v_n t^2/\sigma_n^2+O(|t|^2\sigma_n^{-3}\log n)\right)\longrightarrow e^{-t^2/2}, exp ( − 2 1 v n t 2 / σ n 2 + O ( ∣ t ∣ 2 σ n − 3 log n ) ) ⟶ e − t 2 /2 ,
since v n / σ n 2 → 1 v_n/\sigma_n^2\to1 v n / σ n 2 → 1 and σ n − 3 log n = O ( ( log n ) − 1 / 2 ) \sigma_n^{-3}\log n=O((\log n)^{-1/2}) σ n − 3 log n = O (( log n ) − 1/2 ) . For the random factor, Lemma 7.3 yields Y ^ n ( u n ) − Y ^ n ( 1 ) = O p ( σ n − 1 ) \widehat{Y}_n(u_n)-\widehat{Y}_n(1)=O_p(\sigma_n^{-1}) Y n ( u n ) − Y n ( 1 ) = O p ( σ n − 1 ) and Y ^ n ( 1 ) ⇒ W ( 1 ) > 0 \widehat{Y}_n(1)\Rightarrow W(1)>0 Y n ( 1 ) ⇒ W ( 1 ) > 0 , whence 1 / Y ^ n ( 1 ) = O p ( 1 ) 1/\widehat{Y}_n(1)=O_p(1) 1/ Y n ( 1 ) = O p ( 1 ) and
Y ^ n ( u n ) Y ^ n ( 1 ) = 1 + O p ( σ n − 1 ) ⟶ 1 \frac{\widehat{Y}_n(u_n)}{\widehat{Y}_n(1)}=1+O_p(\sigma_n^{-1})\longrightarrow1 Y n ( 1 ) Y n ( u n ) = 1 + O p ( σ n − 1 ) ⟶ 1
in probability.
Fix T < ∞ T<\infty T < ∞ . Uniformly for ∣ t ∣ ≤ T |t|\le T ∣ t ∣ ≤ T , (2) with s = i t / σ n s=it/\sigma_n s = i t / σ n gives
[ e − i t m n / σ n E Z ( e i t / σ n ) E Z ( 1 ) ] = exp ( − 1 2 v n t 2 / σ n 2 + O T ( σ n − 3 log n ) ) , \left[e^{-itm_n/\sigma_n}\frac{\mathbb{E}Z(e^{it/\sigma_n})}{\mathbb{E}Z(1)}\right]
=\exp\left(-\frac{1}{2}v_n t^2/\sigma_n^2+O_T(\sigma_n^{-3}\log n)\right), [ e − i t m n / σ n E Z ( 1 ) E Z ( e i t / σ n ) ] = exp ( − 2 1 v n t 2 / σ n 2 + O T ( σ n − 3 log n ) ) ,
which converges uniformly to e − t 2 / 2 e^{-t^2/2} e − t 2 /2 , since v n / σ n 2 → 1 v_n/\sigma_n^2\to1 v n / σ n 2 → 1 and σ n − 3 log n → 0 \sigma_n^{-3}\log n\to0 σ n − 3 log n → 0 . For all large n n n the points e i t / σ n e^{it/\sigma_n} e i t / σ n with ∣ t ∣ ≤ T |t|\le T ∣ t ∣ ≤ T lie in ∣ u − 1 ∣ ≤ ε / 4 |u-1|\le\varepsilon/4 ∣ u − 1∣ ≤ ε /4 , so Lemma 7.3 yields
sup ∣ t ∣ ≤ T ∣ Y ^ n ( e i t / σ n ) − Y ^ n ( 1 ) ∣ ≤ sup ∣ u − 1 ∣ ≤ ε / 4 ∣ Y ^ n ′ ( u ) ∣ sup ∣ t ∣ ≤ T ∣ e i t / σ n − 1 ∣ = O p ( σ n − 1 ) . \sup_{|t|\le T}\left|\widehat{Y}_n(e^{it/\sigma_n})-\widehat{Y}_n(1)\right|
\le
\sup_{|u-1|\le\varepsilon/4}|\widehat{Y}'_n(u)|
\sup_{|t|\le T}|e^{it/\sigma_n}-1|
=O_p(\sigma_n^{-1}). ∣ t ∣ ≤ T sup Y n ( e i t / σ n ) − Y n ( 1 ) ≤ ∣ u − 1∣ ≤ ε /4 sup ∣ Y n ′ ( u ) ∣ ∣ t ∣ ≤ T sup ∣ e i t / σ n − 1∣ = O p ( σ n − 1 ) .
Together with Y ^ n ( 1 ) ⇒ W ( 1 ) > 0 \widehat{Y}_n(1)\Rightarrow W(1)>0 Y n ( 1 ) ⇒ W ( 1 ) > 0 , this gives
sup ∣ t ∣ ≤ T ∣ Y ^ n ( e i t / σ n ) Y ^ n ( 1 ) − 1 ∣ = o p ( 1 ) , \sup_{|t|\le T}\left|\frac{\widehat{Y}_n(e^{it/\sigma_n})}{\widehat{Y}_n(1)}-1\right|=o_p(1), ∣ t ∣ ≤ T sup Y n ( 1 ) Y n ( e i t / σ n ) − 1 = o p ( 1 ) ,
and therefore
sup ∣ t ∣ ≤ T ∣ ϕ G ( t ) − e − t 2 / 2 ∣ ⟶ 0 \sup_{|t|\le T}\left|\phi_G(t)-e^{-t^2/2}\right|\longrightarrow0 ∣ t ∣ ≤ T sup ϕ G ( t ) − e − t 2 /2 ⟶ 0
in probability.
Along any subsequence, a diagonal extraction produces a further subsequence on which this convergence holds almost surely for every integer T T T . For almost every such graph sequence the conditional characteristic functions converge pointwise on R \mathbb{R} R to e − t 2 / 2 e^{-t^2/2} e − t 2 /2 , which is continuous at the origin, so Lévy’s continuity theorem yields
L ( ( X − m n ) / σ n ∣ G ) ⇒ N ( 0 , 1 ) \mathcal{L}\left((X-m_n)/\sigma_n \mid G\right) \Rightarrow N(0,1) L ( ( X − m n ) / σ n ∣ G ) ⇒ N ( 0 , 1 )
almost surely along that further subsequence. Tightness is part of this conclusion. Since every subsequence has such a further subsequence, the conditional distributions converge weakly to N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) in probability along the full sequence.
Transfer. Conditioning on simplicity preserves every o p ( 1 ) o_p(1) o p ( 1 ) and O p ( 1 ) O_p(1) O p ( 1 ) asymptotic statement above ((Lemma 5.3)), and no short-cycle factors appear in (13) other than through Y n Y_n Y n , so no adjustments for i = 1 , 2 i=1,2 i = 1 , 2 are needed. Finally, m n − μ n = 3 4 + o ( 1 ) = O ( 1 ) m_n-\mu_n=\frac{3}{4}+o(1)=O(1) m n − μ n = 4 3 + o ( 1 ) = O ( 1 ) , so replacing the centering sequence m n m_n m n by μ n \mu_n μ n alters ( X − m n ) / σ n (X-m_n)/\sigma_n ( X − m n ) / σ n by an error of O ( σ n − 1 ) → 0 O(\sigma_n^{-1})\to0 O ( σ n − 1 ) → 0 . (Similarly, centering at the conditional mean E [ X ∣ G ] = μ n + O p ( 1 ) \mathbb{E}[X\mid G]=\mu_n+O_p(1) E [ X ∣ G ] = μ n + O p ( 1 ) of Theorem 7.4 shifts the normalised variable by O p ( σ n − 1 ) O_p(\sigma_n^{-1}) O p ( σ n − 1 ) and does not affect the limiting distribution.)
Proposition 7.6. Under the hypotheses of Theorem 7.5 ,
Var ( X ∣ G ) = σ n 2 ( 1 + o p ( 1 ) ) . \operatorname{Var}(X\mid G)=\sigma_n^2(1+o_p(1)). Var ( X ∣ G ) = σ n 2 ( 1 + o p ( 1 )) .
Proof. Work first in the pairing model. Let P n P_n P n be the uniform distribution on pairings, and let Q n Q_n Q n be the distribution on pairings with density d Q n / d P n = Y ^ n ( 1 ) = Z ( 1 ) / E Z ( 1 ) dQ_n/dP_n=\widehat{Y}_n(1)=Z(1)/\mathbb{E}Z(1) d Q n / d P n = Y n ( 1 ) = Z ( 1 ) / E Z ( 1 ) . The proof of Theorem 7.5 gives ( X − m n ) / σ n ∣ G ⇒ N ( 0 , 1 ) (X-m_n)/\sigma_n\mid G\Rightarrow N(0,1) ( X − m n ) / σ n ∣ G ⇒ N ( 0 , 1 ) in P n P_n P n -probability. Set V n = Var ( X ∣ G ) / σ n 2 V_n=\operatorname{Var}(X\mid G)/\sigma_n^2 V n = Var ( X ∣ G ) / σ n 2 .
Lower bound. Fix ε > 0 \varepsilon>0 ε > 0 and set f K ( x ) = min ( x 2 , K 2 ) f_K(x)=\min(x^2,K^2) f K ( x ) = min ( x 2 , K 2 ) . Choose K K K so that E f K ( N ) ≥ 1 − ε / 2 \mathbb{E}f_K(N)\ge1-\varepsilon/2 E f K ( N ) ≥ 1 − ε /2 , where N ∼ N ( 0 , 1 ) N\sim N(0,1) N ∼ N ( 0 , 1 ) . Then
M n , K : = E [ f K ( X − m n σ n ) | G ] ⟶ E f K ( N ) M_{n,K}:=\mathbb{E}\left[f_K\left(\frac{X-m_n}{\sigma_n}\right)\middle|G\right]\longrightarrow\mathbb{E}f_K(N) M n , K := E [ f K ( σ n X − m n ) G ] ⟶ E f K ( N )
in P n P_n P n -probability. By the pairing-model step in the proof of Theorem 7.4 , E [ X ∣ G ] − m n = O p ( 1 ) \mathbb{E}[X\mid G]-m_n=O_p(1) E [ X ∣ G ] − m n = O p ( 1 ) . Writing
r n = ( E [ X ∣ G ] − m n σ n ) 2 , r_n=\left(\frac{\mathbb{E}[X\mid G]-m_n}{\sigma_n}\right)^2, r n = ( σ n E [ X ∣ G ] − m n ) 2 ,
one has r n = o p ( 1 ) r_n=o_p(1) r n = o p ( 1 ) under P n P_n P n and E [ ( ( X − m n ) / σ n ) 2 ∣ G ] = V n + r n \mathbb{E}[((X-m_n)/\sigma_n)^2\mid G]=V_n+r_n E [(( X − m n ) / σ n ) 2 ∣ G ] = V n + r n . Since f K ( x ) ≤ x 2 f_K(x)\le x^2 f K ( x ) ≤ x 2 , the event { V n < 1 − ε } \{V_n<1-\varepsilon\} { V n < 1 − ε } is contained in { M n , K < 1 − 3 ε / 4 } ∪ { r n > ε / 4 } \{M_{n,K}<1-3\varepsilon/4\}\cup\{r_n>\varepsilon/4\} { M n , K < 1 − 3 ε /4 } ∪ { r n > ε /4 } , and both of those probabilities tend to zero under P n P_n P n . Thus
P P n ( V n < 1 − ε ) ⟶ 0. P_{P_n}(V_n<1-\varepsilon)\longrightarrow0. P P n ( V n < 1 − ε ) ⟶ 0.
Contiguity. By Lemma 7.2, Y ^ n ( 1 ) ⇒ W ( 1 ) \widehat{Y}_n(1)\Rightarrow W(1) Y n ( 1 ) ⇒ W ( 1 ) with W ( 1 ) > 0 W(1)>0 W ( 1 ) > 0 almost surely and E W ( 1 ) = 1 \mathbb{E}W(1)=1 E W ( 1 ) = 1 . Since also E P n Y ^ n ( 1 ) = 1 \mathbb{E}_{P_n}\widehat{Y}_n(1)=1 E P n Y n ( 1 ) = 1 , these densities are uniformly integrable, so every event of vanishing P n P_n P n -probability has vanishing Q n Q_n Q n -probability. Conversely, if Q n ( A n ) → 0 Q_n(A_n) \to0 Q n ( A n ) → 0 , then for every η > 0 \eta> 0 η > 0
P n ( A n ) ≤ P n ( Y ~ n ( 1 ) ≤ η ) + η − 1 Q n ( A n ) ; P_n(A_n) \le P_n(\widetilde{Y}_n(1) \le\eta) + \eta^{-1}Q_n(A_n); P n ( A n ) ≤ P n ( Y n ( 1 ) ≤ η ) + η − 1 Q n ( A n ) ;
letting n → ∞ n \to\infty n → ∞ and then η ↓ 0 \eta\downarrow0 η ↓ 0 gives P n ( A n ) → 0 P_n(A_n) \to0 P n ( A n ) → 0 , because Y ~ n ( 1 ) ⇒ W ( 1 ) > 0 \widetilde{Y}_n(1) \Rightarrow W(1) > 0 Y n ( 1 ) ⇒ W ( 1 ) > 0 . The two distributions are mutually contiguous.
Upper bound. The uniform pair of Corollary 3.4 has graph marginal Q n Q_n Q n , and the conditional distribution of X X X given G G G is the one already used. The law of total variance therefore yields E Q n V n ≤ Var X / σ n 2 = 1 + O ( 1 / log n ) \mathbb{E}_{Q_n} V_n \le\operatorname{Var} X/\sigma_n^2 = 1 + O(1/\log n) E Q n V n ≤ Var X / σ n 2 = 1 + O ( 1/ log n ) , where Var X \operatorname{Var} X Var X is the variance for a uniform pair. Contiguity transfers the lower tail, so P Q n ( V n < 1 − ε ) → 0 P_{Q_n}(V_n < 1 - \varepsilon) \to0 P Q n ( V n < 1 − ε ) → 0 . Since 0 ≤ ( 1 − V n ) + ≤ 1 0 \le(1 - V_n)_+ \le1 0 ≤ ( 1 − V n ) + ≤ 1 ,
E Q n ( V n − 1 ) + = E Q n ( V n − 1 ) + E Q n ( 1 − V n ) + ≤ O ( 1 / log n ) + ε + o ( 1 ) . \mathbb{E}_{Q_n}(V_n - 1)_+ = \mathbb{E}_{Q_n}(V_n - 1) + \mathbb{E}_{Q_n}(1 - V_n)_+ \le O(1/\log n) + \varepsilon+ o(1). E Q n ( V n − 1 ) + = E Q n ( V n − 1 ) + E Q n ( 1 − V n ) + ≤ O ( 1/ log n ) + ε + o ( 1 ) .
As ε > 0 \varepsilon> 0 ε > 0 is arbitrary, E Q n ( V n − 1 ) + → 0 \mathbb{E}_{Q_n}(V_n - 1)_+ \to0 E Q n ( V n − 1 ) + → 0 , and Markov’s inequality gives P Q n ( V n > 1 + δ ) → 0 P_{Q_n}(V_n > 1 + \delta) \to0 P Q n ( V n > 1 + δ ) → 0 for every δ > 0 \delta> 0 δ > 0 . Reverse contiguity returns this upper tail to P n P_n P n . Combining the upper and lower tails under P n P_n P n yields V n → 1 V_n \to1 V n → 1 in P n P_n P n -probability, and Lemma 5.3 transfers the conclusion to simple graphs. □
Acknowledgements
We thank Guy Blachar and other colleagues for comments on earlier drafts of this paper.
AI Usage Statement: During the preparation of this manuscript, the authors used Google Gemini (Argon) to assist with language editing and clarity, xAI (Grok 4.6) to generate Figure 1 and the C++ code, and Anthropic Claude (Fable 5.2) to verify the mathematical proofs. The authors thoroughly reviewed, tested, and validated all AI-generated code, figures, and proof checks prior to incorporation and take full responsibility for the accuracy and contents of the paper.
Asymptotics of the second moment
This appendix gives the full proof of Proposition 6.2 .
Proof of Proposition 6.2. We work throughout with the multigraph (pairing) expectations of (3) and Theorem 6.1. Both E Z ( u ) \mathbb{E}Z(u) E Z ( u ) and ∑ P Z ( u , P ) 2 \sum_P Z(u,P)^2 ∑ P Z ( u , P ) 2 are entire in u u u for each fixed n n n (finite sums of monomials u X ( F ) u^{X(F)} u X ( F ) ), so R n ( u ) R_n(u) R n ( u ) is meromorphic; on a small disk about u = 1 u = 1 u = 1 one has E Z ( u ) ≠ 0 \mathbb{E}Z(u) \ne0 E Z ( u ) = 0 for large n n n by the first-moment formula (3), hence R n R_n R n is holomorphic there.
Normalisation. Write N ( d n ) = M ( d n ) N(dn) = M(dn) N ( d n ) = M ( d n ) . Then
R n ( u ) = N ( d n ) ∑ P Z ( u , P ) 2 ( ∑ P Z ( u , P ) ) 2 . R_n(u) = \frac{N(dn)\sum_P Z(u,P)^2}{\left(\sum_P Z(u,P)\right)^2}. R n ( u ) = ( ∑ P Z ( u , P ) ) 2 N ( d n ) ∑ P Z ( u , P ) 2 .
Substituting Theorem 6.1 and ∑ P Z ( u , P ) = n ! [ x n ] ( 1 − x ) − u / 2 a n M ( ( d − 2 ) n ) \sum_{\mathcal{P}} Z(u,\mathcal{P}) = n^{-u/2}a^nM((d-2)n) ∑ P Z ( u , P ) = n ! [ x n ] ( 1 − x ) − u /2 a n M (( d − 2 ) n ) with a = d ( d − 1 ) a=d(d-1) a = d ( d − 1 ) yields an explicit sum over lattice points ( n 0 , p ) ∈ Z ≥ 0 2 (n_0,p)\in\mathbb{Z}_{\geq0}^2 ( n 0 , p ) ∈ Z ≥ 0 2 . The summand vanishes unless n − n 0 − 2 p ≥ 0 n-n_0-2p\geq0 n − n 0 − 2 p ≥ 0 , so the support is the triangle
Δ : = { α , β ≥ 0 : α + 2 β ≤ 1 } , α : = n 0 / n , β : = p / n . \Delta:= \{\alpha,\beta\geq0:\ \alpha+2\beta\leq1\},\qquad\alpha:=n_0/n,\quad\beta:=p/n. Δ := { α , β ≥ 0 : α + 2 β ≤ 1 } , α := n 0 / n , β := p / n .
Write σ : = 1 − α − β \sigma:=1-\alpha-\beta σ := 1 − α − β , γ ^ : = 1 − α − 2 β \hat{\gamma}:=1-\alpha-2\beta γ ^ := 1 − α − 2 β (where the hat distinguishes this proportion from Euler’s constant γ \gamma γ ), τ : = d − 2 − 2 α − 2 β \tau:=d-2-2\alpha-2\beta τ := d − 2 − 2 α − 2 β , and N : = n 0 + p N:=n_0+p N := n 0 + p , m : = n − n 0 m:=n-n_0 m := n − n 0 , g : = m − 2 p = γ ^ n g:=m-2p=\hat{\gamma}n g := m − 2 p = γ ^ n , s : = σ n s:=\sigma n s := σ n . The purple coefficient is exact: [ y g ] ( 1 − y ) − ν = ( ν ) g / g ! [y^g](1-y)^{-\nu}=(\nu)_g/g! [ y g ] ( 1 − y ) − ν = ( ν ) g / g ! is a polynomial identity in ν \nu ν , hence
[ x m ] e ( u 2 / 2 ) L ( a x ) π ^ ( x ) p = a m ( c e 2 2 a 2 ) p ( u 2 / 2 + p ) g g ! . [x^m]e^{(u^2/2)L(ax)}\widehat{\pi}(x)^p=a^m\left(\frac{c_e^2}{2a^2}\right)^p\frac{(u^2/2+p)_g}{g!}. [ x m ] e ( u 2 /2 ) L ( a x ) π ( x ) p = a m ( 2 a 2 c e 2 ) p g ! ( u 2 /2 + p ) g .
and 4 p ( c e 2 / ( 2 a 2 ) ) p = ( 2 ( d − 2 ) 2 ) p 4^p(c_e^2/(2a^2))^p=(2(d-2)^2)^p 4 p ( c e 2 / ( 2 a 2 ) ) p = ( 2 ( d − 2 ) 2 ) p . Combined with ( u / 2 ) N = Γ ( N + u / 2 ) / Γ ( u / 2 ) (u/2)_N=\Gamma(N+u/2)/\Gamma(u/2) ( u /2 ) N = Γ ( N + u /2 ) /Γ ( u /2 ) and [ x n ] ( 1 − x ) − u / 2 = ( u / 2 ) n / n ! [x^n](1-x)^{-u/2}=(u/2)_n/n! [ x n ] ( 1 − x ) − u /2 = ( u /2 ) n / n ! , every summand of R n ( u ) R_n(u) R n ( u ) is a ratio of Gamma values, factorials, and matching numbers M ( τ n ) M ( d n ) / M ( ( d − 2 ) n ) 2 M(\tau n)M(dn)/M((d-2)n)^2 M ( τ n ) M ( d n ) / M (( d − 2 ) n ) 2 .
The exponent. Stirling’s formula log Γ ( z ) = ( z − 1 2 ) log z − z + 1 2 log ( 2 π ) + O ( ∣ z ∣ − 1 ) \log\Gamma(z)=(z-\frac12)\log z-z+\frac12\log(2\pi)+O(|z|^{-1}) log Γ ( z ) = ( z − 2 1 ) log z − z + 2 1 log ( 2 π ) + O ( ∣ z ∣ − 1 ) , uniformly for ∣ arg z ∣ ≤ π − δ |\arg z|\leq\pi-\delta ∣ arg z ∣ ≤ π − δ and ∣ z ∣ → ∞ |z|\to\infty ∣ z ∣ → ∞ , applied to every Gamma, factorial, and matching factor, produces two pieces. The n log n n\log n n log n exponents cancel identically (degree d + 1 d+1 d + 1 in the numerator and the denominator). The coefficient of n n n , η \eta η , is independent of u u u : every u u u enters through a shift Γ ( N + u / 2 ) \Gamma(N+u/2) Γ ( N + u /2 ) , Γ ( n + u / 2 ) \Gamma(n+u/2) Γ ( n + u /2 ) , Γ ( s + u 2 / 2 ) \Gamma(s+u^2/2) Γ ( s + u 2 /2 ) , or Γ ( p + u 2 / 2 ) \Gamma(p+u^2/2) Γ ( p + u 2 /2 ) , which contributes only an O ( 1 ) O(1) O ( 1 ) term after the log n \log n log n pieces cancel. Explicitly, for d ≥ 4 d\geq4 d ≥ 4 and ( α , β ) (\alpha,\beta) ( α , β ) in any fixed compact subset of the interior of Δ \Delta Δ ,
η ( α , β ) = 2 ( α + β ) log ( α + β ) + σ log σ + τ 2 log τ + d 2 log d + α log b + β log ( 2 ( d − 2 ) 2 ) − α log α − 2 β log β − γ ^ log γ ^ − log a − ( d − 2 ) log ( d − 2 ) , (14) \begin{aligned}
\eta(\alpha,\beta)={}&2(\alpha+\beta)\log(\alpha+\beta)+\sigma\log\sigma+\frac{\tau}{2}\log\tau+\frac{d}{2}\log d\\
&+\alpha\log b+\beta\log\bigl(2(d-2)^2\bigr)\\
&-\alpha\log\alpha-2\beta\log\beta-\hat{\gamma}\log\hat{\gamma}-\log a-(d-2)\log(d-2), \tag*{(14)}
\end{aligned} η ( α , β ) = 2 ( α + β ) log ( α + β ) + σ log σ + 2 τ log τ + 2 d log d + α log b + β log ( 2 ( d − 2 ) 2 ) − α log α − 2 β log β − γ ^ log γ ^ − log a − ( d − 2 ) log ( d − 2 ) , (14)
with b = ( d − 2 ) ( d − 3 ) b=(d-2)(d-3) b = ( d − 2 ) ( d − 3 ) and the convention 0 log 0 = 0 0\log0=0 0 log 0 = 0 on the boundary, and
Ψ u ( α , β ) = − log ( 2 π ) − 1 2 log ( α β γ ^ ) + ( u − 1 ) log ( α + β ) + u 2 − 1 2 log ( σ / β ) . (15) \Psi_u(\alpha,\beta)=-\log(2\pi)-\frac12\log(\alpha\beta\hat{\gamma})+(u-1)\log(\alpha+\beta)+\frac{u^2-1}{2}\log(\sigma/\beta). \tag*{(15)} Ψ u ( α , β ) = − log ( 2 π ) − 2 1 log ( α β γ ^ ) + ( u − 1 ) log ( α + β ) + 2 u 2 − 1 log ( σ / β ) . (15)
The prefactors ( 2 π n ) 1 / 2 (2\pi n)^{1/2} ( 2 π n ) 1/2 from Stirling’s formula contribute n 1 / 2 n^{1/2} n 1/2 in the numerator (from n ! n! n ! ) and n 3 / 2 n^{3/2} n 3/2 in the denominator (from n 0 ! n_0! n 0 ! , p ! p! p ! , and g ! g! g ! ), leaving a factor of n − 1 n^{-1} n − 1 , the area of a single lattice cell in the ( α , β ) (\alpha,\beta) ( α , β ) -plane. Thus, for ( α , β ) (\alpha,\beta) ( α , β ) in a fixed compact subset of the open triangle, the summand is
ρ n ( α , β ; u ) = n − 1 exp { n η ( α , β ) + Ψ u ( α , β ) + o ( 1 ) } , (16) \rho_n(\alpha,\beta;u)=n^{-1}\exp\{n\eta(\alpha,\beta)+\Psi_u(\alpha,\beta)+o(1)\}, \tag*{(16)} ρ n ( α , β ; u ) = n − 1 exp { n η ( α , β ) + Ψ u ( α , β ) + o ( 1 )} , (16)
uniformly for ( α , β ) (\alpha,\beta) ( α , β ) in any fixed compact subset of the open triangle and ∣ u − 1 ∣ ≤ ϵ |u-1|\leq\epsilon ∣ u − 1∣ ≤ ϵ (principal branches, Re u / 2 > 0 \operatorname{Re}u/2>0 Re u /2 > 0 ). In particular η \eta η does not depend on u u u , so the maximiser computed next is the same for every such u u u , including in a complex disk.
Consecutive ratios. Write T ( n 0 , p ) T(n_0,p) T ( n 0 , p ) for the u = 1 u=1 u = 1 summand of ∑ P Z ( 1 , P ) 2 \sum_P Z(1,P)^2 ∑ P Z ( 1 , P ) 2 . The Pochhammer recurrence ( 1 2 ) k + 1 / ( 1 2 ) k = k + 1 2 \left(\frac{1}{2}\right)_{k+1}/\left(\frac{1}{2}\right)_k=k+\frac{1}{2} ( 2 1 ) k + 1 / ( 2 1 ) k = k + 2 1 , the matching identity M ( 2 k − 2 ) / M ( 2 k ) = 1 / ( 2 k − 1 ) M(2k-2)/M(2k)=1/(2k-1) M ( 2 k − 2 ) / M ( 2 k ) = 1/ ( 2 k − 1 ) , and the exact coefficient ratio give
T ( n 0 + 1 , p ) T ( n 0 , p ) ⟶ f α : = ( α + β ) 2 b γ ^ α σ τ , (17) \frac{T(n_0+1,p)}{T(n_0,p)} \longrightarrow f_\alpha:= \frac{(\alpha+\beta)^2 b\hat{\gamma}}{\alpha\sigma\tau}, \tag*{(17)} T ( n 0 , p ) T ( n 0 + 1 , p ) ⟶ f α := α σ τ ( α + β ) 2 b γ ^ , (17)
T ( n 0 , p + 1 ) T ( n 0 , p ) ⟶ f β : = ( α + β ) 2 2 ( d − 2 ) 2 γ ^ 2 β 2 σ τ , (18) \frac{T(n_0,p+1)}{T(n_0,p)} \longrightarrow f_\beta:= \frac{(\alpha+\beta)^2 2(d-2)^2\hat{\gamma}^2}{\beta^2\sigma\tau}, \tag*{(18)} T ( n 0 , p ) T ( n 0 , p + 1 ) ⟶ f β := β 2 σ τ ( α + β ) 2 2 ( d − 2 ) 2 γ ^ 2 , (18)
as n → ∞ n\to\infty n → ∞ with ( α , β ) (\alpha,\beta) ( α , β ) in a compact subset of the open triangle. Differentiating (14) recovers ∇ η = ( log f α , log f β ) \nabla\eta=(\log f_\alpha,\log f_\beta) ∇ η = ( log f α , log f β ) . Setting both limits to 1 yields
( α + β ) 2 b γ ^ = α σ τ , (19) (\alpha+\beta)^2b\hat{\gamma}=\alpha\sigma\tau, \tag*{(19)} ( α + β ) 2 b γ ^ = α σ τ , (19)
( α + β ) 2 2 ( d − 2 ) 2 γ ^ 2 = β 2 σ τ . (20) (\alpha+\beta)^2 2(d-2)^2\hat{\gamma}^2=\beta^2\sigma\tau. \tag*{(20)} ( α + β ) 2 2 ( d − 2 ) 2 γ ^ 2 = β 2 σ τ . (20)
These are solved by
α ∗ = ( d − 2 ) ( d − 3 ) d ( d − 1 ) , β ∗ = 2 ( d − 2 ) d ( d − 1 ) , σ ∗ = 2 d . (21) \alpha^*=\frac{(d-2)(d-3)}{d(d-1)},\qquad\beta^*=\frac{2(d-2)}{d(d-1)},\qquad\sigma^*=\frac{2}{d}. \tag*{(21)} α ∗ = d ( d − 1 ) ( d − 2 ) ( d − 3 ) , β ∗ = d ( d − 1 ) 2 ( d − 2 ) , σ ∗ = d 2 . (21)
At this point γ ^ ∗ = 2 / ( d ( d − 1 ) ) \hat{\gamma}^*=2/(d(d-1)) γ ^ ∗ = 2/ ( d ( d − 1 )) and τ ∗ = ( d − 2 ) 2 / d \tau^*=(d-2)^2/d τ ∗ = ( d − 2 ) 2 / d ; direct substitution confirms that both sides of (19) equal 2 ( d − 3 ) ( d − 2 ) 3 / ( d 3 ( d − 1 ) ) 2(d-3)(d-2)^3/(d^3(d-1)) 2 ( d − 3 ) ( d − 2 ) 3 / ( d 3 ( d − 1 )) and both sides of (20) equal 8 ( d − 2 ) 4 / ( d 4 ( d − 1 ) 2 ) 8(d-2)^4/(d^4(d-1)^2) 8 ( d − 2 ) 4 / ( d 4 ( d − 1 ) 2 ) . Dividing the two critical equations gives the relation 2 ( d − 2 ) α γ ^ = ( d − 3 ) β 2 2(d-2)\alpha\hat{\gamma}=(d-3)\beta^2 2 ( d − 2 ) α γ ^ = ( d − 3 ) β 2 . With r = β / α r=\beta/\alpha r = β / α this reads α = 2 ( d − 2 ) / ( ( d − 3 ) r 2 + 2 ( d − 2 ) ( 1 + 2 r ) ) \alpha=2(d-2)/((d-3)r^2+2(d-2)(1+2r)) α = 2 ( d − 2 ) / (( d − 3 ) r 2 + 2 ( d − 2 ) ( 1 + 2 r )) , and substituting into (19) and clearing denominators leaves the cubic
( ( d − 3 ) r − 2 ) ( ( d − 3 ) ( 2 d − 5 ) r 2 + 2 ( d − 3 ) ( 2 d − 5 ) r + 2 ( d − 2 ) ( d − 4 ) ) = 0. \bigl((d-3)r-2\bigr)\bigl((d-3)(2d-5)r^2+2(d-3)(2d-5)r+2(d-2)(d-4)\bigr)=0. ( ( d − 3 ) r − 2 ) ( ( d − 3 ) ( 2 d − 5 ) r 2 + 2 ( d − 3 ) ( 2 d − 5 ) r + 2 ( d − 2 ) ( d − 4 ) ) = 0.
For d ≥ 4 d\ge4 d ≥ 4 the quadratic factor has nonnegative coefficients and positive leading coefficient, hence no root r > 0 r>0 r > 0 ; so r = 2 / ( d − 3 ) r=2/(d-3) r = 2/ ( d − 3 ) is the only root with α , β > 0 \alpha,\beta>0 α , β > 0 and γ ^ > 0 \hat{\gamma}>0 γ ^ > 0 , recovering (21) uniquely in the open triangle. On the open edges, f α → + ∞ f_\alpha\to+\infty f α → + ∞ as α → 0 + \alpha\to0^+ α → 0 + with β \beta β fixed in ( 0 , 1 / 2 ) (0,1/2) ( 0 , 1/2 ) , f β → + ∞ f_\beta\to+\infty f β → + ∞ as β → 0 + \beta\to0^+ β → 0 + , and f β → 0 f_\beta\to0 f β → 0 as γ ^ → 0 + \hat{\gamma}\to0^+ γ ^ → 0 + . At the three corners, η ( 0 , 0 ) = d 2 log d − d − 2 2 log ( d − 2 ) − log ( d ( d − 1 ) ) < 0 \eta(0,0)=\frac{d}{2}\log d-\frac{d-2}{2}\log(d-2)-\log(d(d-1))<0 η ( 0 , 0 ) = 2 d log d − 2 d − 2 log ( d − 2 ) − log ( d ( d − 1 )) < 0 , and likewise η ( 1 , 0 ) < 0 \eta(1,0)<0 η ( 1 , 0 ) < 0 , η ( 0 , 1 2 ) < 0 \eta(0,\frac{1}{2})<0 η ( 0 , 2 1 ) < 0 . Thus no boundary point is a local maximum, and (21) is the unique global maximiser on the compact set Δ \Delta Δ . Substituting the coordinates into (14) and collecting coefficients of log ( d − 3 ) \log(d-3) log ( d − 3 ) , log ( d − 1 ) \log(d-1) log ( d − 1 ) , log d \log d log d , log ( d − 2 ) \log(d-2) log ( d − 2 ) and log 2 \log2 log 2 gives respectively α ∗ − α ∗ \alpha^*-\alpha^* α ∗ − α ∗ , α ∗ + 2 β ∗ + γ ^ ∗ − 1 \alpha^*+2\beta^*+\hat{\gamma}^*-1 α ∗ + 2 β ∗ + γ ^ ∗ − 1 , d 2 − 2 ( d − 2 ) d − 2 d \frac{d}{2}-\frac{2(d-2)}{d}-\frac{2}{d} 2 d − d 2 ( d − 2 ) − d 2 , 2 ( d − 2 ) 2 d − ( d − 2 ) 2 2 d \frac{2(d-2)}{2d}-\frac{(d-2)^2}{2d} 2 d 2 ( d − 2 ) − 2 d ( d − 2 ) 2 , 2 ( d − 2 ) d + ( d − 2 ) 2 d − ( d − 2 ) \frac{2(d-2)}{d}+\frac{(d-2)^2}{d}-(d-2) d 2 ( d − 2 ) + d ( d − 2 ) 2 − ( d − 2 ) and 2 d − β ∗ − γ ^ ∗ \frac{2}{d}-\beta^*-\hat{\gamma}^* d 2 − β ∗ − γ ^ ∗ , each identically zero, so η ( α ∗ , β ∗ ) = 0 \eta(\alpha^*,\beta^*)=0 η ( α ∗ , β ∗ ) = 0 .
Hessian
Differentiating ( log f α , log f β ) (\log f_\alpha,\log f_\beta) ( log f α , log f β ) at (21) produces H : = D 2 η ( α ∗ , β ∗ ) H:=D^2\eta(\alpha^*,\beta^*) H := D 2 η ( α ∗ , β ∗ ) with entries
H 11 = − d ( d 4 − 9 d 3 + 28 d 2 − 34 d + 16 ) 2 ( d − 3 ) ( d − 2 ) 2 , H 12 = d ( − 2 d 3 + 11 d 2 − 16 d + 8 ) 2 ( d − 2 ) 2 , H 22 = d ( − 4 d 3 + 19 d 2 − 26 d + 12 ) 2 ( d − 2 ) 2 . (22) \begin{aligned}
H_{11} &= -\frac{d(d^4-9d^3+28d^2-34d+16)}{2(d-3)(d-2)^2},\\
H_{12} &= \frac{d(-2d^3+11d^2-16d+8)}{2(d-2)^2},\\
H_{22} &= \frac{d(-4d^3+19d^2-26d+12)}{2(d-2)^2}. \tag*{(22)}
\end{aligned} H 11 H 12 H 22 = − 2 ( d − 3 ) ( d − 2 ) 2 d ( d 4 − 9 d 3 + 28 d 2 − 34 d + 16 ) , = 2 ( d − 2 ) 2 d ( − 2 d 3 + 11 d 2 − 16 d + 8 ) , = 2 ( d − 2 ) 2 d ( − 4 d 3 + 19 d 2 − 26 d + 12 ) . (22)
for d ≥ 4 d \ge4 d ≥ 4 . In particular
det H = d 3 ( d − 1 ) 2 4 ( d − 3 ) ( d − 2 ) > 0 , \det H=\frac{d^3(d-1)^2}{4(d-3)(d-2)}>0, det H = 4 ( d − 3 ) ( d − 2 ) d 3 ( d − 1 ) 2 > 0 ,
tr H = − d ( 5 d 4 − 40 d 3 + 111 d 2 − 124 d + 52 ) 2 ( d − 3 ) ( d − 2 ) 2 < 0 (23) \operatorname{tr} H=-\frac{d(5d^4-40d^3+111d^2-124d+52)}{2(d-3)(d-2)^2}<0 \tag*{(23)} tr H = − 2 ( d − 3 ) ( d − 2 ) 2 d ( 5 d 4 − 40 d 3 + 111 d 2 − 124 d + 52 ) < 0 (23)
for every d ≥ 4 d \ge4 d ≥ 4 : both quartics d 4 − 9 d 3 + 28 d 2 − 34 d + 16 d^4-9d^3+28d^2-34d+16 d 4 − 9 d 3 + 28 d 2 − 34 d + 16 and 5 d 4 − 40 d 3 + 111 d 2 − 124 d + 52 5d^4-40d^3+111d^2-124d+52 5 d 4 − 40 d 3 + 111 d 2 − 124 d + 52 are positive on [ 4 , ∞ ) [4,\infty) [ 4 , ∞ ) (each has all real critical points in ( 0 , 4 ) (0,4) ( 0 , 4 ) , and the endpoint values at d = 4 d=4 d = 4 are positive). Thus H ≺ 0 H \prec0 H ≺ 0 .
The neighbourhood of the maximiser. Fix a width ω n = n − 2 / 5 \omega_n=n^{-2/5} ω n = n − 2/5 (so ( log n ) / n ≪ ω n ≪ 1 \sqrt{(\log n)}/n\ll\omega_n\ll1 ( log n ) / n ≪ ω n ≪ 1 ). Let L n L_n L n be the lattice points in Δ \Delta Δ with ∥ ( α , β ) − ( α ∗ , β ∗ ) ∥ ≤ ω n \lVert(\alpha,\beta)-(\alpha^*,\beta^*)\rVert\le\omega_n ∥( α , β ) − ( α ∗ , β ∗ )∥ ≤ ω n , and write R n l o c ( u ) = ∑ L n ρ n ( α , β ; u ) R_n^{\mathrm{loc}}(u)=\sum_{L_n}\rho_n(\alpha,\beta;u) R n loc ( u ) = ∑ L n ρ n ( α , β ; u ) . For large n n n this neighbourhood lies in a fixed compact subset of the open triangle, at a definite distance from ∂ Δ \partial\Delta ∂ Δ . Taylor-expand η \eta η about the maximiser: with x = n ( α − α ∗ , β − β ∗ ) ∈ R 2 x=\sqrt{n}(\alpha-\alpha^*,\beta-\beta^*)\in\mathbb{R}^2 x = n ( α − α ∗ , β − β ∗ ) ∈ R 2 ,
n η ( α , β ) = 1 2 x T H x + O ( ∣ x ∣ 3 n − 1 / 2 ) = 1 2 x T H x + O ( n − 1 / 5 ) , (24) n\eta(\alpha,\beta)=\frac{1}{2}x^{\mathsf T}Hx+O(|x|^3n^{-1/2})=\frac{1}{2}x^{\mathsf T}Hx+O(n^{-1/5}), \tag*{(24)} n η ( α , β ) = 2 1 x T H x + O ( ∣ x ∣ 3 n − 1/2 ) = 2 1 x T H x + O ( n − 1/5 ) , (24)
since ∣ x ∣ ≤ n 1 / 10 |x|\le n^{1/10} ∣ x ∣ ≤ n 1/10 on this neighbourhood and therefore ∣ x ∣ 3 n − 1 / 2 ≤ n − 1 / 5 |x|^3n^{-1/2}\le n^{-1/5} ∣ x ∣ 3 n − 1/2 ≤ n − 1/5 , while Ψ u ( α , β ) = Ψ u ( α ∗ , β ∗ ) + O ( ω n ) \Psi_u(\alpha,\beta)=\Psi_u(\alpha^*,\beta^*)+O(\omega_n) Ψ u ( α , β ) = Ψ u ( α ∗ , β ∗ ) + O ( ω n ) uniformly for ∣ u − 1 ∣ ≤ ε |u-1|\le\varepsilon ∣ u − 1∣ ≤ ε . The lattice has spacing 1 / n 1/n 1/ n in ( α , β ) (\alpha,\beta) ( α , β ) , hence spacing n − 1 / 2 n^{-1/2} n − 1/2 in the x x x -plane. Substituting (16) –(24) ,
R n l o c ( u ) = e Ψ u ( α ∗ , β ∗ ) ∑ ∥ x ∥ ≤ n 1 / 10 exp ( 1 2 x T H x + O ( n − 1 / 5 ) ) n − 1 = e Ψ u ( α ∗ , β ∗ ) ∫ ∥ x ∥ ≤ n 1 / 10 exp ( 1 2 x T H x ) d x ( 1 + O ( n − 1 / 5 ) ) , (25) \begin{aligned}
R_n^{\mathrm{loc}}(u)
&=e^{\Psi_u(\alpha^*,\beta^*)}\sum_{\lVert x\rVert\le n^{1/10}}\exp\left(\frac{1}{2}x^{\mathsf T}Hx+O(n^{-1/5})\right)n^{-1}\\
&=e^{\Psi_u(\alpha^*,\beta^*)}\int_{\lVert x\rVert\le n^{1/10}}\exp\left(\frac{1}{2}x^{\mathsf T}Hx\right)\,dx\left(1+O(n^{-1/5})\right), \tag*{(25)}
\end{aligned} R n loc ( u ) = e Ψ u ( α ∗ , β ∗ ) ∥ x ∥ ≤ n 1/10 ∑ exp ( 2 1 x T H x + O ( n − 1/5 ) ) n − 1 = e Ψ u ( α ∗ , β ∗ ) ∫ ∥ x ∥ ≤ n 1/10 exp ( 2 1 x T H x ) d x ( 1 + O ( n − 1/5 ) ) , (25)
uniformly for ∣ u − 1 ∣ ≤ ε |u-1|\le\varepsilon ∣ u − 1∣ ≤ ε . Extending the integral to R 2 \mathbb{R}^2 R 2 costs O ( exp ( − c n 1 / 5 ) ) O(\exp(-cn^{1/5})) O ( exp ( − c n 1/5 )) because H ≺ 0 H\prec0 H ≺ 0 , and
∫ R 2 exp ( 1 2 x T H x ) d x = 2 π det ( − H ) , \int_{\mathbb{R}^2}\exp\left(\frac{1}{2}x^{\mathsf T}Hx\right)\,dx=\frac{2\pi}{\sqrt{\det(-H)}}, ∫ R 2 exp ( 2 1 x T H x ) d x = det ( − H ) 2 π ,
so
R n l o c ( u ) = e Ψ u ( α ∗ , β ∗ ) 2 π det ( − H ) ( 1 + O ( n − 1 / 5 ) ) . (26) R_n^{\mathrm{loc}}(u)=e^{\Psi_u(\alpha^*,\beta^*)}\frac{2\pi}{\sqrt{\det(-H)}}\left(1+O(n^{-1/5})\right). \tag*{(26)} R n loc ( u ) = e Ψ u ( α ∗ , β ∗ ) det ( − H ) 2 π ( 1 + O ( n − 1/5 ) ) . (26)
The remaining summands. Let F n \mathcal{F}_n F n be the complementary lattice in Δ \Delta Δ . On the compact set Δ \Delta Δ the continuous function η \eta η attains the value 0 0 0 only at ( α ∗ , β ∗ ) (\alpha^*,\beta^*) ( α ∗ , β ∗ ) , so η ≤ − δ \eta\le-\delta η ≤ − δ off a fixed ball about the maximiser. In the annulus ω n ≤ ∥ ( α , β ) − ( α ∗ , β ∗ ) ∥ ≤ κ \omega_n \le\lVert(\alpha,\beta)-(\alpha^*,\beta^*)\rVert\le\kappa ω n ≤ ∥( α , β ) − ( α ∗ , β ∗ )∥ ≤ κ the quadratic upper bound from H ≺ 0 H \prec0 H ≺ 0 gives η ≤ − c ω n 2 = − c n − 4 / 5 \eta\le-c\omega_n^2=-cn^{-4/5} η ≤ − c ω n 2 = − c n − 4/5 . Near ∂ Δ \partial\Delta ∂ Δ the expansion (16) is not uniform (the factor − 1 2 log ( α β γ ^ ) -\frac{1}{2}\log(\alpha\beta\hat{\gamma}) − 2 1 log ( α β γ ^ ) diverges), but the two-sided bounds ( N / e ) N ≤ N ! ≤ e N + 1 ( N / e ) N (N/e)^N \le N! \le e\sqrt{N+1}(N/e)^N ( N / e ) N ≤ N ! ≤ e N + 1 ( N / e ) N and the analogous bounds for Γ ( N + u / 2 ) \Gamma(N+u/2) Γ ( N + u /2 ) with ∣ u − 1 ∣ ≤ ε \lvert u-1\rvert\le\varepsilon ∣ u − 1 ∣ ≤ ε (valid for all N ≥ 0 N \ge0 N ≥ 0 ; for N = 0 N=0 N = 0 , which occurs at p = 0 p=0 p = 0 , s = 0 s=0 s = 0 or τ = 0 \tau=0 τ = 0 , they read 1 ≤ 0 ! ≤ e 1 \le0! \le e 1 ≤ 0 ! ≤ e and Γ ( u / 2 ) \Gamma(u/2) Γ ( u /2 ) , Γ ( u 2 / 2 ) \Gamma(u^2/2) Γ ( u 2 /2 ) are bounded and bounded away from 0 0 0 on the disk, while M ( 0 ) = 1 M(0)=1 M ( 0 ) = 1 ) give ∣ summand ∣ ≤ n C e n η ( α , β ) \lvert\text{summand}\rvert\le n^C e^{n\eta(\alpha,\beta)} ∣ summand ∣ ≤ n C e n η ( α , β ) on all of Δ \Delta Δ , for a constant C = C ( d , ε ) C=C(d,\varepsilon) C = C ( d , ε ) . On a fixed neighbourhood of ∂ Δ \partial\Delta ∂ Δ one has η ≤ − δ / 2 \eta\le-\delta/2 η ≤ − δ /2 , so those O ( n 2 ) O(n^2) O ( n 2 ) points contribute O ( n C + 2 e − δ n / 2 ) O(n^{C+2}e^{-\delta n/2}) O ( n C + 2 e − δ n /2 ) . There are O ( n 2 ) O(n^2) O ( n 2 ) lattice points in total, and each remaining summand off that neighbourhood is O ( n − 1 exp ( − c ′ n 1 / 5 ) ) O(n^{-1}\exp(-c'n^{1/5})) O ( n − 1 exp ( − c ′ n 1/5 )) uniformly for ∣ u − 1 ∣ ≤ ε \lvert u-1\rvert\le\varepsilon ∣ u − 1 ∣ ≤ ε . Hence
R n t a i l ( u ) : = ∑ F n ρ n ( α , β ; u ) = O ( n exp ( − c ′ n 1 / 5 ) ) = o ( n − N ) (27) R_n^{\mathrm{tail}}(u):=\sum_{\mathcal{F}_n}\rho_n(\alpha,\beta;u)=O\bigl(n\exp(-c'n^{1/5})\bigr)=o(n^{-N}) \tag*{(27)} R n tail ( u ) := F n ∑ ρ n ( α , β ; u ) = O ( n exp ( − c ′ n 1/5 ) ) = o ( n − N ) (27)
for every N N N . Adding the two parts,
R n ( u ) = e Ψ u ( α ∗ , β ∗ ) 2 π det ( − H ) ( 1 + O ( n − 1 / 5 ) ) , R_n(u)=e^{\Psi_u(\alpha^*,\beta^*)}\frac{2\pi}{\sqrt{\det(-H)}}\left(1+O(n^{-1/5})\right), R n ( u ) = e Ψ u ( α ∗ , β ∗ ) det ( − H ) 2 π ( 1 + O ( n − 1/5 ) ) ,
uniformly on the closed disk D ‾ ( 1 , ε ) \overline{D}(1,\varepsilon) D ( 1 , ε ) .
Leading constant. From (15) at u = 1 u=1 u = 1 ,
e Ψ 1 ( α ∗ , β ∗ ) 2 π det ( − H ) = ( α ∗ β ∗ γ ^ ∗ det H ) − 1 / 2 . e^{\Psi_1(\alpha^*,\beta^*)}\frac{2\pi}{\sqrt{\det(-H)}}=(\alpha^*\beta^*\hat{\gamma}^*\det H)^{-1/2}. e Ψ 1 ( α ∗ , β ∗ ) det ( − H ) 2 π = ( α ∗ β ∗ γ ^ ∗ det H ) − 1/2 .
The product of the coordinates is α ∗ β ∗ γ ^ ∗ = 4 ( d − 2 ) 2 ( d − 3 ) / ( d 3 ( d − 1 ) 3 ) \alpha^*\beta^*\hat{\gamma}^*=4(d-2)^2(d-3)/(d^3(d-1)^3) α ∗ β ∗ γ ^ ∗ = 4 ( d − 2 ) 2 ( d − 3 ) / ( d 3 ( d − 1 ) 3 ) , and with (23)
α ∗ β ∗ γ ^ ∗ det H = d − 2 d − 1 , \alpha^*\beta^*\hat{\gamma}^*\det H=\frac{d-2}{d-1}, α ∗ β ∗ γ ^ ∗ det H = d − 1 d − 2 ,
hence the leading constant at u = 1 u=1 u = 1 is C ( 1 ) = ( d − 1 ) / ( d − 2 ) C(1)=\sqrt{(d-1)/(d-2)} C ( 1 ) = ( d − 1 ) / ( d − 2 ) . The dependence on u u u is given by the factor
e Ψ u ( α ∗ , β ∗ ) − Ψ 1 ( α ∗ , β ∗ ) = ( α ∗ + β ∗ ) u − 1 ( α ∗ β ∗ ) ( u 2 − 1 ) / 2 = ( d − 2 d ) u − 1 ( d − 1 d − 2 ) ( u 2 − 1 ) / 2 , \begin{aligned}
e^{\Psi_u(\alpha^*,\beta^*)-\Psi_1(\alpha^*,\beta^*)}=(\alpha^*+\beta^*)^{u-1}\left(\frac{\alpha^*}{\beta^*}\right)^{(u^2-1)/2} \\
&=\left(\frac{d-2}{d}\right)^{u-1}\left(\frac{d-1}{d-2}\right)^{(u^2-1)/2},
\end{aligned} e Ψ u ( α ∗ , β ∗ ) − Ψ 1 ( α ∗ , β ∗ ) = ( α ∗ + β ∗ ) u − 1 ( β ∗ α ∗ ) ( u 2 − 1 ) /2 = ( d d − 2 ) u − 1 ( d − 2 d − 1 ) ( u 2 − 1 ) /2 ,
which equals C ( u ) / C ( 1 ) C(u)/C(1) C ( u ) / C ( 1 ) by (5) (an algebraic identity valid for all complex u u u ). Therefore
R n ( u ) = C ( u ) ( 1 + O ( n − 1 / 5 ) ) , R_n(u)=C(u)\left(1+O(n^{-1/5})\right), R n ( u ) = C ( u ) ( 1 + O ( n − 1/5 ) ) ,
uniformly on D ‾ ( 1 , ε ) \overline{D}(1,\varepsilon) D ( 1 , ε ) . Since u ↦ Ψ u ( α ∗ , β ∗ ) u\mapsto\Psi_u(\alpha^*,\beta^*) u ↦ Ψ u ( α ∗ , β ∗ ) is holomorphic on a neighbourhood of u = 1 u=1 u = 1 , no additional analytic continuation step is required.
The cubic case d = 3 d = 3 d = 3 . Here b = 0 b = 0 b = 0 forces n 0 = 0 n_0 = 0 n 0 = 0 , and the sum is one-dimensional in β ∈ [ 0 , 1 / 2 ] \beta\in[0,1/2] β ∈ [ 0 , 1/2 ] , with σ = 1 − β \sigma= 1 - \beta σ = 1 − β , γ ^ = τ = 1 − 2 β \hat{\gamma} = \tau= 1 - 2\beta γ ^ = τ = 1 − 2 β . The same Stirling computation (now n ! / ( p ! g ! ) n!/(p!g!) n ! / ( p ! g !) ), which contributes a factor of n − 1 / 2 n^{-1/2} n − 1/2 , gives
η ( β ) = σ log σ − γ ^ 2 log γ ^ + β log 2 + 3 2 log 3 − log 6 , Ψ u ( β ) = − 1 2 log ( 2 π ) − 1 2 log ( β γ ^ ) + ( u − 1 ) log β + u 2 − 1 2 log ( σ / β ) . (28) \begin{aligned}
\eta(\beta) &= \sigma\log\sigma- \frac{\hat{\gamma}}{2}\log\hat{\gamma} + \beta\log2 + \frac{3}{2}\log3 - \log6,\\
\Psi_u(\beta) &= -\frac{1}{2}\log(2\pi) - \frac{1}{2}\log(\beta\hat{\gamma}) + (u-1)\log\beta+ \frac{u^2-1}{2}\log(\sigma/\beta). \tag*{(28)}
\end{aligned} η ( β ) Ψ u ( β ) = σ log σ − 2 γ ^ log γ ^ + β log 2 + 2 3 log 3 − log 6 , = − 2 1 log ( 2 π ) − 2 1 log ( β γ ^ ) + ( u − 1 ) log β + 2 u 2 − 1 log ( σ / β ) . (28)
and ρ n ( β ; u ) = n − 1 / 2 exp ( n η ( β ) + Ψ u ( β ) + o ( 1 ) ) \rho_n(\beta;u) = n^{-1/2}\exp(n\eta(\beta)+\Psi_u(\beta)+o(1)) ρ n ( β ; u ) = n − 1/2 exp ( n η ( β ) + Ψ u ( β ) + o ( 1 )) . One has η ′ ( β ) = log ( 2 γ ^ / σ ) \eta'(\beta) = \log(2\hat{\gamma}/\sigma) η ′ ( β ) = log ( 2 γ ^ / σ ) , so the unique critical point in ( 0 , 1 / 2 ) (0,1/2) ( 0 , 1/2 ) is β ∗ = 1 / 3 \beta^* = 1/3 β ∗ = 1/3 , with η ( 1 / 3 ) = 0 \eta(1/3) = 0 η ( 1/3 ) = 0 and η ′ ′ ( 1 / 3 ) = − 9 / 2 < 0 \eta''(1/3) = -9/2 < 0 η ′′ ( 1/3 ) = − 9/2 < 0 . The one-dimensional Laplace method (neighbourhood of width ω n = n − 2 / 5 \omega_n = n^{-2/5} ω n = n − 2/5 , tail exp ( − c n 1 / 5 ) \exp(-cn^{1/5}) exp ( − c n 1/5 ) ) yields
R n ( u ) = e Ψ u ( 1 / 3 ) 2 π ∣ η ′ ′ ( 1 / 3 ) ∣ ( 1 + O ( n − 1 / 5 ) ) . R_n(u) = e^{\Psi_u(1/3)}\sqrt{\frac{2\pi}{|\eta''(1/3)|}}\left(1+O(n^{-1/5})\right). R n ( u ) = e Ψ u ( 1/3 ) ∣ η ′′ ( 1/3 ) ∣ 2 π ( 1 + O ( n − 1/5 ) ) .
At u = 1 u = 1 u = 1 ,
e Ψ 1 ( 1 / 3 ) 2 π 9 / 2 = ( β ∗ γ ^ ∗ ∣ η ′ ′ ( 1 / 3 ) ∣ ) − 1 / 2 = ( 1 3 ⋅ 1 3 ⋅ 9 2 ) − 1 / 2 = 2 = C ( 1 ) , e^{\Psi_1(1/3)}\sqrt{\frac{2\pi}{9/2}} = (\beta^*\hat{\gamma}^*|\eta''(1/3)|)^{-1/2} = \left(\frac{1}{3}\cdot\frac{1}{3}\cdot\frac{9}{2}\right)^{-1/2} = \sqrt{2} = C(1), e Ψ 1 ( 1/3 ) 9/2 2 π = ( β ∗ γ ^ ∗ ∣ η ′′ ( 1/3 ) ∣ ) − 1/2 = ( 3 1 ⋅ 3 1 ⋅ 2 9 ) − 1/2 = 2 = C ( 1 ) ,
and the u u u -dependent factor is ( β ∗ ) u − 1 ( σ ∗ / β ∗ ) ( u 2 − 1 ) / 2 = 2 ( u − 1 ) 2 / 2 ( 2 / 3 ) u − 1 = C ( u ) / C ( 1 ) (\beta^*)^{u-1}(\sigma^*/\beta^*)^{(u^2-1)/2} = 2^{(u-1)^2/2}(2/3)^{u-1} = C(u)/C(1) ( β ∗ ) u − 1 ( σ ∗ / β ∗ ) ( u 2 − 1 ) /2 = 2 ( u − 1 ) 2 /2 ( 2/3 ) u − 1 = C ( u ) / C ( 1 ) for d = 3 d = 3 d = 3 . The same formulae hold uniformly on D ‾ ( 1 , ε ) \overline{D}(1,\varepsilon) D ( 1 , ε ) .
Exact enumeration and simulations
Code availability. All implementations and reproducibility scripts for the computations reported below are available at https://github.com/ktadler/2factor-cycles .
Small values of n n n are treated by exhaustive enumeration: for d = 3 d = 3 d = 3 , every perfect-matching complement is enumerated up to n = 80 n = 80 n = 80 , and for d = 4 d = 4 d = 4 , every 2-factor is enumerated up to n = 24 n = 24 n = 24 . For larger n n n , each trial consists of one simple d d d -regular graph generated via networkx.random_regular_graph [10 ] and one 2-factor obtained by the Karp–Sipser algorithm followed by Edmonds’ blossom algorithm [1 , 5 , 14 ] , applied directly to G G G when d = 3 d = 3 d = 3 and to Tutte’s gadget [19 ] (which has 2 ( d − 1 ) n 2(d-1)n 2 ( d − 1 ) n vertices) when d ≥ 4 d \ge4 d ≥ 4 . While this heuristic is not guaranteed to sample a uniformly random 2-factor of G G G , its empirical mean agrees closely with the exact uniform per-graph mean throughout the range where exhaustive enumeration is feasible.
Exact verification. All identities were verified in exact arithmetic. The counts N c = n ! [ x n ] L ≥ 3 ( x ) c / c ! N_c = n![x^n]L_{\ge3}(x)^c/c! N c = n ! [ x n ] L ≥ 3 ( x ) c / c ! of simple 2-regular graphs coincide with brute-force enumeration for all 3 ≤ n ≤ 9 3 \le n \le9 3 ≤ n ≤ 9 ; and for n = 4 n = 4 n = 4 , d = 3 d = 3 d = 3 , the identity of
Theorem 3.1 was verified integer-for-integer against all M ( 12 ) = 10,395 M(12) = 10{,}395 M ( 12 ) = 10 , 395 pairings (∑ P Z c = 11664 , 10692 , 2916 , 243 \sum_P Z_c = 11664, 10692, 2916, 243 ∑ P Z c = 11664 , 10692 , 2916 , 243 for c = 1 , … , 4 c = 1, \ldots, 4 c = 1 , … , 4 ). Monte Carlo estimates at ( n , d ) = ( 6 , 3 ) (n,d) = (6,3) ( n , d ) = ( 6 , 3 ) and ( 5 , 4 ) (5,4) ( 5 , 4 ) agree with the theoretical formulas within sampling error.
Exact enumeration on fixed graphs (d = 3 d = 3 d = 3 , n ≤ 80 n \le80 n ≤ 80 ; d = 4 d = 4 d = 4 , n ≤ 24 n \le24 n ≤ 24 ). For d = 3 d = 3 d = 3 , the 2-factors of a graph are the complements of its perfect matchings. For each n ∈ { 8 , 12 , 16 , 24 , 32 , 48 , 64 , 80 } n \in\{8, 12, 16, 24, 32, 48, 64, 80\} n ∈ { 8 , 12 , 16 , 24 , 32 , 48 , 64 , 80 } , we sampled random simple cubic graphs, enumerated all perfect matchings by backtracking, and recorded the exact conditional mean of X ′ X' X ′ on each graph; see Table 1 . For d = 4 d = 4 d = 4 , where no single-matching reduction is available and the expected number of 2-factors E Z \mathbb{E}Z E Z is much larger (approximately 1.7 × 10 14 1.7 \times10^{14} 1.7 × 1 0 14 at n = 80 n = 80 n = 80 , compared with 1.4 × 10 5 1.4 \times10^5 1.4 × 1 0 5 for d = 3 d = 3 d = 3 ), exhaustive backtracking was carried out for 40 simple 4-regular graphs at each n ∈ { 8 , 12 , 16 , 20 , 24 } n \in\{8, 12, 16, 20, 24\} n ∈ { 8 , 12 , 16 , 20 , 24 } , yielding per-graph sample means 1.29, 1.49, 1.62, 1.74, 1.82 (compared with the Karp–Sipser sample means 1.33, 1.39, 1.64, 1.83, 1.80).
Table 1. Exact enumeration on fixed graphs: mean cycle count of a uniform random 2-factor per sampled cubic graph.
Simulations for larger n n n and d d d . For each pair ( n , d ) (n,d) ( n , d ) in Table 2 and Figure 2 , we generated N = 100 N = 100 N = 100 independent simple d d d -regular graphs and sampled one 2-factor per graph using the Karp–Sipser heuristic finished by Edmonds’ blossom algorithm; reported uncertainties ± \pm ± denote the standard error sd / N \operatorname{sd}/\sqrt{N} sd / N . Figure 2 (a) compares these empirical means with the exact uniform per-graph means for n ≤ 80 n \le80 n ≤ 80 (d = 3 d = 3 d = 3 ) and n ≤ 24 n \le24 n ≤ 24 (d = 4 d = 4 d = 4 ). Figure 2 (b) extends the estimates to n ≤ 10 6 n \le10^6 n ≤ 1 0 6 for d = 3 , 4 d = 3,4 d = 3 , 4 and n ≤ 10 5 n \le10^5 n ≤ 1 0 5 for d = 10 d = 10 d = 10 , comparing them against the asymptotic simple-graph mean μ n = 1 2 log n + 1 2 + log 2 − 3 4 \mu_n = \frac{1}{2}\log n + \frac{1}{2} + \log2 - \frac{3}{4} μ n = 2 1 log n + 2 1 + log 2 − 4 3 of Theorem 4.1 . Figure 2 (c) holds n = 10 4 n = 10^4 n = 1 0 4 fixed and varies d ∈ { 3 , 4 , 10 , 30 , 50 } d \in\{3,4,10,30,50\} d ∈ { 3 , 4 , 10 , 30 , 50 } , illustrating the degree-independence of the mean cycle count. Finally, Figure 3 compares the empirical distribution of the number of cycles over N = 500 N = 500 N = 500 independent trials at n = 10 6 n = 10^6 n = 1 0 6 for d = 3 d = 3 d = 3 and d = 4 d = 4 d = 4 with the theoretical distribution of Theorem 4.1 .
Table 2. Sample means from N = 100 N = 100 N = 100 independent trials per ( n , d ) (n,d) ( n , d ) pair (one 2-factor per graph), compared with the asymptotic simple-graph mean 1 2 log n + 1 2 + log 2 − 3 4 \frac{1}{2}\log n + \frac{1}{2} + \log2 - \frac{3}{4} 2 1 log n + 2 1 + log 2 − 4 3 of Theorem 4.1 .
Figure 2. (a) Comparison of exact per-graph uniform means and Karp–Sipser + blossom sample means (N = 100 N = 100 N = 100 ) for n ≤ 80 n \le80 n ≤ 80 (d = 3 d = 3 d = 3 ) and n ≤ 24 n \le24 n ≤ 24 (d = 4 d = 4 d = 4 ). (b) Sample means (N = 100 N = 100 N = 100 ) across powers of ten up to n = 10 6 n = 10^6 n = 1 0 6 . (c) Sample means at fixed n = 10 4 n = 10^4 n = 1 0 4 for d ∈ { 3 , 4 , 10 , 30 , 50 } d \in\{3, 4, 10, 30, 50\} d ∈ { 3 , 4 , 10 , 30 , 50 } . Dashed line: simple-graph mean of Theorem 4.1 ; error bars show ± s d / N \pm\mathrm{sd}/\sqrt{N} ± sd / N .
Figure 3. Empirical distribution of cycle counts at n = 10 6 n = 10^{6} n = 1 0 6 (N = 500 N = 500 N = 500 trials) for (a) d = 3 d = 3 d = 3 and (b) d = 4 d = 4 d = 4 , compared with the theoretical distribution of Theorem 4.1 (dashed curve).
Competing interests
The authors declare none.
Data availability
The code and the numerical comparisons reported in Appendix § 10 are openly available at https://github.com/ktadler/2factor-cycles .
Funding
This work received no specific grant from any funding agency, commercial or not-for-profit sectors.