Distribution of subgraphs of random regular graphs |
| |
| Authors: | Zhicheng Gao N.C. Wormald |
| |
| Affiliation: | 1. School of Mathematics and Statistics, Carleton University, Ottawa, Ontario, Canada K1S5B6;2. Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, China;3. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 |
| |
| Abstract: | We obtain the asymptotic distribution of the number of copies of a fixed subgraph H in a random d‐regular graph, provided H is strictly balanced and d = d(n) is chosen so that the expected number of copies of H tends to infinity (but not too quickly), and the expected number of copies sharing edges with two other copies is bounded. The proof of asymptotic normality of the distribution uses a method of factorial moments for variables with unbounded means that was recently derived by the authors. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008 |
| |
| Keywords: | random regular graphs normal distribution subgraphs moments |
|
|
