Portal de Periódicos da CAPES

Upper tails for subgraph counts in random graphs

2004; Hebrew University of Jerusalem; Volume: 142; Issue: 1 Linguagem: Inglês

10.1007/bf02771528

1565-8511

Svante Janson, Krzysztof Oleszkiewicz, Andrzej Ruciński,

Graph theory and applications

LetG be a fixed graph and letX G be the number of copies ofG contained in the random graphG(n, p). We prove exponential bounds on the upper tail ofX G 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.