The Erdős–Stone Theorem and Chromatic Number

From Forbidden Graphs to Asymptotic Density

For a fixed forbidden graph \(H\), one can ask how many edges an \(n\)-vertex graph can have without containing \(H\). When \(H\) has chromatic number at least three, the answer has a striking asymptotic form: the leading edge density depends on the chromatic number of \(H\), not on its finer structure. The Erdős–Stone theorem makes this statement precise.

All graphs in this tutorial are finite and simple. A graph \(G\) contains \(H\) as a subgraph if some vertices of \(G\), together with some edges between them, form a graph isomorphic to \(H\). The subgraph need not be induced: extra edges among the chosen vertices do not prevent a copy of \(H\). A graph is \(H\)-free if it contains no such copy.

The limit concerns \(n\) tending to infinity while \(H\) stays fixed. A statement that a ratio equals a constant plus \(o(1)\) means that its difference from that constant tends to zero as \(n\to\infty\). It does not give an exact value for each finite \(n\), nor does it specify a rate of convergence.

The Erdős–Stone Theorem

The theorem is a deep result in extremal graph theory; its proof is beyond the scope of this tutorial. The constructions and deductions below are proved directly. They explain why the density in the theorem has this form, and how to use the conclusion without mistaking it for a finite exact formula.

For the lower-bound construction, write \(q=r-1\). Let \(T_q(n)\) be the complete \(q\)-partite graph whose \(q\) part sizes differ by at most one. A complete multipartite graph has every edge between different parts and no edges within a part. Because \(H\) has chromatic number \(r=q+1\), it cannot be a subgraph of a \(q\)-partite graph: assigning each vertex the part containing it would give a proper coloring of \(H\) with at most \(q\) colors.

Proof. The graph \(T_{r-1}(n)\) is \((r-1)\)-partite, so the coloring argument above shows that it is \(H\)-free. Its edge count is therefore at most the maximum defining \(\operatorname{ex}(n,H)\), proving the inequality. To compute its limiting density, put \(q=r-1\) and write \(n=qa+s\), where \(a\) and \(s\) are integers with \(0\le s<q\). The part sizes are \(s\) copies of \(a+1\) and \(q-s\) copies of \(a\). Their squared sizes sum to \[ s(a+1)^2+(q-s)a^2 =qa^2+2sa+s =\frac{n^2}{q}+\frac{s(q-s)}{q}. \] For a complete multipartite graph with part sizes \(n_1,\ldots,n_q\), every pair of vertices is either an edge between parts or a pair within one part. Thus its number of edges is \(\frac12(n^2-\sum_i n_i^2)\). Consequently, \[ |E(T_q(n))| =\frac12\left(n^2-\frac{n^2}{q}-\frac{s(q-s)}q\right). \] Here \(q\) is fixed and \(0\le s<q\), so \(s(q-s)/q\) is bounded independently of \(n\). Dividing by \(\binom n2=n(n-1)/2\) and letting \(n\) tend to infinity gives the limit \(1-1/q=1-1/(r-1)\). \(\square\)

This proposition proves that the proposed density is attainable asymptotically by \(H\)-free graphs. The Erdős–Stone theorem supplies the difficult complementary fact: no \(H\)-free graphs have a larger limiting density.

Worked Applications

What the Theorem Says—and Does Not Say

The theorem identifies the leading term of \(\operatorname{ex}(n,H)\) on the scale of all possible edges. Equivalently, for fixed \(H\) with \(\chi(H)=r\ge3\), \[ \operatorname{ex}(n,H) = \left(1-\frac{1}{r-1}+o(1)\right)\binom n2. \] The term tending to zero may depend on \(H\). The statement does not specify that term, determine the exact extremal graph for a given \(n\), or give an exact value of \(\operatorname{ex}(n,H)\) for small \(n\). Those are separate finite questions.

Proof. Any \(F\)-free graph is \(H\)-free: if it contained \(H\), the copy of \(F\) inside \(H\) would also occur in the graph. Thus every \(F\)-free graph on \(n\) vertices has at most \(\operatorname{ex}(n,H)\) edges, proving the inequality. By the Erdős–Stone theorem applied to each fixed graph, both extremal numbers divided by \(\binom n2\) tend to \(1-1/(r-1)\). Subtracting these two convergent ratios gives \[ \frac{\operatorname{ex}(n,H)-\operatorname{ex}(n,F)}{\binom n2}\longrightarrow 0. \] Since \(\binom n2/n^2=(n-1)/(2n)\) tends to \(1/2\), the difference divided by \(n^2\) also tends to zero. \(\square\)

This comparison shows one precise sense in which chromatic number controls the asymptotic answer: for forbidden graphs with the same chromatic number, their extremal numbers differ by a quantity negligible compared with \(n^2\). It does not say their finite extremal numbers are equal.

A Common Denominator Error

A frequent mistake is to replace the theorem’s denominator \(\chi(H)-1\) by \(\chi(H)\). For \(C_5\), that incorrect calculation gives \(1-1/3=2/3\). The correct calculation uses \(\chi(C_5)=3\), so the denominator is \(3-1=2\), and the density is \(1-1/2=1/2\). The multipartite construction confirms the denominator: a graph with \(r-1\) parts avoids every \(r\)-chromatic graph, and its density tends to \(1-1/(r-1)\).

Another error is to interpret an asymptotic formula as an exact finite answer. For example, \(T_3(12)\) has density \(48/66=8/11\), while the limiting density for a 4-chromatic forbidden graph is \(2/3\). These numbers need not match at \(n=12\); the theorem concerns the limit as \(n\to\infty\).