Concentration of Edges and Vertex Degrees

From Expected Values to Concentration

Knowing the expected number of edges in a random graph does not by itself tell us whether a typical graph has close to that many edges. Concentration bounds answer a stronger question: how likely is a substantial deviation from the mean? The same question applies to the degree of one vertex, and to all vertex degrees at once.

Throughout, \(G(n,p)\) is the random simple graph on vertex set \(\{1,\dots,n\}\) in which each possible edge is included independently with probability \(p\), where \(n\ge 1\) and \(0\le p\le 1\). Let \(X=|E(G(n,p))|\) be its edge count, and let \(D_v=\deg(v)\) be the degree of a fixed vertex \(v\). The edge indicators are independent Bernoulli random variables, so \(X\) is binomial with mean \(\binom n2p\). For fixed \(v\), the \(n-1\) incident-edge indicators are independent, so \(D_v\) is binomial with mean \((n-1)p\). These are the expected counts; concentration bounds control their deviations.

A Binomial Tail Bound

Proof. Write \(X=\sum_i Y_i\), where the \(Y_i\) are independent Bernoulli random variables with \(\Pr(Y_i=1)=q_i\), so \(\mu=\sum_i q_i\). For every real \(s\), independence and the inequality \(1+z\le e^z\) give $$ \mathbb E(e^{sX}) =\prod_i\bigl(1+q_i(e^s-1)\bigr) \le \exp\bigl(\mu(e^s-1)\bigr). $$ For the upper tail, take \(s=\ln(1+\delta)>0\). Markov's inequality applied to \(e^{sX}\) gives $$ \Pr(X\ge(1+\delta)\mu) \le \exp\bigl(-\mu h(\delta)\bigr),\qquad h(\delta)=(1+\delta)\ln(1+\delta)-\delta. $$ For \(0\le x\le1\), \(\ln(1+x)\ge 2x/(2+x)\): the difference is zero at \(x=0\), and its derivative is \(x^2/((1+x)(2+x)^2)\ge0\). Also \(2x/(2+x)\ge2x/3\) on this interval. Therefore \(h'(x)=\ln(1+x)\ge2x/3\). Integrating from \(0\) to \(\delta\) gives \(h(\delta)\ge\delta^2/3\), so the upper-tail probability is at most \(\exp(-\delta^2\mu/3)\).

For \(0<\delta<1\), put \(t=-\ln(1-\delta)>0\). On the event \(X\le(1-\delta)\mu\), \(e^{-tX}\ge e^{-t(1-\delta)\mu}\). Markov's inequality and the same product estimate give $$ \Pr(X\le(1-\delta)\mu) \le\exp\bigl(-\mu g(\delta)\bigr),\qquad g(\delta)=\delta+(1-\delta)\ln(1-\delta). $$ Since \(g'(x)=-\ln(1-x)\ge x\) for \(0\le x<1\), integration gives \(g(\delta)\ge\delta^2/2\ge\delta^2/3\). At \(\delta=1\), the lower-tail bound follows by taking the limit as \(\delta\) increases to \(1\). Adding the upper- and lower-tail bounds proves the two-sided inequality. Finally, the strict event \(|X-\mu|>t\) is contained in \(|X-\mu|\ge t\), proving the stated version for \(t=\delta\mu\). \(\square\)

The theorem applies to any sum of independent Bernoulli variables, including the edge count and one fixed degree in \(G(n,p)\). The edge indicators for different vertices' degrees are not all distinct: for example, \(D_u\) and \(D_v\) both involve the indicator of \(uv\). Thus degrees are generally dependent, but this does not prevent bounding the probability of a deviation at any vertex.

Concentration of the Edge Count

More generally, when \(p>0\) and \(n\ge2\), the edge count has mean \(\mu_E=\binom n2p\). For any fixed \(0<\varepsilon\le1\), applying the theorem with \(\delta=\varepsilon\) yields $$ \Pr\bigl(|X-\mu_E|>\varepsilon\mu_E\bigr) \le2\exp\left(-\frac{\varepsilon^2\mu_E}{3}\right). $$ In particular, if \(\mu_E\) tends to infinity along a sequence of choices of \(n\) and \(p\), the probability of a fixed positive relative deviation tends to zero. If \(p=0\) or \(n=1\), then \(X=0\) deterministically, so there is no deviation to bound.

One Vertex Degree and All Degrees

For a fixed vertex \(v\), if \(p>0\) and \(n\ge2\), the mean degree is \(\mu_D=(n-1)p\). Hence, for \(0<\varepsilon\le1\), $$ \Pr\bigl(|D_v-\mu_D|>\varepsilon\mu_D\bigr) \le2\exp\left(-\frac{\varepsilon^2\mu_D}{3}\right). $$ This gives concentration for one chosen vertex when its expected degree grows. It does not by itself guarantee that every vertex has a degree near the mean: there are \(n\) vertices to consider.

Proof. For each vertex \(v\), let \(A_v\) be the event that \(|D_v-(n-1)p|>\varepsilon(n-1)p\). The probability of the union of finitely many events is at most the sum of their probabilities. Applying the degree bound to each of the \(n\) vertices gives $$ \Pr\left(\bigcup_{v\in V}A_v\right) \le\sum_{v\in V}\Pr(A_v) \le n\cdot2\exp\left(-\frac{\varepsilon^2(n-1)p}{3}\right). $$ This is the claimed bound. No independence between the events \(A_v\) is required. \(\square\)

When Does Simultaneous Concentration Follow?

The corollary reveals an important difference between a single degree and all degrees. For a fixed tolerance \(\varepsilon\), the one-vertex bound becomes small when \((n-1)p\) grows. For the bound over all vertices to tend to zero, it is sufficient that $$ \frac{\varepsilon^2(n-1)p}{3}-\ln(2n)\longrightarrow+\infty. $$ Indeed, the right-hand side of the corollary is \( \exp\bigl(\ln(2n)-\varepsilon^2(n-1)p/3\bigr)\), which tends to zero under that condition. In particular, for fixed \(0<\varepsilon\le1\), the condition \((n-1)p/\ln n\to\infty\) is sufficient.

This is a sufficient condition from the bound, not a necessary condition for simultaneous concentration. When the expected degree is small compared with \(\ln n\), this union-bound estimate may fail to be informative; a bound larger than \(1\) is still a valid upper bound, but it does not establish a useful probability guarantee. Also, “every degree is close to its mean” refers here to a relative tolerance around \((n-1)p\), not to all degrees being equal.

Common Pitfall: Rounding and the Union Bound

A small rounding error can make a numerical probability claim inaccurate. For example, writing \(2e^{-3.3}\approx0.0739\) is not the correct rounding to three significant figures: direct evaluation gives approximately \(0.073766\), which rounds to \(0.0738\). Likewise, \(2e^{-1.65}\approx0.385\) is not correct to three significant figures: direct evaluation gives approximately \(0.384100\), which rounds to \(0.384\). Keeping the exponential expression exact until the final evaluation avoids this mistake.

A different pitfall is to multiply a one-vertex probability by \(n\) while assuming the degree-deviation events are independent. They need not be. The union bound justifies the multiplication without independence: the probability that at least one event occurs is no greater than the sum of the individual probabilities. This is why the simultaneous estimate is valid even though degrees share edge indicators.