Predicting Extremal Density from Chromatic Number

Chromatic Number as a Density Predictor

When a graph is forbidden, the extremal number asks how many edges a graph on $n$ vertices can have while avoiding that forbidden graph. For large $n$, the exact answer may be difficult, but a striking asymptotic theorem gives a first prediction using just one feature of the forbidden graph: its chromatic number. In particular, two fixed forbidden graphs with the same chromatic number, at least three, have extremal numbers with the same leading density, even though their exact extremal numbers need not agree.

Definition: For a fixed finite simple graph $F$, $\operatorname{ex}(n,F)$ is the maximum number of edges in an $n$-vertex simple graph containing no subgraph isomorphic to $F$. Here “subgraph” is not required to be induced: extra edges among the selected vertices do not prevent a copy of $F$.

The chromatic number $\chi(F)$ is the least number of colors in a proper vertex coloring of $F$, meaning that adjacent vertices receive different colors. Throughout the main comparison, $F$ is fixed while $n$ tends to infinity. We compare edge counts with $\binom{n}{2}$, the number of edges in the complete graph on $n$ vertices; thus $\operatorname{ex}(n,F)/\binom{n}{2}$ is the proportion of all possible edges achieved by an extremal $F$-free graph.

The Erdős–Stone Density Prediction

Theorem (Erdős–Stone): Let $F$ be a fixed finite simple graph with $\chi(F)=r+1$, where $r\ge 2$. Then $$ \operatorname{ex}(n,F)=\left(1-\frac{1}{r}+o(1)\right)\binom{n}{2} \qquad\text{as }n\to\infty. $$ Equivalently, $\operatorname{ex}(n,F)/\binom{n}{2}\to 1-1/r$. This is a standard result established in the earlier material on the Erdős–Stone theorem; its proof is not repeated here.

The term $o(1)$ denotes a quantity that tends to zero as $n$ tends to infinity, with $F$ held fixed. It can depend on $F$ and on $n$. The theorem therefore predicts a limiting proportion of all possible edges, not an exact edge count for a particular $n$.

The denominator $r$ is one less than the chromatic number. For example, if $\chi(F)=3$, then $r=2$, and the predicted density among all possible edges is $1/2$. In edge-count form this is $$ \operatorname{ex}(n,F)=\frac{n^2}{4}+o(n^2), $$ because $\binom{n}{2}=n^2/2+O(n)$. The leading term is quadratic: the remaining term, divided by $n^2$, tends to zero.

Corollary: If $F_1,F_2$ are fixed graphs with the same chromatic number $q\ge 3$, then $$ \operatorname{ex}(n,F_1)-\operatorname{ex}(n,F_2)=o(n^2). $$ In particular, their normalized extremal densities have the same limit, $1-1/(q-1)$.

Proof. Set $r=q-1$, which is at least $2$. By the Erdős–Stone theorem, there are quantities $\varepsilon_1(n)$ and $\varepsilon_2(n)$, each tending to zero, such that $\operatorname{ex}(n,F_i)=(1-1/r+\varepsilon_i(n))\binom{n}{2}$ for $i=1,2$. Subtracting gives $\operatorname{ex}(n,F_1)-\operatorname{ex}(n,F_2)=(\varepsilon_1(n)-\varepsilon_2(n))\binom{n}{2}$. Since both $\varepsilon_i(n)$ tend to zero, their difference tends to zero; since $\binom{n}{2}\le n^2/2$, the difference of extremal numbers is $o(n^2)$. Dividing each expression by $\binom{n}{2}$ gives the same limiting density. $\square$

This says the two edge counts differ by less than a fixed positive multiple of $n^2$ for sufficiently large $n$. It does not say the difference is zero, bounded, or even of a particular smaller order such as $O(n)$. The theorem identifies the leading quadratic scale; more detailed estimates require information beyond the chromatic number.

Why Balanced Multipartite Graphs Give the Leading Scale

For $r\ge 1$, the balanced complete $r$-partite graph $T_r(n)$ divides its vertices into $r$ parts as equally as possible and joins every pair in different parts, with no edges within a part. If $n=qr+s$, where $0\le s<r$, its part sizes are $q+1$ for $s$ parts and $q$ for the other $r-s$ parts. Its edge count is $$ t_r(n)=\frac{1}{2}\left(n^2-\big((r-s)q^2+s(q+1)^2\big)\right) =\left(1-\frac{1}{r}\right)\frac{n^2}{2}-\frac{s(r-s)}{2r}. $$ Thus $t_r(n)=(1-1/r)\binom{n}{2}+O(n)$, so these graphs have the density appearing in Erdős–Stone.

If $\chi(F)=r+1$, then $T_r(n)$ contains no copy of $F$. Indeed, every subgraph of $T_r(n)$ can be colored using the $r$ parts, whereas a copy of $F$ would require $r+1$ colors. So $t_r(n)\le\operatorname{ex}(n,F)$. This explains the lower-bound construction and its density. Erdős–Stone supplies the matching leading upper bound; the construction alone would not establish the theorem.

Worked Example: Triangle and Five-Cycle Forbidden Graphs

Let $F_1$ be the triangle, with vertex set $\{a,b,c\}$ and edge set $\{ab,bc,ca\}$. Let $F_2$ be the five-cycle, with vertex set $\{1,2,3,4,5\}$ and edge set $\{12,23,34,45,51\}$. Both have chromatic number $3$: the triangle requires three colors, and the five-cycle can be colored with three but not two colors.

For each, Erdős–Stone uses $r=3-1=2$. Therefore $\operatorname{ex}(n,F_1)=(1/2+o(1))\binom{n}{2}$ and $\operatorname{ex}(n,F_2)=(1/2+o(1))\binom{n}{2}$. For $n=100$, $\binom{100}{2}=100\cdot99/2=4950$, so the shared leading-density benchmark is $(1/2)\cdot4950=2475$ edges. This is a benchmark from the leading term, not an exact prediction at $n=100$.

The balanced bipartite graph with parts $X=\{1,\ldots,50\}$ and $Y=\{51,\ldots,100\}$, and edge set consisting of every pair $xy$ with $x\in X$ and $y\in Y$, has $50\cdot50=2500$ edges. It is triangle-free and has no odd cycle, so it avoids both $F_1$ and $F_2$. Independently, every vertex has degree $50$, giving total degree $100\cdot50=5000$, hence $5000/2=2500$ edges. This illustrates why the actual extremal count can sit above the leading benchmark at a finite value of $n$.

Check: Mantel’s theorem gives $\operatorname{ex}(100,F_1)=\lfloor100^2/4\rfloor=2500$. For $F_2$, the construction gives $\operatorname{ex}(100,F_2)\ge2500$, while Erdős–Stone gives its asymptotic density, not its exact value at $100$. The common limit is $1/2$; these calculations do not establish that the two extremal numbers agree at every $n$.

Worked Example: A Clique and a Larger Four-Chromatic Forbidden Graph

Let $F_1=K_4$, with vertex set $\{1,2,3,4\}$ and all six possible edges. Let $F_2$ be the complete four-partite graph with parts $\{a\},\{b\},\{c\},\{d,e\}$, with all edges between different parts and no edge $de$. It has five vertices and nine edges: the complete graph on five vertices has ten edges, and just the within-part edge $de$ is omitted. Both graphs have chromatic number $4$.

Since $F_2$ contains a $K_4$, formed by choosing $a,b,c$ and either $d$ or $e$, any graph avoiding $F_2$ also avoids $K_4$. Thus $\operatorname{ex}(n,K_4)\le\operatorname{ex}(n,F_2)$. But the Erdős–Stone theorem gives the same limiting density for both: $1-1/(4-1)=2/3$. The containment gives an ordering of their extremal numbers; the common leading density does not say the two numbers are equal.

For a concrete balanced construction at $n=100$, write $100=3\cdot33+1$. The parts of $T_3(100)$ have sizes $34,33,33$, so the edge count is $(10000-(34^2+33^2+33^2))/2=(10000-(1156+1089+1089))/2=3333$. As a second count, the sum of degrees is $34\cdot66+33\cdot67+33\cdot67=2244+2211+2211=6666$, giving $6666/2=3333$ edges. This is a lower bound for each extremal number, since $T_3(100)$ has no four-chromatic subgraph.

Check: $(2/3)\binom{100}{2}=(2/3)\cdot4950=3300$, while $t_3(100)=3333$. The difference between this construction count and the leading benchmark is $3333-3300=33$. It is compatible with the theorem: the theorem permits lower-order terms and does not give an exact finite-$n$ count.

When the Prediction Applies—and When It Does Not

Worked Example: Different Chromatic Numbers, Different Leading Densities

Compare the five-cycle $F_1$, with the vertex and edge sets specified above, and $F_2=K_4$, with vertex set $\{1,2,3,4\}$ and all six edges. Their chromatic numbers are $3$ and $4$, respectively. Erdős–Stone predicts limiting densities $1-1/(3-1)=1/2$ for $F_1$ and $1-1/(4-1)=2/3$ for $F_2$.

At $n=12$, the balanced bipartite graph $T_2(12)$ has parts of size $6,6$, hence $6\cdot6=36$ edges, and avoids the five-cycle. The balanced tripartite graph $T_3(12)$ has three parts of size $4$, hence $(12^2-3\cdot4^2)/2=(144-48)/2=48$ edges, and avoids $K_4$. Counting by degrees checks the latter value: each vertex has degree $12-4=8$, so $12\cdot8/2=48$ edges.

Check: $\binom{12}{2}=12\cdot11/2=66$. The construction densities are $36/66=6/11$ and $48/66=8/11$, not the limiting densities $1/2$ and $2/3$. The examples are finite lower bounds; the theorem concerns the limits as $n$ grows.

The hypothesis $\chi(F)\ge3$ matters. If $F$ is bipartite, then formally inserting $\chi(F)=2$ into the coefficient gives zero, which does not provide a positive leading-density prediction or resolve the finer scale of $\operatorname{ex}(n,F)$. Bipartite forbidden graphs require different information. Thus the chromatic-number rule is a powerful predictor for fixed non-bipartite forbidden graphs, not a complete description of every extremal problem.

Common Pitfall: Using the Wrong Denominator

A frequent error is to use $1-1/\chi(F)$ instead of $1-1/(\chi(F)-1)$. For a triangle, this incorrect calculation gives $1-1/3=2/3$, suggesting about $(2/3)\binom{n}{2}$ edges. The correction is $r=\chi(F)-1=2$, so the theorem gives $1-1/2=1/2$. This is consistent with Mantel’s exact value $\operatorname{ex}(n,K_3)=\lfloor n^2/4\rfloor$, whose ratio to $\binom{n}{2}$ tends to $1/2$.

A second error is to turn shared leading density into exact equality. The corollary proves only that the difference between two extremal numbers with the same chromatic number is $o(n^2)$. It does not determine that difference. A third is to treat the asymptotic benchmark $(1-1/r)\binom{n}{2}$ as an exact finite-$n$ count: the balanced multipartite construction has a rounding term, and the extremal number can also have lower-order contributions.

The practical lesson is to use chromatic number for a first-order prediction: it identifies the quadratic density scale for non-bipartite forbidden graphs. To distinguish forbidden graphs with the same chromatic number, one must examine more structure than the theorem’s leading term records.

Check Your Understanding

In each question, state the relevant assumptions and distinguish an asymptotic conclusion from an exact finite-$n$ claim.

If $\chi(F)=5$, what limiting value does $\operatorname{ex}(n,F)/\binom{n}{2}$ have?
Suppose $\chi(F_1)=\chi(F_2)=4$. What does Erdős–Stone imply about the difference of their extremal numbers?
If $F_1$ is a subgraph of $F_2$, which inequality holds between $\operatorname{ex}(n,F_1)$ and $\operatorname{ex}(n,F_2)$? Explain why.
Why does $T_r(n)$ avoid every graph with chromatic number $r+1$?
Why does the Erdős–Stone theorem not give a useful positive-density prediction for a bipartite forbidden graph?