论文标题
密集的随机常规图中的子图分布
Subgraph distributions in dense random regular graphs
论文作者
论文摘要
给定连接的图形$ h $（不是恒星），我们表明密集的随机常规图中$ h $的副本数量是渐近的高斯，即使$ h $也不是三角形。这解决了2010年国际数学家大会的麦凯问题。实际上，我们证明，$ h $的副本数量的差异的行为微妙地取决于$ 3,4,5 $的循环的发生和循环数，以及$ h $中$ 3 $的路径。更普遍地，我们可以控制某些有界程度统计量的渐近分布，这些分布在顶点排列下是不变的，包括随机常规图的光谱。 我们的技术是基于通过McKay和Wormald列举常规图的组合，该方法与Janson在研究$ \ Mathbb {g}（n，p）$中开发的图形因子的概念。
Given 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 length $3,4,5$ as well as paths of length $3$ 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)$.
