Distribution of subgraphs of random regular graphs

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...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2008-01, Vol.32 (1), p.38-48
Main Authors: Gao, Zhicheng, Wormald, N.C.
Format: Article
Language:English
Subjects:
moments
normal distribution
random regular graphs
subgraphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.20189