A Large Deviation Result on the Number of Small Subgraphs of a Random Graph
VAN H. VU
Source record
Source: Crossref
Published: Jan 1, 2001
DOI: 10.1017/s0963548300004545
Open original source ↗Source abstract
Fix a small graph H and let Y H denote the number of copies of H in the random graph G ( n , p ). We investigate the degree of concentration of Y H around its mean, motivated by the following questions. [bull ] What is the upper tail probability Pr( Y H [ges ] (1 + ε)[ ]( Y H ))? [bull ] For which λ does Y H 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].
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.