Premium
Distribution of subgraphs of random regular graphs
Author(s) -
Gao Zhicheng,
Wormald N.C.
Publication year - 2008
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20189
Subject(s) - mathematics , combinatorics , random graph , asymptotic distribution , struct , infinity , bounded function , discrete mathematics , distribution (mathematics) , random regular graph , graph , line graph , pathwidth , statistics , computer science , mathematical analysis , estimator , programming language
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