Hostname: page-component-6bf8c574d5-9nwgx Total loading time: 0 Render date: 2025-02-15T04:45:37.576Z Has data issue: false hasContentIssue false
  • English
  • Français

Subgraph distributions in dense random regular graphs

Part of: Graph theory Limit theorems Combinatorics

Published online by Cambridge University Press:  25 August 2023

Ashwin Sah  and
Mehtaab Sawhney
Ashwin Sah
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139, USA [email protected]
Mehtaab Sawhney
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139, USA [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Given a connected graph $H$ which is not a star, we show that the number of copies of $H$ in a dense uniformly random regular graph is asymptotically Gaussian, which was not known even for $H$ being a triangle. This addresses a question of McKay from the 2010 International Congress of Mathematicians. In fact, we prove that the behavior of the variance of the number of copies of $H$ depends in a delicate manner on the occurrence and number of cycles of $3,4,5$ edges as well as paths of $3$ edges in $H$. More generally, we provide control of the asymptotic distribution of certain statistics of bounded degree which are invariant under vertex permutations, including moments of the spectrum of a random regular graph. Our techniques are based on combining complex-analytic methods due to McKay and Wormald used to enumerate regular graphs with the notion of graph factors developed by Janson in the context of studying subgraph counts in $\mathbb {G}(n,p)$.

Keywords

random regular graphscentral limit theorem

MSC classification

Primary: 60F05: Central limit and other weak theorems 05C80: Random graphs 05A16: Asymptotic enumeration
Type
Research Article
Information
Compositio Mathematica , Volume 159 , Issue 10 , October 2023 , pp. 2125 - 2148
Check for updates
Copyright
© 2023 The Author(s). The publishing rights in this article are licensed to Foundation Compositio Mathematica under an exclusive licence

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-2141064. Sah was supported by the PD Soros Fellowship.

References

Bollobás, B., A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin. 1 (1980), 311–316.CrossRefGoogle Scholar
Durrett, R., Probability—theory and examples, fifth edition, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 49 (Cambridge University Press, Cambridge, 2019).CrossRefGoogle Scholar
Gao, P., Triangles and subgraph probabilities in random regular graphs, Preprint (2020), arXiv:2012.01492.Google Scholar
Gao, Z. and Wormald, N. C., Distribution of subgraphs of random regular graphs, Random Structures Algorithms 32 (2008), 38–48.CrossRefGoogle Scholar
He, Y., Spectral gap and edge universality of dense random regular graphs, Preprint (2022), arXiv:2203.07317.Google Scholar
Isaev, M. and McKay, B. D., Complex martingales and asymptotic enumeration, Random Structures Algorithms 52 (2018), 617–661.10.1002/rsa.20754CrossRefGoogle Scholar
Janson, S., The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph, Combin. Probab. Comput. 3 (1994), 97–126.10.1017/S0963548300001012CrossRefGoogle Scholar
Janson, S., Orthogonal decompositions and functional limit theorems for random graph statistics, Mem. Amer. Math. Soc. 111 (1994).Google Scholar
Janson, S., A graph Fourier transform and proportional graphs, Random Structures Algorithms 6 (1995), 341–351.10.1002/rsa.3240060221CrossRefGoogle Scholar
Janson, S., Łuczak, T. and Rucinski, A., Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization (Wiley, New York, 2000).CrossRefGoogle Scholar
Kim, J. H., Sudakov, B. and Vu, V., Small subgraphs of random regular graphs, Discrete Math. 307 (2007), 1961–1967.10.1016/j.disc.2006.09.032CrossRefGoogle Scholar
Landon, B. and Sosoe, P., Applications of mesoscopic CLTs in random matrix theory, Ann. Appl. Probab. 30 (2020), 2769–2795.CrossRefGoogle Scholar
Liebenau, A. and Wormald, N., Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph, J. Eur. Math. Soc. (JEMS), to appear.Google Scholar
McKay, B. D., Asymptotics for symmetric 0-1 matrices with prescribed row sums, Ars Combin. 19 (1985), 15–25.Google Scholar
McKay, B. D., Subgraphs of random graphs with specified degrees, Proceedings of the International Congress of Mathematicians, vol. IV (Hindustan Book Agency, New Delhi, 2010), 2489–2501.Google Scholar
McKay, B. D., Subgraphs of dense random graphs with specified degrees, Combin. Probab. Comput. 20 (2011), 413–433.CrossRefGoogle Scholar
McKay, B. D. and Wormald, N. C., Asymptotic enumeration by degree sequence of graphs of high degree, European J. Combin. 11 (1990), 565–580.CrossRefGoogle Scholar
McKay, B. D. and Wormald, N. C., Asymptotic enumeration by degree sequence of graphs with degrees $o(n^{1/2})$, Combinatorica 11 (1991), 369–382.10.1007/BF01275671CrossRefGoogle Scholar
McKay, B. D., Wormald, N. C. and Wysocka, B., Short cycles in random regular graphs, Electron. J. Combin. 11 (2004), 12.CrossRefGoogle Scholar
Rigollet, P. and Weed, J., Uncoupled isotonic regression via minimum Wasserstein deconvolution, Inf. Inference 8 (2019), 691–717.10.1093/imaiai/iaz006CrossRefGoogle Scholar
Ruciński, A., When are small subgraphs of a random graph normally distributed?, Probab. Theory Related Fields 78 (1988), 1–10.CrossRefGoogle Scholar
Sinai, Y. and Soshnikov, A., Central limit theorem for traces of large random symmetric matrices with independent matrix elements, Bull. Braz. Math. Soc. (N.S.) 29 (1998), 1–24.CrossRefGoogle Scholar
Wormald, N., Asymptotic enumeration of graphs with given degree sequence, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited Lectures (World Scientific, Hackensack, NJ, 2018), 3245–3264.Google Scholar
Wormald, N. C., The asymptotic distribution of short cycles in random regular graphs, J. Combin. Theory Ser. B 31 (1981), 168–182.CrossRefGoogle Scholar