Counting Candidate Independent Sets
In a random graph, the existence of a large independent set can be studied by counting all vertex sets that could be one. The first-moment method does not need the candidate sets to occur independently: it computes their expected number, then uses that expectation to bound the probability that the number is positive. The resulting estimate is useful when the expected number is less than \(1\).
Throughout, \(n\ge1\), \(0\le p\le1\), and \(1\le k\le n\) are integers except for the real parameter \(p\). The random graph \(G(n,p)\) has vertex set \(\{1,\ldots,n\}\); each possible edge is included with probability \(p\), independently of every other possible edge. All graphs considered are finite and simple. An independent set is a set of vertices with no edge between any two of them. The independence number \(\alpha(G)\) is the largest size of an independent set in \(G\).
For a fixed \(k\)-vertex set \(S\), independence requires that all \(\binom{k}{2}\) possible edges with both endpoints in \(S\) be absent. Each is absent with probability \(1-p\), and these edge choices are independent. Thus the probability that this particular \(S\) is independent is \((1-p)^{\binom{k}{2}}\). There are \(\binom{n}{k}\) possible choices of \(S\).
Proof. For each \(k\)-vertex set \(S\subseteq\{1,\ldots,n\}\), let \(I_S\) be \(1\) if \(S\) is independent and \(0\) otherwise. Then \(X_k=\sum_{|S|=k} I_S\). The probability calculation above gives \(\mathbb{E}[I_S]=(1-p)^{\binom{k}{2}}\) for every such \(S\). By linearity of expectation, which does not require the indicators to be independent, $$ \mathbb{E}[X_k]=\sum_{|S|=k}\mathbb{E}[I_S] =\binom{n}{k}(1-p)^{\binom{k}{2}}. $$ \(\square\)
The First-Moment Upper Bound
Having an independent set of size at least \(k\) is equivalent to having one of size exactly \(k\): any \(k\)-vertex subset of a larger independent set is still independent. Therefore the event \(\{\alpha(G(n,p))\ge k\}\) is exactly \(\{X_k\ge1\}\).
Proof. Since \(X_k\) is a nonnegative integer, \(X_k\ge1\) on the event \(X_k\ge1\). Hence \(X_k\ge \mathbf{1}_{\{X_k\ge1\}}\) for every outcome, where the indicator on the right is \(1\) on that event and \(0\) otherwise. Taking expectations gives \(\mathbb{E}[X_k]\ge\mathbb{P}(X_k\ge1)\). Substitute the formula for \(\mathbb{E}[X_k]\) from the Proposition and use the event equivalence to obtain the bound. If the bound is less than \(1\), then \(\mathbb{P}(X_k=0)=1-\mathbb{P}(X_k\ge1)>0\), and \(X_k=0\) means \(\alpha(G(n,p))\le k-1\). \(\square\)
The estimate is an upper bound on the probability, not a formula for it. Its strength comes from a small expected count: if the expected number of candidates is less than \(1\), the probability that at least one candidate occurs is also less than \(1\). If the expectation is at least \(1\), this argument may still be valid, but its upper bound is then at least \(1\) and gives no nontrivial probability information.
Worked Example: A Bound for \(G(8,1/2)\)
Take \(n=8\), \(p=1/2\), and \(k=5\). There are \(\binom{8}{5}=56\) candidate sets. For a fixed five-vertex set, there are \(\binom{5}{2}=10\) possible internal edges, all of which must be absent. The probability of that is \((1/2)^{10}=1/1024\). Therefore $$ \mathbb{E}[X_5]=56\cdot\frac{1}{1024} =\frac{56}{1024}=\frac{7}{128}. $$ The first-moment bound gives \(\mathbb{P}(\alpha(G(8,1/2))\ge5)\le7/128\). Thus the probability that \(\alpha(G(8,1/2))\le4\) is at least \(1-7/128=121/128\).
Check: \(7/128<1\), so the theorem does imply positive probability of having no independent set of size \(5\). The complement probability bound is \(1-7/128=121/128\), as stated.
A Convenient Exponential Form
The exact expression can be simplified to give a criterion that is easier to inspect as \(n\) and \(k\) vary. Write \(q=1-p\). For \(1\le k\le n\), the elementary estimates $$ \binom{n}{k}\le\frac{n^k}{k!} \qquad\text{and}\qquad k!\ge\left(\frac{k}{e}\right)^k $$ give \(\binom{n}{k}\le(en/k)^k\). To justify the second estimate, for \(k\ge1\) the monotonicity of \(\ln x\) gives $$ \ln(k!)=\sum_{j=2}^{k}\ln j \ge\int_1^k\ln x\,dx =k\ln k-k+1 \ge k\ln k-k. $$ For \(k=1\), the sum and the integral are both \(0\), so the inequalities still hold. Exponentiating yields \(k!\ge(k/e)^k\).
Proof. Apply the binomial coefficient estimate to the exact expectation: $$ \mathbb{E}[X_k] =\binom{n}{k}(1-p)^{k(k-1)/2} \le\left(\frac{en}{k}\right)^k(1-p)^{k(k-1)/2} =\left(\frac{en}{k}(1-p)^{(k-1)/2}\right)^k. $$ If the displayed condition holds, this upper bound on the expectation is less than \(1\). The Theorem then gives the probability bound and the positive-probability conclusion. When \(p=1\) and \(k=1\), the factor with exponent \(0\) is interpreted as \(1\), consistent with the exact formula. \(\square\)
Worked Example: Applying the Exponential Criterion
Take \(G(12,1/2)\) and \(k=8\). The base in the criterion is $$ \frac{e\cdot12}{8}\left(\frac12\right)^{7/2} =\frac{3e}{2\cdot8\sqrt{2}}. $$ Using \(e<3\) and \(\sqrt{2}>1\), this base is less than \(9/16\), which is less than \(1\). Its eighth power is therefore less than \(1\), so the Corollary applies.
The exact expectation checks the conclusion directly: $$ \binom{12}{8}\left(\frac12\right)^{\binom{8}{2}} =495\left(\frac12\right)^{28} =\frac{495}{268435456}<1. $$ Consequently, \(\mathbb{P}(\alpha(G(12,1/2))\ge8)\le495/268435456\). The probability that \(\alpha(G(12,1/2))\le7\) is at least $$ 1-\frac{495}{268435456} =\frac{268434961}{268435456}. $$
Check: \(\binom{12}{8}=495\), \(\binom{8}{2}=28\), and \(2^{28}=268435456\). Subtracting the numerator \(495\) from the denominator gives \(268434961\), so the stated complementary bound follows from the exact count.
How the Edge Probability Affects the Count
For a fixed \(n\) and \(k\), the expectation is \(\binom{n}{k}(1-p)^{\binom{k}{2}}\). When \(k\ge2\), increasing \(p\) decreases the probability that a particular candidate set is independent, and hence decreases the expected count. The exponent \(\binom{k}{2}\) matters: a candidate set of size \(k\) requires the absence of every possible edge among its vertices, not merely the absence of a particular collection of edges.
Worked Example: A Dense Random Graph
Let \(n=10\), \(p=3/4\), and \(k=4\). There are \(\binom{10}{4}=210\) candidate four-vertex sets. Each has \(\binom{4}{2}=6\) possible internal edges, and each edge is absent with probability \(1-p=1/4\). Thus $$ \mathbb{E}[X_4]=210\left(\frac14\right)^6 =\frac{210}{4096}=\frac{105}{2048}. $$ The first-moment bound gives \(\mathbb{P}(\alpha(G(10,3/4))\ge4)\le105/2048\). Therefore \(\mathbb{P}(\alpha(G(10,3/4))\le3)\ge1-105/2048=1943/2048\).
Check: \(105/2048<1\), and \(2048-105=1943\). Thus the bound is nontrivial and its complementary probability is computed correctly.
Common Pitfall: Candidate Events Need Not Be Independent
A tempting but generally incorrect step is to treat the events “\(S\) is independent” as independent for different \(k\)-vertex sets \(S\). For example, in \(G(8,1/2)\), let \(S=\{1,2,3,4\}\) and \(T=\{1,2,3,5\}\). Both candidate sets require the three edges \(12,13,23\) to be absent. Their events therefore share edge conditions and are not independent. In particular, it is not valid to compute the probability that at least one candidate works by raising a single-candidate probability to the number of candidates and using a product formula.
The correct calculation uses indicators and linearity of expectation. For \(G(8,1/2)\) and \(k=4\), each candidate has probability \((1/2)^{\binom{4}{2}}=1/64\), and there are \(\binom{8}{4}=70\) candidates. Hence \(\mathbb{E}[X_4]=70/64=35/32\). The first-moment inequality gives \(\mathbb{P}(\alpha(G(8,1/2))\ge4)\le35/32\), which is weaker than the trivial bound \(1\). It does not say that the probability equals \(35/32\), nor does it establish a useful upper bound in this case. The method becomes informative when the computed expectation is below \(1\).
The same reasoning works at the endpoints of the parameter range. If \(p=0\), every edge is absent, so \(X_k=\binom{n}{k}\) and the expectation formula gives \(\binom{n}{k}\); the bound is usually not useful. If \(p=1\) and \(k\ge2\), no \(k\)-vertex set is independent, and the formula gives expectation \(0\). For \(k=1\), every single vertex is independent, so \(X_1=n\); the formula also gives \(n\), since \(\binom{1}{2}=0\). Keeping these cases in view helps distinguish an exact expectation from a probability that an event occurs.
Check Your Understanding
In each question, specify the candidate-set size and the probability that a fixed candidate is independent before drawing a conclusion.
- For \(G(7,1/2)\), compute \(\mathbb{E}[X_3]\) and use the first-moment bound to bound the probability that there is an independent set of size at least \(3\).
- For \(G(9,1/3)\), write the exact formula for \(\mathbb{E}[X_5]\). Does the first-moment bound show that the probability of an independent set of size at least \(5\) is less than \(1\)?
- Explain why the indicators for two candidate sets that share vertices need not be independent, and why this does not affect the expectation calculation.
- State what the first-moment estimate implies if \(\mathbb{E}[X_k]<1\), and explain why the same conclusion does not follow when \(\mathbb{E}[X_k]\ge1\).