= Solution
Because $\chi(H)=3$, every bipartite graph is $H$-free. The balanced complete bipartite graph therefore gives
$$
\liminf_{n\to\infty}\frac{\operatorname{ex}(n,H)}{\binom n2}\ge\frac12.
$$
For the reverse bound, fix $\delta>0$ and suppose that $G$ has more than $(1/2+\delta)\binom n2$ edges. Apply the <Szemerédi regularity lemma> with parameters much smaller than $\delta$. Form the reduced graph whose vertices are the regularity classes and whose edges are the regular pairs of density above a small fixed threshold. Edges inside classes, irregular pairs, and regular pairs below the threshold account for $o_\delta(n^2)$ edges. The remaining edges force the reduced graph to have more than $m^2/4$ edges.
By the <Turan theorem>, the reduced graph contains a triangle. The three corresponding regular pairs all have positive density, and the <graph embedding lemma for regular pairs> embeds every fixed three-colourable graph, in particular $H$, across suitable repeated subclusters of these three classes. Thus every sufficiently large graph of density above $1/2+\delta$ contains $H$. Letting $\delta\downarrow0$ gives
$$
\boxed{\lim_{n\to\infty}\frac{\operatorname{ex}(n,H)}{\binom n2}=\frac12.}
$$
This is the chromatic-number-three case of the <Erdős-Stone theorem>.
Back to article page
