Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-12T18:35:45.491Z Has data issue: false hasContentIssue false
  • English
  • Français

A Large Deviation Result on the Number of Small Subgraphs of a Random Graph

Published online by Cambridge University Press:  12 April 2001

VAN H. VU
VAN H. VU
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA (e-mail: vanhavu@@microsoft.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Fix a small graph H and let YH denote the number of copies of H in the random graph G(n, p). We investigate the degree of concentration of YH around its mean, motivated by the following questions.

[bull] What is the upper tail probability Pr(YH [ges ] (1 + ε)[](YH))?

[bull] For which λ does YH have sub-Gaussian behaviour, namely

(formula here)

where c is a positive constant?

[bull] Fixing λ = ω(1) in advance, find a reasonably small tail T = T(λ) such that

(formula here)

We prove a general concentration result which contains a partial answer to each of these questions. The heart of the proof is a new martingale inequality, due to J. H. Kim and the present author [13].

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 10 , Issue 1 , January 2001, pp. 79 - 94
Copyright
2001 Cambridge University Press