Bounded Differences for Random Graph Statistics

Why Edge Changes Control Graph Statistics

A graph statistic can depend on many edges without being very sensitive to any one of them. Changing one edge in a large graph may alter a count by only a small amount; if the edges are generated independently, this limited influence leads to concentration around the statistic’s expectation. The key calculation is not just how many edges the graph has, but how much the statistic can change when a single edge is toggled.

We consider a simple undirected graph on $n$ labelled vertices, with no loops or multiple edges. Its potential edges are the unordered pairs in $\mathcal E_n=\{\{u,v\}:1\leq u<v\leq n\}$, so there are $m=\binom{n}{2}$ potential edges. For each $e\in\mathcal E_n$, let $X_e$ be 1 if $e$ is present and 0 otherwise. The independent-edge model assumes that the indicators $X_e$ are mutually independent; in $G(n,p)$, each has the Bernoulli distribution with success probability $p$.

Definition: For a graph statistic $T=T((X_e)_{e\in\mathcal E_n})$, its coordinate change bound for edge $e$ is a number $c_e\geq 0$ such that changing $X_e$ from 0 to 1, or from 1 to 0, changes $T$ by at most $c_e$, for every fixed configuration of all the other edges. The bound is required to hold uniformly over those configurations.

The word “uniformly” matters: an average change, or a change observed in a typical graph, is not enough for the inequality below. The bounds may differ by edge. For a vertex degree, for instance, edges not incident to the vertex have change bound zero.

The Bounded-Differences Bound for Independent Edges

Theorem: Suppose $X_1,\ldots,X_m$ are independent random variables and $T=T(X_1,\ldots,X_m)$ is bounded. Suppose that replacing coordinate $i$, while fixing all other coordinates, changes $T$ by at most $c_i$. If $C=\sum_{i=1}^m c_i^2>0$, then for every $t>0$, $$ P(T-E[T]\geq t)\leq \exp\!\left(-\frac{2t^2}{C}\right),\qquad P(E[T]-T\geq t)\leq \exp\!\left(-\frac{2t^2}{C}\right). $$ Consequently, $P(|T-E[T]|\geq t)\leq 2\exp(-2t^2/C)$. If $C=0$, the statistic is constant on the possible input configurations, so each of these deviation probabilities is zero.

Here is a proof that makes explicit why the edge-change bounds enter as a sum of squares. The argument applies to any finite collection of independent inputs, and hence to the edge indicators of an independent-edge random graph.

Control each conditional increment.
Reveal the inputs in order and define $M_i=E[T\mid X_1,\ldots,X_i]$, with $M_0=E[T]$. For fixed $X_1,\ldots,X_{i-1}$, the possible values of $M_i$, as $X_i$ varies, lie in an interval of length at most $c_i$. Indeed, for any two values of $X_i$, couple the remaining inputs to be identical; the corresponding values of $T$ differ by at most $c_i$, and taking expectations over those remaining inputs preserves this bound. Thus $D_i=M_i-M_{i-1}$, conditionally on the first $i-1$ inputs, has mean zero and lies in an interval of length at most $c_i$.

Apply the bounded-variable exponential bound.
If a bounded, mean-zero random variable $Z$ lies in an interval of length $c$, then $E[e^{\lambda Z}]\leq e^{\lambda^2c^2/8}$ for every real $\lambda$. To verify this, let $\psi(\lambda)=\log E[e^{\lambda Z}]$. Boundedness permits differentiation; $\psi(0)=\psi'(0)=0$, and $\psi''(\lambda)$ is the variance under the probability distribution tilted by the factor $e^{\lambda Z}$. That tilted distribution is still supported on the same interval, so $\psi''(\lambda)\leq c^2/4$: a variable in an interval $[a,b]$ has variance at most $E[(Z-(a+b)/2)^2]\leq (b-a)^2/4$. Integrating this second-derivative bound from 0 to $\lambda$ gives $\psi(\lambda)\leq\lambda^2c^2/8$, for positive or negative $\lambda$.

Combine increments and optimize.
Apply the conditional exponential bound from Step 2 to each $D_i$, successively conditioning on the revealed inputs. Since $T-E[T]=\sum_iD_i$, this gives $E[e^{\lambda(T-E[T])}]\leq \exp(\lambda^2C/8)$. For $\lambda>0$, Markov’s inequality therefore yields $P(T-E[T]\geq t)\leq\exp(-\lambda t+\lambda^2C/8)$. Choosing $\lambda=4t/C$ gives the stated upper-tail bound. Apply the same argument to $-T$ for the lower tail, then add the two probabilities for the two-sided bound. $\square$

For a graph statistic, take one coordinate for each potential edge. The sum $C$ is then the sum of the squared edge change bounds. The theorem uses independence of the edge indicators, not identical edge probabilities: it applies to independent edges with different probabilities as well.

Worked Applications

Worked Example: Edge Count in $G(20,1/2)$

Let $E(G)$ be the number of present edges in $G(20,1/2)$. There are $\binom{20}{2}=190$ independent edge indicators, and toggling any one edge changes the count by exactly 1. Thus $c_e=1$ for all 190 edges and $C=190$.

Each edge is present with probability $1/2$, so by adding the expectations of the edge indicators, $$ E[E(G)]=190\cdot\frac12=95. $$ For a deviation of $t=30$, the two-sided bounded-differences inequality gives $$ P(|E(G)-95|\geq 30)\leq 2\exp\!\left(-\frac{2(30)^2}{190}\right) =2e^{-1800/190}\approx 0.000154. $$ This is a valid upper bound on the probability of having at most 65 edges or at least 125 edges. It is a bound, not an assertion that the probability equals the displayed value.

Worked Example: Degree of One Vertex in $G(50,0.1)$

Fix a vertex $v$, and let $D_v$ be its degree. Only the 49 potential edges incident to $v$ can change $D_v$; each changes it by 1. The other $\binom{50}{2}-49=1225-49=1176$ edges have change bound zero. Therefore $$ C=49\cdot 1^2+1176\cdot 0^2=49. $$

The degree is the sum of the 49 incident Bernoulli indicators, each with success probability 0.1, so $E[D_v]=49(0.1)=4.9$. Taking $t=10$, $$ P(|D_v-4.9|\geq 10)\leq 2\exp\!\left(-\frac{2(10)^2}{49}\right) =2e^{-200/49}\approx 0.0338. $$ Although a degree is an integer and its expectation is not, the inequality applies to the real-valued deviation from 4.9 exactly as stated.

Triangle Counts and Local Sensitivity

A triangle is a set of three vertices for which all three connecting edges are present. Let $T_\triangle$ count the triangles in a graph. Toggling an edge $\{u,v\}$ can only affect triangles that use that edge. Each such triangle needs one additional vertex $w$, and there are $n-2$ choices. This gives a uniform bound on the change.

Proposition: In a simple graph on $n\geq 2$ vertices, changing one edge changes the number of triangles by at most $n-2$. Consequently, in $G(n,p)$, for $n\geq 3$ and $0<p<1$, $$ P\!\left(\left|T_\triangle-E[T_\triangle]\right|\geq t\right) \leq 2\exp\!\left(-\frac{2t^2}{\binom{n}{2}(n-2)^2}\right),\qquad t>0. $$

To prove the change bound, fix all edges except $\{u,v\}$. A triangle’s status can change only if it contains both $u$ and $v$. Such a triangle is uniquely specified by its third vertex $w$, and there are $n-2$ possible choices. In the fixed configuration, toggling $\{u,v\}$ can therefore add or remove at most $n-2$ triangles. Assigning $c_e=n-2$ to each of the $\binom{n}{2}$ possible edges gives $C=\binom{n}{2}(n-2)^2$; the theorem proves the probability bound. $\square$

Worked Example: Triangle Count in $G(30,0.2)$

There are $\binom{30}{2}=435$ possible edges. Each set of three vertices forms a triangle precisely when its three distinct edges are all present. Independence gives probability $0.2^3=0.008$ for this event. Summing the triangle indicators over all $\binom{30}{3}=4060$ vertex triples, $$ E[T_\triangle]=\binom{30}{3}(0.2)^3=4060(0.008)=32.48. $$

Changing one edge can affect at most $30-2=28$ triangles, so the sum of squared change bounds is $$ C=435(28)^2=435(784)=341040. $$ For a deviation of $t=1000$, the two-sided bound is $$ P(|T_\triangle-32.48|\geq 1000) \leq 2\exp\!\left(-\frac{2(1000)^2}{341040}\right) =2e^{-5.8648\ldots}\approx 0.0057. $$ This large-deviation bound is valid but conservative: the same edge can participate in many possible triangles, so the worst-case change bound is much larger than the edge-count bound.

Choosing and Interpreting the Bounds

These examples follow the same procedure: identify the independent input coordinates, bound the change caused by each coordinate in every configuration, square and add those bounds, and substitute into the inequality. A general fixed subgraph count can be handled by the same idea: an edge can affect only copies of the subgraph that contain that edge. Counting those copies gives a coordinate change bound, though a crude worst-case count may yield a weak probability bound.

The bound is useful because it turns a structural property of a statistic—its response to a local edge change—into an explicit tail estimate. Its quality depends strongly on the sensitivity calculation. For example, using $n-1$ nonzero coordinates for a fixed vertex’s degree would be correct but wasteful; treating all $\binom n2$ edges as having a nonzero effect would be unnecessarily loose.

Common pitfall: Triangle indicators for different vertex triples are not generally independent: two triples may share edges. It is therefore incorrect to apply a sum-of-independent-indicators bound to the triangle count merely because it is written as a sum. The bounded-differences argument instead uses the independence of the underlying edge indicators and a valid bound on how changing one of them affects the entire statistic.

The independent-edge assumption is essential to this theorem. A graph sampled uniformly from all graphs with exactly $k$ edges has dependent edge indicators, so the independent-input result cannot be applied to that model without an additional argument. Likewise, a change bound must cover every allowed configuration; observing that an edge usually creates few triangles does not replace the uniform bound of $n-2$.

Key takeaway: For an independent-edge graph statistic, establish a uniform edge-toggle bound $c_e$ for every potential edge. The deviation probability is then controlled by $2\exp(-2t^2/\sum_e c_e^2)$. Accurate local sensitivity—not the name of the graph statistic—is what determines the bound.

Check Your Understanding

Use the edge-coordinate viewpoint to answer each question.

In $G(n,p)$, what is the coordinate change bound for the number of present edges, and what is the resulting sum of squared bounds?
Why are the change bounds for the degree of a fixed vertex zero on edges not incident to that vertex?
Explain why toggling one edge can affect at most $n-2$ triangles.
For $G(10,1/2)$, calculate the expected number of triangles by summing the probabilities of the $\binom{10}{3}$ possible triangles.
Why does the independent-edge bounded-differences theorem not apply directly to a graph chosen uniformly subject to having exactly $k$ edges?

Bounded Differences for Random Graph Statistics

What You'll Learn

Why Edge Changes Control Graph Statistics

The Bounded-Differences Bound for Independent Edges

Worked Applications

Worked Example: Edge Count in \(G(20,1/2)\)

Worked Example: Degree of One Vertex in \(G(50,0.1)\)

Triangle Counts and Local Sensitivity

Worked Example: Triangle Count in \(G(30,0.2)\)

Choosing and Interpreting the Bounds

Check Your Understanding

Bounded Differences for Random Graph Statistics

What You'll Learn

Why Edge Changes Control Graph Statistics

The Bounded-Differences Bound for Independent Edges

Worked Applications

Worked Example: Edge Count in \(G(20,1/2)\)

Worked Example: Degree of One Vertex in \(G(50,0.1)\)

Triangle Counts and Local Sensitivity

Worked Example: Triangle Count in \(G(30,0.2)\)

Choosing and Interpreting the Bounds

Check Your Understanding

Previous

Next