1. Subgraph distributions in dense random regular graphs.
- Author
-
Sah, Ashwin and Sawhney, Mehtaab
- Subjects
- *
RANDOM graphs , *REGULAR graphs , *GRAPH connectivity , *ASYMPTOTIC distribution , *MATHEMATICIANS , *CENTRAL limit theorem - 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)$. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF