Reading the Erdős–Stone Formula
For a fixed graph \(H\), the extremal number \(\operatorname{ex}(n,H)\) asks how many edges a simple graph on \(n\) vertices can have while containing no copy of \(H\) as a subgraph. The Erdős–Stone theorem gives a striking large-\(n\) answer when \(H\) has chromatic number at least three: the leading edge count depends on the chromatic number, not on the detailed structure of \(H\). Interpreting the formula correctly means keeping track of its normalization, its fixed-\(H\) hypothesis, and the information hidden in its error term.
Here \(H\) is fixed while \(n\) tends to infinity. A graph is \(H\)-free if it contains no subgraph isomorphic to \(H\); the extremal number \(\operatorname{ex}(n,H)\) is the maximum number of edges among all \(H\)-free simple graphs of order \(n\). The chromatic number \(\chi(H)\) is the least number of colors needed to color the vertices of \(H\) so that adjacent vertices receive different colors.
The notation \(o(1)\) denotes a quantity tending to zero as \(n\) tends to infinity, with \(H\) held fixed. Thus the coefficient of \(\binom{n}{2}\) approaches \(1-1/(r-1)\). In the second form, \(o(n^2)\) denotes an error whose ratio to \(n^2\) tends to zero. Neither notation, by itself, specifies an exact error for a particular \(n\).
Why the Two Forms Agree
The two displays use slightly different normalizations. Since \(\binom{n}{2}=(n^2-n)/2\), replacing \(\binom{n}{2}\) with \(n^2/2\) changes the main expression by a term proportional to \(n\), which is smaller than \(n^2\) by a factor tending to zero. More explicitly, put \(c=1-1/(r-1)\), a constant because \(H\) is fixed. If the first form is written as \(\operatorname{ex}(n,H)=(c+\varepsilon_n)\binom{n}{2}\), where \(\varepsilon_n\to0\), then $$ (c+\varepsilon_n)\binom{n}{2} =\frac{c}{2}n^2-\frac{c}{2}n+\frac{\varepsilon_n}{2}(n^2-n). $$ The term \(-cn/2\) is \(o(n^2)\), and the last term is also \(o(n^2)\). This gives the second form.
Proof. Divide the first Erdős–Stone expression by \(\binom{n}{2}\), which is positive for \(n\ge2\). The resulting ratio is \(c+\varepsilon_n\), so it tends to \(c=1-1/(r-1)\). For the second limit, use \(\binom{n}{2}/n^2=(1-1/n)/2\), which tends to \(1/2\). Therefore $$ \frac{\operatorname{ex}(n,H)}{n^2} =(c+\varepsilon_n)\frac{1-1/n}{2} \longrightarrow \frac{c}{2}. $$ This proves both stated limits. \(\square\)
The factor of \(1/2\) matters. A limiting edge density of \(c\), measured relative to all \(\binom{n}{2}\) possible edges, corresponds to a leading term \(c n^2/2\), not \(c n^2\).
What the Error Term Says
Writing \(\operatorname{ex}(n,H)=c n^2/2+o(n^2)\) says that for every fixed \(\epsilon>0\), there is a threshold \(N\), which may depend on \(H\) and \(\epsilon\), such that for every \(n\ge N\), $$ \left|\operatorname{ex}(n,H)-\frac{c}{2}n^2\right|<\epsilon n^2. $$ This is a relative-scale statement: the discrepancy becomes negligible compared with \(n^2\). It does not say that the discrepancy is bounded by a particular constant times \(n\), nor that the displayed main term is an exact finite-\(n\) answer. An \(o(n^2)\) error could still grow with \(n\); the formula only requires that its growth be slower than \(n^2\) in the ratio sense.
Balanced Turán graphs give a useful finite-\(n\) comparison. For an integer \(s\ge1\), the balanced complete \(s\)-partite graph divides \(n\) vertices into \(s\) parts whose sizes differ by at most one, and joins every pair from different parts. If \(H\) has chromatic number \(s+1\), this graph is \(H\)-free: a subgraph of an \(s\)-partite graph can be colored with at most \(s\) colors, while \(H\) requires \(s+1\). Thus its edge count is a lower bound for \(\operatorname{ex}(n,H)\).
Proof. The number of edges is the total number of vertex pairs minus the pairs lying within parts, so \(t_s(n)=(n^2-\sum_{i=1}^s a_i^2)/2\), where \(a_i\) are the part sizes. For the balanced sizes just listed, $$ \sum_{i=1}^s a_i^2=j(q+1)^2+(s-j)q^2=sq^2+2jq+j. $$ Also \(n^2/s=(sq+j)^2/s=sq^2+2jq+j^2/s\). Subtracting gives \(\sum_i a_i^2=n^2/s+j-j^2/s=n^2/s+j(s-j)/s\). Substitution into the edge count yields the formula. The correction is bounded for fixed \(s\), since \(0\le j<s\); for example \(j(s-j)\le s^2/4\). \(\square\)
When \(\chi(H)=s+1\), this construction has leading term \((1-1/s)n^2/2\), exactly the leading term in Erdős–Stone. The construction explains a natural lower bound; the theorem says that no \(H\)-free graph can exceed that leading quadratic scale asymptotically. It does not say that the error for \(\operatorname{ex}(n,H)\) is the same bounded correction as for the construction.
Worked Interpretations
Worked Example: The Five-Cycle
Let \(H=C_5\), defined by \(V(H)=\{1,2,3,4,5\}\) and \(E(H)=\{12,23,34,45,51\}\). Its vertices cannot be colored with two colors: colors must alternate around the cycle, and the final edge would join vertices of the same color. Three colors suffice, so \(\chi(H)=3\).
Set \(r=3\) in Erdős–Stone. The limiting proportion of possible edges is $$ 1-\frac{1}{r-1}=1-\frac12=\frac12. $$ The leading quadratic term is therefore \(\frac12\cdot\frac{n^2}{2}=\frac{n^2}{4}\), and the conclusion is \(\operatorname{ex}(n,C_5)=n^2/4+o(n^2)\).
For \(n=100\), the leading term evaluates to \(100^2/4=10000/4=2500\). The balanced two-part construction has parts of size \(50\) and \(50\), so its edge count is \(50\cdot50=2500\). It contains no \(C_5\), since every cycle in a bipartite graph has even length. Thus \(2500\) is a verified lower bound from this construction, while the asymptotic formula alone does not assert that the exact extremal number at \(n=100\) is \(2500\).
Check: there are \(\binom{100}{2}=100\cdot99/2=4950\) possible edges. The construction's density is \(2500/4950=50/99\), which tends to \(1/2\) as the order grows; this agrees with the formula's density limit.
Worked Example: The Complete Graph \(K_4\)
Take \(H=K_4\), with \(V(H)=\{1,2,3,4\}\) and \(E(H)=\{12,13,14,23,24,34\}\). Every pair of vertices is adjacent, so four distinct colors are needed and sufficient: \(\chi(H)=4\).
Here \(r-1=3\). The limiting proportion of possible edges is \(1-1/3=2/3\), so the coefficient of \(n^2\) is \((2/3)/2=1/3\). Hence \(\operatorname{ex}(n,K_4)=n^2/3+o(n^2)\).
At \(n=100\), the leading term is \(100^2/3=10000/3=3333\frac13\). The balanced three-part construction has part sizes \(34,33,33\). Its number of edges is the total number of pairs minus the within-part pairs: $$ \binom{100}{2}-\binom{34}{2}-2\binom{33}{2} =4950-561-2(528)=4950-1617=3333. $$ It is \(K_4\)-free because its three parts give a proper coloring with three colors.
Check: counting across parts gives \(34\cdot33+34\cdot33+33\cdot33=1122+1122+1089=3333\) edges, agreeing with the independent total-pairs calculation. The construction lies just below the leading term \(3333\frac13\); the theorem says the normalized discrepancy vanishes asymptotically, not that this particular comparison gives the exact value of \(\operatorname{ex}(100,K_4)\).
Worked Example: An Odd Wheel and \(K_4\)
Define \(H\) by \(V(H)=\{h,a,b,c,d,e\}\) and \(E(H)=\{ab,bc,cd,de,ea,ha,hb,hc,hd,he\}\). The vertices \(a,b,c,d,e\) form a 5-cycle, and \(h\) is adjacent to all five. The rim requires at least three colors. Since \(h\) is adjacent to every rim vertex, its color cannot be any color used on the rim, so at least four colors are needed. Four suffice: color \(a,c\) with one color, \(b,d\) with a second, \(e\) with a third, and \(h\) with a fourth. Thus \(\chi(H)=4\).
The formula gives the same leading coefficient as for \(K_4\): \(1-1/(4-1)=2/3\) relative to all possible pairs, or \(1/3\) multiplying \(n^2\). At \(n=60\), the leading term is \(60^2/3=3600/3=1200\), and the total number of possible edges is \(\binom{60}{2}=60\cdot59/2=1770\). The limiting density specified by the theorem is \(2/3\), whose corresponding leading count at this order is \((2/3)\cdot1770=1180\); the difference from \(1200\) is the linear normalization difference between \(\binom{n}{2}\) and \(n^2/2\).
Check: \(1200/60^2=1200/3600=1/3\), while \(1180/1770=2/3\). These are the same leading coefficient expressed relative to \(n^2\) and to the number of possible edges, respectively. Asymptotic equality of coefficients does not guarantee equality of these finite-\(n\) quantities.
A Common Coefficient Mistake
A frequent error is to use \(1-1/\chi(H)\) instead of \(1-1/(\chi(H)-1)\). For \(K_4\), that mistake gives a supposed density of \(1-1/4=3/4\). At \(n=60\), it would predict the leading edge count \((3/4)(60^2/2)=(3/4)(1800)=1350\). The correct density is \(1-1/(4-1)=2/3\), and the corresponding quadratic leading term is \((2/3)(60^2/2)=(2/3)(1800)=1200\). The denominator is the number of parts in the Turán construction, which is one less than the chromatic number of the forbidden graph.
A second mistake is to treat the formula as an exact finite-\(n\) identity. For example, \(n^2/3\) need not even be an integer, as the \(K_4\) calculation at \(n=100\) showed. The formula identifies a leading asymptotic term; lower-order corrections and exact values require more information than this asymptotic statement provides.
Check Your Understanding
Use the fixed-\(H\) Erdős–Stone formula and distinguish density, leading term, and error.
- If a fixed graph \(H\) has \(\chi(H)=5\), what is the limiting proportion of possible edges in an \(H\)-free graph of maximum size, and what is the coefficient of \(n^2\)?
- Explain why \(\operatorname{ex}(n,H)=c\binom{n}{2}+o(n^2)\) implies \(\operatorname{ex}(n,H)=cn^2/2+o(n^2)\).
- For a fixed graph \(H\) with \(\chi(H)=3\), state the asymptotic leading term and explain what the notation \(o(n^2)\) does not specify.
- Why is the balanced complete three-partite graph \(H\)-free whenever \(\chi(H)=4\)?
- For the odd wheel defined above, verify that three colors cannot suffice, and explain why its leading quadratic coefficient matches that of \(K_4\).