Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings

preprint2011arXivOpen access

Abstract

A concentration of measure result is proved for the number of isolated vertices YY in the Erdős-Rényi random graph model on nn edges with edge probability pp. When μμ and σ2σ^2 denote the mean and variance of YY respectively, P((Y−μ)/σ≥t)P((Y-μ)/σ\ge t) admits a bound of the form e−kt2e^{-kt^2} for some constant positive kk under the assumption p∈(0,1)p \in (0,1) and np→c∈(0,∞)np\rightarrow c \in (0,\infty) as n→∞n \rightarrow \infty. The left tail inequality $$ P(\frac{Y-μ}σ\le -t)&\le& \exp(-\frac{t^2σ^2}{4μ}) $$ holds for all n∈2,3,...,p∈(0,1)n \in {2,3,...},p \in (0,1) and t≥0t \ge 0. The results are shown by coupling YY to a random variable YsY^s having the YY-size biased distribution, that is, the distribution characterized by E[Yf(Y)]=μE[f(Ys)]E[Yf(Y)]=μE[f(Y^s)] for all functions ff for which these expectations exist.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.