Controlling Several Obstructions at Once
A random graph may be unlikely to contain any one particular obstruction, yet a construction often needs to avoid several kinds at the same time. Examples include avoiding both a triangle and a cycle of length four, or avoiding a specified list of subgraphs in a Ramsey-type existence argument. The union bound gives a direct method: bound the probability of each obstruction, add those bounds, and check whether the sum is less than \(1\). No independence between the obstruction events is needed.
For \(n\ge 1\) and \(0\le p\le 1\), the random graph \(G(n,p)\) has vertex set \([n]=\{1,\ldots,n\}\). Each of the \(\binom n2\) possible edges is included independently with probability \(p\). A copy of a graph \(H\) means a subgraph isomorphic to \(H\), not necessarily an induced subgraph: all edges of \(H\) must appear, while additional edges among its vertices are allowed.
The Union Bound and Its Existence Consequence
Proof. For each outcome \(\omega\), let \(\mathbf{1}_{B_i}(\omega)\) equal \(1\) if \(\omega\in B_i\) and \(0\) otherwise. If \(\omega\) belongs to at least one \(B_i\), then \(\sum_i\mathbf{1}_{B_i}(\omega)\ge 1\); if it belongs to none, then the sum is \(0\). Thus, for every outcome, \(\mathbf{1}_{\cup_i B_i}(\omega)\le\sum_i\mathbf{1}_{B_i}(\omega)\). Taking expectations gives the stated probability inequality, since the expectation of an event's indicator is its probability and expectation is additive for finite sums. If the sum of the probabilities is less than \(1\), then \(\Pr(\cup_i B_i)<1\), so its complement has positive probability and is nonempty. Any outcome in that complement avoids every \(B_i\). \(\square\)
The sum is an upper bound, not generally an equality. In particular, the theorem makes no assumption that the events are independent. If the sum is at least \(1\), the inequality is still true, but this argument alone gives no positive lower bound for the probability of avoiding all the events.
Bounding the Probability of a Forbidden Copy
Let \(H\) be a fixed finite simple graph with \(h=|V(H)|\ge 1\) vertices and \(q=|E(H)|\ge 1\) edges. An automorphism of \(H\) is a bijection from \(V(H)\) to itself that preserves adjacency in both directions; write \(\operatorname{aut}(H)\) for the number of automorphisms. The number of distinct copies of \(H\) on \([n]\), when \(n\ge h\), is \((n)_h/\operatorname{aut}(H)\), where \((n)_h=n(n-1)\cdots(n-h+1)\).
To see the count, first map the \(h\) vertices of \(H\) injectively into \([n]\). There are \((n)_h\) such maps. Two maps describe the same copy exactly when they differ by an automorphism of \(H\): the selected vertices and the required edges are then identical. Each copy is therefore counted \(\operatorname{aut}(H)\) times. For any fixed copy, all its \(q\) required edges must be present; independence of edge choices gives probability \(p^q\).
Proof. For each distinct copy \(C\) of \(H\), let \(B_C\) be the event that every edge required by \(C\) is present. The event that \(G(n,p)\) contains a copy of \(H\) is the union of the events \(B_C\). There are \((n)_h/\operatorname{aut}(H)\) such copies, and each \(B_C\) has probability \(p^q\). Applying the union bound gives the inequality. If \(n<h\), there are not enough vertices for a copy, so the event is impossible. \(\square\)
Because \((n)_h\le n^h\), a convenient, sometimes weaker, bound is \(n^h p^q/\operatorname{aut}(H)\). For several forbidden graphs \(H_1,\ldots,H_r\), each with at least one edge, let \(h_i=|V(H_i)|\), \(q_i=|E(H_i)|\). Applying the proposition to each type and then the union bound shows that the probability of at least one forbidden copy is at most
If the right-hand sum is less than \(1\), then a graph on \(n\) vertices avoiding every listed graph exists. The inequality is valid even if some types of copies overlap: the union bound allows overlap and simply may overestimate the probability.
Worked Example: Avoiding a Triangle and a Four-Cycle
Take \(G(4,1/2)\), and forbid both \(K_3\) and \(C_4\). There are \(\binom43=4\) choices of three vertices, each giving one triangle. Each triangle requires \(3\) edges, so its event has probability \((1/2)^3=1/8\). The sum of the four triangle-copy probabilities is \(4(1/8)=1/2\).
For a \(C_4\), choose all four vertices. There are \(3\) distinct cycles on that set: fixing one vertex, the other three can be ordered around the cycle in \(3!/2=3\) ways, where reversal gives the same cycle. Each cycle requires \(4\) edges, so its event has probability \((1/2)^4=1/16\). The sum for the four-cycle copies is \(3(1/16)=3/16\).
The union bound gives \(\Pr(\text{a triangle or a }C_4)\le 1/2+3/16=11/16\). Therefore the probability of avoiding both is at least \(1-11/16=5/16>0\). In particular, at least one graph on these four vertices has neither obstruction.
Check: the copy counts also follow from automorphisms: \(4!/((3!))=4\) triangle copies and \(4!/(8)=3\) four-cycle copies. Substituting their edge counts gives \(4(1/2)^3=1/2\) and \(3(1/2)^4=3/16\), as above.
Worked Example: A Three-Vertex Path and a Triangle
In \(G(5,1/10)\), forbid \(P_3\), the path on three vertices, and \(K_3\). A \(P_3\) copy is determined by choosing three vertices and choosing which of the three possible pairs is the missing edge. Thus there are \(\binom53\cdot3=10\cdot3=30\) copies. Equivalently, \(\operatorname{aut}(P_3)=2\), so the count is \((5)_3/2=(5\cdot4\cdot3)/2=30\). Each copy requires \(2\) edges and has probability \((1/10)^2=1/100\), giving the bound \(30/100=3/10\).
There are \(\binom53=10\) triangle copies. Each requires \(3\) edges, so the sum of their probabilities is \(10(1/10)^3=10/1000=1/100\). Adding the two obstruction bounds gives \(3/10+1/100=31/100<1\). Hence the probability of avoiding both types is at least \(1-31/100=69/100\), so such a graph exists.
Check: the triangle count is \((5)_3/6=(5\cdot4\cdot3)/6=10\), since \(\operatorname{aut}(K_3)=6\). The calculated probability bounds use \(30\) copies with two required edges and \(10\) copies with three required edges, matching the direct counts.
A Parameter Choice for Several Forbidden Graphs
The copy bounds can also show that the probability of any listed obstruction tends to zero as \(n\) grows. Consider a fixed finite list \(H_1,\ldots,H_r\) in which every graph has at least one edge. Choose \(p=n^{-a}\), where \(a>0\). For each \(i\), the convenient copy bound is \[ \frac{n^{h_i}p^{q_i}}{\operatorname{aut}(H_i)} =\frac{n^{h_i-aq_i}}{\operatorname{aut}(H_i)}. \] If \(a>h_i/q_i\) for every \(i\), then \(h_i-aq_i<0\) for every \(i\). Each term tends to zero, and because the list is finite, their sum tends to zero. In particular, for all sufficiently large \(n\) the sum is less than \(1\), giving a graph with no copy of any listed \(H_i\).
Graphs with no edges require separate care. If an edgeless graph has \(h\ge1\) vertices, then for \(n\ge h\) it appears as a subgraph of every graph on \([n]\): choose any \(h\) vertices and take no edges in the subgraph. Its occurrence probability is \(1\), not \(p^0\) times a decaying factor. Thus the ratio \(h/q\) is not defined when \(q=0\), and the decay criterion above applies only when every forbidden graph has at least one edge. If an edgeless graph is on more vertices than \(G(n,p)\), it cannot occur, but that is a finite-size vertex-count issue rather than a probability estimate.
Worked Example: Simultaneously Avoiding \(K_3\) and \(C_4\) for Large \(n\)
Let \(p=n^{-3/2}\), and forbid \(K_3\) and \(C_4\). For the triangle, \(h=3\), \(q=3\), and \(\operatorname{aut}(K_3)=6\). Its copy-probability sum is at most \(n^3p^3/6=n^3(n^{-3/2})^3/6=1/(6n^{3/2})\). For the four-cycle, \(h=4\), \(q=4\), and \(\operatorname{aut}(C_4)=8\). Its sum is at most \(n^4p^4/8=n^4(n^{-3/2})^4/8=1/(8n^2)\).
At \(n=4\), these two upper bounds are \(1/(6\cdot4^{3/2})=1/48\), since \(4^{3/2}=8\), and \(1/(8\cdot4^2)=1/128\), since \(4^2=16\). Their sum is \(1/48+1/128=8/384+3/384=11/384<1\). For every \(n\ge4\), both positive terms are no larger than their values at \(n=4\), so their sum remains less than \(1\). The union bound therefore guarantees a graph avoiding both \(K_3\) and \(C_4\) for every \(n\ge4\).
Check: the exponent tests agree: \(3/3=1\) and \(4/4=1\), while \(a=3/2>1\) in both cases. The computed powers are \(p^3=n^{-9/2}\) and \(p^4=n^{-6}\); multiplying by \(n^3/6\) and \(n^4/8\) gives \(n^{-3/2}/6\) and \(n^{-2}/8\), respectively.
Common Pitfall: Multiplying Avoidance Probabilities
It is tempting to treat two obstruction events as independent and multiply their avoidance probabilities. That is not justified merely because the events are described by different subgraphs: their required edge sets may overlap.
For a concrete example in \(G(4,1/2)\), let \(A\) be the event that the edges \(12,23,13\) are all present, and let \(B\) be the event that the edges \(12,23,34,41\) are all present. Then \(\Pr(A)=1/8\) and \(\Pr(B)=1/16\). Both occur exactly when the five distinct edges \(12,23,13,34,41\) are present, so \(\Pr(A\cap B)=(1/2)^5=1/32\). Independence would instead require \(\Pr(A\cap B)=\Pr(A)\Pr(B)=(1/8)(1/16)=1/128\), which is false. Consequently, the independence calculation \(\Pr(A\cup B)=1-(1-1/8)(1-1/16)=23/128\) is not valid; the actual value is \(1/8+1/16-1/32=5/32=20/128\).
The union bound avoids this error. It always gives \(\Pr(A\cup B)\le1/8+1/16=3/16\), whether or not the events overlap. For a family of forbidden subgraphs, count the possible copies, compute the probability required for each copy, and add those bounds. A total strictly below \(1\) is the decisive condition for existence.
Check Your Understanding
Use the copy bounds and the union bound where appropriate. When a probability estimate is requested, distinguish the bound from the exact probability.
- In \(G(6,1/2)\), how many distinct triangle copies are there, and what is the sum of their individual occurrence probabilities?
- For \(G(n,p)\), derive the copy bound for a fixed graph with \(h\) vertices, \(q\ge1\) edges, and \(\operatorname{aut}(H)\) automorphisms.
- Suppose a finite list of forbidden graphs has parameters \((h_i,q_i)\) with every \(q_i\ge1\). State a sufficient condition on \(a\) for the union-bound sum with \(p=n^{-a}\) to tend to zero.
- Why does the same decay criterion not apply to a forbidden edgeless graph on \(h\) vertices when \(n\ge h\)?
- Give a reason the union bound remains valid when two bad events are dependent, and explain why multiplying their avoidance probabilities may fail.