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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom