Upper tails for subgraph counts in random graphs

LetG be a fixed graph and letXG be the number of copies ofG contained in the random graphG(n, p). We prove exponential bounds on the upper tail ofXG which are best possible up to a logarithmic factor in the exponent. Our argument relies on an extension of Alon’s result about the maximum number of co...

Full description

Saved in:
Bibliographic Details
Published in:Israel journal of mathematics 2004-01, Vol.142 (1), p.61-92
Main Authors: Janson, Svante, Oleszkiewicz, Krzysztof, Ruciński, Andrzej
Format: Article
Language:English
Subjects:
Graph theory
Mathematics
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:LetG be a fixed graph and letXG be the number of copies ofG contained in the random graphG(n, p). We prove exponential bounds on the upper tail ofXG which are best possible up to a logarithmic factor in the exponent. Our argument relies on an extension of Alon’s result about the maximum number of copies ofG in a graph with a given number of edges. Similar bounds are proved for the random graphG(n, M) too.
ISSN:0021-2172
1565-8511
DOI:10.1007/BF02771528