betaFeedback

WorksMathematics

The number of kk-factors of a random regular graph

Abstract

Let Zk(G)Z_k(G) be the number of kk-factors (kk-regular spanning subgraphs) of a uniformly random simple dd-regular graph G∼G(n,d)G\sim G(n,d), where d≥3d\ge 3 and 1≤k≤d−11\le k\le d-1 are fixed integers such that dndn and knkn are even. We determine the asymptotic second moment of Zk(G)Z_k(G) and show that Zk(G)/EZk(G)Z_k(G)/\mathbb{E} Z_k(G) converges in distribution to an explicit random variable WW that depends on the short-cycle counts of GG but not on kk. Moreover, for any 1≤k,ℓ≤d−11\le k,\ell\le d-1, the normalised counts on the same graph satisfy Zk(G)/EZk(G)−Zℓ(G)/EZℓ(G)→0Z_k(G)/\mathbb{E} Z_k(G) - Z_\ell(G)/\mathbb{E} Z_\ell(G) \to 0 in probability, and, since W>0W>0 almost surely, their ratio converges to 11 in probability. This extends results of Bollobás–McKay and Janson for k=1k=1 and Robalewska for k=2k=2 to all 1≤k≤d−11\le k\le d-1. In the pairing model, the second moment reduces to a one-dimensional lattice sum over the overlap of two kk-factors. We evaluate this sum using the Poisson-binomial representation of the hypergeometric distribution, exponential tilting, and a uniform local limit theorem.

Introduction

Fix integers d≥3d \ge3 and 1≤k≤d−11 \le k \le d-1, and let nn be a positive integer such that dndn and knkn are even. A kk-factor of a graph GG is a spanning kk-regular subgraph. Let G(n,d)G(n,d) be the probability space of uniformly random labelled simple dd-regular graphs on [n]={1,…,n}[n]=\{1,\ldots,n\}. Write Zk(G)Z_k(G) for the number of kk-factors of GG, and Xi(G)X_i(G) for the number of cycles of length ii in GG. Throughout,

λi=(d−1)i2i,δi=(−1)i(d−1)i(i≥1),(1)\lambda_i=\frac{(d-1)^i}{2i},\qquad\delta_i=\frac{(-1)^i}{(d-1)^i}\qquad(i\ge1), \tag*{(1)}

so 1+δi>01+\delta_i>0 for all ii and ∑i≥1λiδi2=12∑i≥1(d−1)−i/i=12log⁡d−1d−2<∞\sum_{i\ge1}\lambda_i\delta_i^2=\frac{1}{2}\sum_{i\ge1}(d-1)^{-i}/i=\frac{1}{2}\log\frac{d-1}{d-2}<\infty. We prove that the short cycles of GG govern the relative fluctuations of Zk(G)Z_k(G) around its mean, independently of kk.

Theorem 1.1. Fix integers d≥3d\ge3 and 1≤k≤d−11\le k\le d-1. Let n→∞n\to\infty along integers for which dndn and knkn are even, and let G∼G(n,d)G\sim G(n,d). Let (ξi)i≥3(\xi_i)_{i\ge3} be independent Poisson(λi)(\lambda_i) random variables.

(i) (mean)

EG(n,d)[Zk(G)]=2e1/4((dk)kk/2(d−k)(d−k)/2d−d/2)n(1+o(1)).(2)\mathbb{E}_{G(n,d)}[Z_k(G)]=\sqrt{2}e^{1/4}\left(\binom{d}{k}k^{k/2}(d-k)^{(d-k)/2}d^{-d/2}\right)^n(1+o(1)). \tag*{(2)}

(ii) (second moment)

EG(n,d)[Zk(G)2](EG(n,d)[Zk(G)])2⟶exp⁡(∑i≥3λiδi2)=e−2d−14(d−1)2d−1d−2.(3)\frac{\mathbb{E}_{G(n,d)}[Z_k(G)^2]}{\left(\mathbb{E}_{G(n,d)}[Z_k(G)]\right)^2} \longrightarrow\exp\left(\sum_{i\ge3}\lambda_i\delta_i^2\right) =e^{-\frac{2d-1}{4(d-1)^2}}\sqrt{\frac{d-1}{d-2}}. \tag*{(3)}

(iii) (limit distribution) The infinite product

W:=∏i=3∞(1+δi)ξie−λiδi.(4)W:=\prod_{i=3}^{\infty}(1+\delta_i)^{\xi_i}e^{-\lambda_i\delta_i}. \tag*{(4)}

converges almost surely and in L2L^2. It satisfies W>0W > 0 almost surely, EW=1\mathbb{E}W = 1, and EW2=exp⁡(∑i≥3λiδi2)\mathbb{E}W^2 = \exp\left(\sum_{i\geq3}\lambda_i\delta_i^2\right). Moreover,

Zk(G)EG(n,d)[Zk(G)]⟹W,(5)\frac{Z_k(G)}{\mathbb{E}_{G(n,d)}[Z_k(G)]} \Longrightarrow W, \tag*{(5)}

jointly with (X3(G),…,Xm(G))⟹(ξ3,…,ξm)(X_3(G),\ldots,X_m(G)) \Longrightarrow(\xi_3,\ldots,\xi_m) for every fixed mm.

(iv) (linkage) For any 1≤k,ℓ≤d−11 \leq k,\ell\leq d-1, let nn tend to infinity along integers for which dndn, knkn, and ℓn\ell n are even. The normalised counts on the same graph G∼G(n,d)G \sim G(n,d) satisfy

Zk(G)EG(n,d)[Zk(G)]−Zℓ(G)EG(n,d)[Zℓ(G)]→p0,(6)\frac{Z_k(G)}{\mathbb{E}_{G(n,d)}[Z_k(G)]} - \frac{Z_\ell(G)}{\mathbb{E}_{G(n,d)}[Z_\ell(G)]} \xrightarrow{p} 0, \tag*{(6)}

and consequently Zk(G)/EG(n,d)[Zk(G)]Zℓ(G)/EG(n,d)[Zℓ(G)]→p1\frac{Z_k(G)/\mathbb{E}_{G(n,d)}[Z_k(G)]}{Z_\ell(G)/\mathbb{E}_{G(n,d)}[Z_\ell(G)]} \xrightarrow{p} 1. Here the ratio is set equal to 1 on the event {Zℓ(G)=0}\{Z_\ell(G) = 0\}, whose probability tends to 0.

Previous work. For k=1k = 1 (perfect matchings), Bollobás and McKay [2] determined the asymptotics of the first two moments of Z1(G)Z_1(G). Janson [6] obtained the limit distribution of Z1(G)/EZ1(G)Z_1(G)/\mathbb{E}Z_1(G) by the small subgraph conditioning method. Robinson and Wormald introduced this method for Hamilton cycles in cubic graphs [9] and applied it to perfect matchings [10]. For k=2k = 2, Robalewska [8] computed the second moment and established the limit distribution.

The complement of a kk-factor in a dd-regular graph is a (d−k)(d-k)-factor. Thus Zk(G)=Zd−k(G)Z_k(G) = Z_{d-k}(G), and the cases k=d−1k = d-1 and k=d−2k = d-2 follow. Theorem 1.1 was therefore known for k∈{1,2,d−2,d−1}k \in\{1,2,d-2,d-1\}. In particular, the normalised numbers of perfect matchings and 2-factors have the same limit distribution [8 Corollary 4]. Wormald also observed that they are asymptotically linked: Z1(G)/EZ1(G)∼Z2(G)/EZ2(G)Z_1(G)/\mathbb{E}Z_1(G) \sim Z_2(G)/\mathbb{E}Z_2(G) asymptotically almost surely [12 Corollary 4.10 and the remark following it]. Part (iv) extends this result to all pairs k,ℓk,\ell.

References

  1. [1]B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin. 1 (1980), 311–316.DOI
  2. [2]B. Bollobás and B. D. McKay, The number of matchings in random regular graphs and bipartite graphs, J. Combin. Theory Ser. B 41 (1986), 80–91.
  3. [3]P. Gao, The number of perfect matchings, and the nesting properties, of random regular graphs, Random Structures Algorithms 62 (2023), 935–955.arxiv.org/abs/2104.11850
  4. [4]M. HashemiNezhad and B. D. McKay, Factorisation of the complete graph into spanning regular factors, Adv. in Appl. Math. 146 (2023), Paper No. 102487.arxiv.org/abs/2206.12792
  5. [5]M. Isaev, B. D. McKay, A. Southwell, and M. Zhukovskii, Sprinkling with random regular graphs, Electron. J. Probab. 30 (2025), Paper No. 17, 1–20.arxiv.org/abs/2309.00190
  6. [6]S. Janson, Random regular graphs: asymptotic distributions and contiguity, Combin. Probab. Comput. 4 (1995), 369–405.DOI
  7. [7]J. Pitman, Probabilistic bounds on the coefficients of polynomials with only real zeros, J. Combin. Theory Ser. A 77 (1997), 279–303.DOI
  8. [8]H. D. Robalewska, 2-factors in random regular graphs, J. Graph Theory 23 (1996), 215–224.doi.org/10.1002/(sici)1097-0118(199611)23:3<215::aid-jgt1>3.0.co;2-v
  9. [9]R. W. Robinson and N. C. Wormald, Almost all cubic graphs are Hamiltonian, Random Structures Algorithms 3 (1992), 117–125.DOI
  10. [10]R. W. Robinson and N. C. Wormald, Almost all regular graphs are Hamiltonian, Random Structures Algorithms 5 (1994), 363–374.DOI
  11. [11]V. A. Vatutin and V. G. Mikhailov, Limit theorems for the number of empty cells in an equiprobable scheme for group allocation of particles, Theory Probab. Appl. 27 (1982), 734–743.DOI
  12. [12]N. C. Wormald, Models of random regular graphs, in Surveys in Combinatorics, 1999, London Math. Soc. Lecture Note Ser., vol. 267, Cambridge Univ. Press, Cambridge, 1999, pp. 239–298.

Paper details

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

views · 0

downloads · 0

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

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents