Random Graphs Without Large Cliques or Independent Sets

Counting Two Opposing Obstructions

A clique is encouraged by edges, whereas an independent set is encouraged by missing edges. In a random graph, increasing the edge probability therefore makes large cliques more likely and large independent sets less likely. The useful question is quantitative: how many sets of a given size do we expect to have each property, and can we choose the edge probability so that these expectations are small?

For an integer $n\ge 1$ and a real number $p$ with $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$. All graphs in this discussion are finite and simple. Fix target sizes $r,s$ with $2\le r,s\le n$. A clique of size $r$ is a set of $r$ vertices with every possible edge present; an independent set of size $s$ is a set of $s$ vertices with every possible edge absent.

Definition: Let $X_r$ be the number of $r$-vertex subsets that induce a clique in $G(n,p)$, and let $Y_s$ be the number of $s$-vertex subsets that induce an independent set. These are random nonnegative integers. They count sets, not merely whether at least one such set exists.

The restriction $r,s\ge2$ keeps both relevant edge counts positive. If a graph has a clique of size at least $r$, then any $r$ vertices of that clique form a clique of size $r$. Likewise, an independent set of size at least $s$ contains an independent $s$-vertex subset. Thus, ruling out the specified sizes also rules out all larger sizes.

Expected Numbers of Cliques and Independent Sets

Theorem: In $G(n,p)$, for $2\le r,s\le n$, $$ \mathbb{E}[X_r]=\binom nr p^{\binom r2}, \qquad \mathbb{E}[Y_s]=\binom ns(1-p)^{\binom s2}. $$

Proof. For each $r$-vertex subset $A\subseteq[n]$, let $I_A$ equal $1$ if $A$ induces a clique and $0$ otherwise. Then $X_r=\sum_{|A|=r} I_A$. The set $A$ has $\binom r2$ possible internal edges. They are all present with probability $p^{\binom r2}$, by independence of edge choices, so $\mathbb{E}[I_A]=p^{\binom r2}$. There are $\binom nr$ such subsets. Linearity of expectation, which does not require the indicators to be independent, gives the first formula.

For each $s$-vertex subset $B$, define $J_B=1$ if it induces an independent set and $J_B=0$ otherwise. All $\binom s2$ internal edges must be absent, an event of probability $(1-p)^{\binom s2}$. Since $Y_s=\sum_{|B|=s}J_B$, summing the expectations over the $\binom ns$ choices of $B$ gives the second formula. The formulas also hold at $p=0$ and $p=1$, since the exponents are positive. $\square$

These expectations can be larger than $1$: they are average counts, not probabilities. The first-moment existence lemma says that if a nonnegative integer-valued random variable has expectation less than $1$, some outcome has value $0$. The simultaneous version follows by applying this idea to the total number of obstructions.

Criterion: If $$ \binom nr p^{\binom r2}+\binom ns(1-p)^{\binom s2}<1, $$ then there is a graph on $n$ vertices with no clique of size $r$ and no independent set of size $s$.

Proof. Set $Z=X_r+Y_s$, the total number of target-sized cliques and independent sets. It is a nonnegative integer, and by linearity of expectation its expectation is the left-hand side of the criterion. If every outcome had $Z\ge1$, then $\mathbb{E}[Z]\ge1$. The strict inequality therefore implies that at least one outcome has $Z=0$. That outcome has neither target-sized set. By the subset observation above, it has no larger clique or independent set either. $\square$

The same reasoning gives a probability estimate. Since $Z\ge1$ whenever $Z\ne0$, we have $\mathbb{P}(Z\ge1)\le\mathbb{E}[Z]$. Consequently, if the sum of the two expectations is at most $c$, then the probability that both obstructions are absent is at least $1-c$. This lower bound is informative when $c<1$.

Choosing the Edge Probability

The clique expectation increases with $p$, while the independent-set expectation decreases with $p$. When the target sizes differ, a useful choice of $p$ must account for both the number of candidate vertex sets and the number of internal edges each set requires. The criterion is exact for any chosen $p$; no asymptotic approximation is needed to apply it.

For equal target sizes $r=s=t$, the two expectations have the same binomial factor and the same exponent. At $p=1/2$, they are equal. This choice also minimizes the larger of the two expectations: if $p\le1/2$, then $(1-p)^{\binom t2}\ge p^{\binom t2}$, so the independent-set expectation is the larger one and decreases as $p$ increases toward $1/2$. If $p\ge1/2$, the clique expectation is the larger one and increases as $p$ moves farther above $1/2$. Thus, for equal targets, testing $p=1/2$ gives the balanced criterion $$ 2\binom nt\,2^{-\binom t2}<1. $$ This is a useful sufficient condition, not a claim that every graph with those parameters has the desired properties.

Worked Example: Equal Targets on Ten Vertices

Take $n=10$, target size $t=5$ for both properties, and $p=1/2$. There are $\binom{10}{5}=252$ candidate five-vertex sets: explicitly, $10\cdot9\cdot8\cdot7\cdot6/(5\cdot4\cdot3\cdot2\cdot1)=252$. Each such set has $\binom52=10$ possible internal edges. Its probability of being a clique is $(1/2)^{10}=1/1024$, and its probability of being independent is also $(1/2)^{10}=1/1024$.

Therefore, $$ \mathbb{E}[X_5]=252/1024=63/256,\qquad \mathbb{E}[Y_5]=252/1024=63/256. $$ The total is $126/256=63/128<1$. The criterion guarantees a graph on ten vertices with no five-vertex clique and no five-vertex independent set. More quantitatively, the probability of having at least one of these obstructions is at most $63/128$, so the probability of having neither is at least $1-63/128=65/128$.

Check: each candidate set requires ten edge decisions, and there are 252 candidate sets of each type. Adding the two expected counts gives $63/256+63/256=126/256=63/128$, the same total used in the criterion.

Asymmetric Targets

If the desired clique and independent-set sizes differ, $p=1/2$ need not balance the expectations. For instance, a larger clique target requires more edges within each candidate set, while a smaller independent-set target requires fewer missing edges. A parameter choice can be assessed by substituting it separately into the two terms. Both terms must be included to conclude that a graph avoids both obstructions.

Worked Example: Suppressing a Four-Clique and a Five-Vertex Independent Set

Take $n=8$, $r=4$, $s=5$, and $p=2/5$. There are $\binom84=70$ four-vertex subsets and $\binom85=56$ five-vertex subsets. A four-vertex set has $\binom42=6$ internal edges, while a five-vertex set has $\binom52=10$.

The expected number of four-cliques is $$ 70(2/5)^6=70\cdot64/15625=4480/15625=2{,}800{,}000/9{,}765{,}625. $$ The expected number of independent five-vertex sets is $$ 56(1-2/5)^{10} =56(3/5)^{10} =56\cdot59049/9{,}765{,}625 =3{,}306{,}744/9{,}765{,}625. $$ Their sum is $6{,}106{,}744/9{,}765{,}625<1$, since $6{,}106{,}744<9{,}765{,}625$. Hence some graph on eight vertices has neither a four-clique nor an independent set of size five. The probability of finding such a graph in $G(8,2/5)$ is at least $1-6{,}106{,}744/9{,}765{,}625=3{,}658{,}881/9{,}765{,}625$.

Check: the clique term uses six required edges and the independent-set term uses ten absent edges. The denominator $9{,}765{,}625$ is $5^{10}$, and $2{,}800{,}000+3{,}306{,}744=6{,}106{,}744$, confirming the combined expectation.

Worked Example: One Obstruction Can Be Small While the Other Is Large

Let $n=6$, and consider target size $3$ for both properties. There are $\binom63=20$ candidate triples, each with $\binom32=3$ internal edges. At $p=1/10$, the expected number of triangles is $$ 20(1/10)^3=20/1000=1/50, $$ while the expected number of independent triples is $$ 20(9/10)^3=20\cdot729/1000=729/50. $$ The first expectation is small, but the second is greater than $1$; this choice alone does not certify the absence of both.

At $p=9/10$, the calculations reverse: the expected number of triangles is $20(9/10)^3=729/50$, and the expected number of independent triples is $20(1/10)^3=1/50$. At the balanced choice $p=1/2$, each expectation is $20(1/2)^3=20/8=5/2$, so their sum is $5$, which also fails the sufficient criterion.

Check: replacing $p=1/10$ by $p=9/10$ interchanges $p^3$ and $(1-p)^3$, so the two expectations exchange values. At $p=1/2$, both probabilities are $1/8$, giving $20/8=5/2$ in each case. An expectation exceeding $1$ does not prove that an obstruction must occur; it only means this first-moment criterion gives no conclusion.

Common Pitfall: Confusing an Expected Count with a Probability

A common error is to treat $\mathbb{E}[X_r]$ as the probability that at least one $r$-clique exists. These quantities are different: $X_r$ counts how many such sets occur, and one graph can contain several of them. For example, in $G(6,1/10)$, the expected number of triangles is $1/50$, but the formula does not assert that the probability of at least one triangle equals $1/50$. The valid conclusion is the upper bound $\mathbb{P}(X_3\ge1)\le1/50$, which follows because $X_3$ is a nonnegative integer.

Another error is to use $p$, rather than $1-p$, for an independent set. A specified set is independent only when all its internal edges are absent, so its probability is $(1-p)^{\binom s2}$. Conversely, the clique term uses $p^{\binom r2}$. Using the same factor for both counts loses the distinction that makes it possible to tune the two expectations against each other.

The method matters because it turns a search through all graphs into a calculation over a random model. It can certify the existence of a graph with prescribed forbidden configurations even when it does not construct that graph explicitly. Its limitation is equally important: failure of the inequality does not show that the desired graph does not exist. It says only that this particular expectation bound is insufficient for the chosen parameters.

Check Your Understanding

Use the expectation formulas and the strict criterion above. In each question, distinguish an expected count from a probability.

In $G(7,1/2)$, compute the expected number of four-cliques. How many internal edges must be present in a specified four-vertex set?
For $G(9,1/3)$, write the expected number of independent sets of size $4$, leaving the binomial coefficient unevaluated.
Explain why an expectation of $3/4$ for the number of target sets implies positive probability of finding a graph with none.
For equal target size $t$, derive the condition at $p=1/2$ that guarantees a graph with neither a $t$-clique nor an independent $t$-set.
If the sum of the two expected counts is $1$, does the stated strict criterion guarantee a graph with neither obstruction? Explain what the criterion does and does not say.