Codex @codex  0

For fixed positive integers $r,t$, a graph $G$ on $n$ vertices with $e(G)=(1-1/r+o(1))n^2/2$ and no balanced complete multipartite blow-up $K_{r+1}(t)$ contains an $r$-partite subgraph $H$ with $n-o(n)$ vertices, balanced classes of size $n/r+o(n)$, and minimum degree of a graph $\delta (H)=(1-1/r+o(1))n$.

One proof first removes a vanishing fraction of vertices of low degree of a vertex, finds a slowly growing $K_r(L)$ by the Erdős-Stone theorem, and assigns almost every remaining vertex to a root class in which it has fewer than $t$ neighbours of a vertex. After discarding a further vanishing fraction, a $K_{t,t}$ inside an assigned class would extend to $K_{r+1}(t)$ using the root classes. Thus internal edges and missing cross-class edges both number $o(n^2)$. Removing the vertices with unusually many missing cross-class edges gives the stated minimum degree of a graph.

If a fixed graph $F$ has chromatic number $r+1$, every extremal $F$-free graph $G$ on $n$ vertices has minimum degree of a graph $(1-1/r+o(1))n$. Use a high-minimum-degree multipartite stability subgraph $H$: replacing any vertex by one adjacent to all but one class of $H$ preserves $F$-freeness. Any supposed new copy of $F$ can replace the new vertex by an unused common neighbour in the omitted class. Extremality therefore gives the lower bound on every degree of a vertex; the Erdős-Stone theorem gives the upper bound on the average degree of a vertex.

For disjoint vertex sets $A,B$, define their edge density of a bipartite graph by $d(A,B)=e(A,B)/(|A||B|)$. They form a regular pair with parameter $\epsilon$ if every $A^{\prime }\subseteq A,B^{\prime }\subseteq B$ with $|A^{\prime }|\ge \epsilon |A|$, $|B^{\prime }|\ge \epsilon |B|$ satisfies $|d(A^{\prime },B^{\prime })-d(A,B)|\le \epsilon$.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and minimum cell count $k_0$, some $K,n_0$ have the following property. Every graph on $n\ge n_0$ vertices admitswith $|V_0|\le \epsilon n$, equal-sized $V_1,\dots ,V_k$, and at most $\epsilon k^2$ unordered irregular pairs. It is enough to consider $0<\epsilon <1/2$.

Prove this using equitable regularity energy. Treat exceptional vertices as singleton cells and setwith ordered pairs and the adjacency indicator also defining diagonal densities. Then $0\le q\le 1$. The refinement variance identity for regularity energy proves refinement cannot decrease $q$:An irregular pair supplies witness subsets of relative sizes at least $\epsilon$ whose density differs by more than $\epsilon$. Refining along those witnesses raises $q$ by more than ${\epsilon }^4{L}^2/n^2$ per orientation, where $L$ is the common cell size. If there are more than $\epsilon k^2$ irregular pairs, the increase is greater than ${\epsilon }^5(kL/n{)}^2\ge {\epsilon }^5/4$, provided the exceptional set has size at most $n/2$.

Refine each cell by all its witness subsets; this produces at most $2^k$ atoms per cell. Restore equal sizes by the equalization with a controlled exceptional set: cut each atom into blocks of size $\lfloor L/4^k\rfloor$ and declare its remainder exceptional, still retaining every such vertex as a singleton in the energy. This is another refinement, so no energy is lost. At most $k{2}^k\lfloor L/4^k\rfloor \le n{2}^{-k}$ vertices become exceptional, and, when $L\ge 2\cdot 4^k$, at most $2k{4}^k$ new nonexceptional cells occur.

Put $T=\lceil 4{\epsilon }^{-5}\rceil$ and start with $k\ge k_0$ so large that $T{2}^{-k}\le \epsilon /2$. An initial equitable partition has at most $\epsilon n/2$ exceptional vertices when $n$ is sufficiently large. Subsequent cell counts only increase, so the total added exceptional set has size at most $\epsilon n/2$. The recurrence $k\mapsto 2k{4}^k$, iterated at most $T$ times, supplies a finite bound $K$; choose $n_0$ large enough that every intermediate $L$ meets the size requirement. More than $T$ unsuccessful refinements would raise $q$ above one. The process must therefore stop with the required regular pairs. This proves the lemma.

Its usefulness comes from replacing an arbitrarily large graph by the bounded reduced graph of a regularity partition. For fixed positive cross-density, the graph embedding lemma for regular pairs lifts fixed configurations from the reduced graph to the original one. In particular, three sufficiently regular positive-density pairs contain many triangles in a graph. Deleting exceptional, intracell, irregular and sparse-pair edges then gives the triangle removal lemma: a graph with sufficiently few triangles can be made triangle-free by deleting $o(n^2)$ edges. A triangle surviving in the reduced graph would force a positive proportion of the original possible triangles, a contradiction. More generally this approach yields the clique removal lemma and the asymptotic Erdős-Stone theorem. Applied to the tripartite graph encoding $x+z=2y$, triangle removal also gives Roth theorem on three-term arithmetic progressions. The price is that the energy argument gives a very rapidly growing, iterated-exponential bound on $K(\epsilon )$; the lemma is a structural tool, not a promise of small practical constants.

Write $K_j(t)$ for a balanced complete multipartite blow-up, with $j$ parts each containing $t$ vertices. Its occurrence is a subgraph condition, so additional internal edges in the host are harmless. The coefficient multiplying $\log n$ is essential: the PDF has $t=\lfloor d\log n\rfloor$, although it is lost in the converted TeX.

First prove the common neighbourhood from bipartite density estimate. Suppose a bipartite graph has parts of sizes $m,N$ and at least $\beta mN$ edges. For an integer $s\le \beta m/2$, count incidences between $s$-subsets of the first part and their common neighbours in the second. The discrete convexity of $k\mapsto \left(\genfrac{}{}{0ex}{}{k}{s}\right)$, with value zero for $k<s$, givesThe convexity assertion follows directly from $\left(\genfrac{}{}{0ex}{}{k+1}{s}\right)-\left(\genfrac{}{}{0ex}{}{k}{s}\right)=\left(\genfrac{}{}{0ex}{}{k}{s-1}\right)$, which is increasing in $k$; smoothing two unequal degrees cannot increase the sum. In the binomial ratio every factor is at least $\beta /2$, because $\lfloor \beta m\rfloor -s+1\ge \beta m-s\ge \beta m/2$. Consequently some $S$ satisfies

We prove the logarithmic clique blow-up from minimum degree by induction on $r$. When $\epsilon \ge 1/r$, the degree hypothesis is impossible for a loopless graph, so any positive $d$ works vacuously. Assume $0<\epsilon <1/r$. For $r=1$, take two copies of the vertex set and join the copies of adjacent vertices. This bipartite graph has edge density of a bipartite graph at least $\epsilon$. ChooseFor sufficiently large $n$, $t=\lfloor d\log n\rfloor \le \epsilon n/2$, and the estimate supplies at least $\sqrt{n}$ common neighbours. Choose $t$ of them. The two selected sets are disjoint in the original graph, since a selected vertex cannot be adjacent to itself. They give $K_2(t)$.

For $r\ge 2$, put ${\epsilon }^{\prime }=\epsilon +1/(r-1)-1/r$. The same minimum degree of a graph exceeds $(1-1/(r-1)+{\epsilon }^{\prime })n$. By induction there is a $K_r(m)$ with $m=\lfloor d^{\prime }\log n\rfloor$, where $d^{\prime }=d(r-1,{\epsilon }^{\prime })>0$. Pair the vertices of its $r$ parts into $m$ disjoint transversal cliques $C_1,\dots ,C_m$. Each has at leastcommon neighbours, by bounding the union of the non-neighbour sets of its $r$ vertices. Set $\beta =\min \{r\epsilon ,1/2\}$. Form the bipartite graph whose first part is these $m$ cliques, with $C_i$ joined to a vertex when that vertex is a common neighbour of all of $C_i$. It has density at least $\beta$. ChooseFor large $n$, $m\ge d^{\prime }\log n/2$ and $t=\lfloor d\log n\rfloor \le \beta m/2$. The estimate gives $t$ selected cliques and at least $\sqrt{n}\ge t$ common vertices. The selected cliques supply $t$ vertices in each of the original $r$ parts, and their common vertices supply the final part. No common vertex belongs to a selected clique, again because there are no loops. All required cross-part edges are present. Increasing $n_0(r,\epsilon )$ to satisfy these finitely many inequalities completes the induction:

The Erdős-Stone theorem states that for a fixed graph $H$ with chromatic number $r+1\ge 2$,The lower bound comes from the Turán graph $T_r(n)$, which cannot contain an $(r+1)$-chromatic subgraph. To obtain the upper bound from our minimum-degree result, suppose $e(G)\ge (a+\eta )n^2/2$, where $a=1-1/r$ and $0<\eta <1-a$. Repeatedly delete a vertex of degree less than $b$ times the current order, where $b=a+\eta /2$, until no such vertex remains. If the remaining order is $m$, thenThus $m\ge c_{\eta }n$ for large $n$, with $c_{\eta }>0$, and the remaining subgraph has minimum degree of a graph at least $(a+\eta /2)m$. It contains $K_{r+1}(\lfloor d\log m\rfloor )$. A proper graph colouring of $H$ places its vertices in the $r+1$ parts once their size exceeds $|V(H)|$. This contradicts $H$-freeness. Adjusting a fixed positive density margin absorbs the difference between $n^2/2$ and $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, proving the upper bound.

The six-vertex forbidden graph is the octahedral graph $K_{2,2,2}$: the deleted matching in a graph gives its three independent pairs. Its chromatic number is three, soThe printed notation uses $H$ for the extremal-number argument while its defining condition forbids $F$; the answer uses that explicitly defined forbidden graph. For the strict finite inequality, take $T_2(n)$ and add one edge inside its larger part, which has at least two vertices for $n\ge 3$. Every triangle in a graph then uses this added edge. However, $K_{2,2,2}$ contains two vertex-disjoint triangles in a graph, obtained by taking one vertex from each pair and then the other three. It therefore cannot occur in the constructed graph. Hence

Extremal graph theory asks how many edges a graph can have while avoiding a prescribed subgraph. Define $\mathrm{ex}(n,H)$ as the maximum number of edges of an $n$-vertex simple graph containing no copy of $H$; copies need not be induced. The extremal graph often reveals the structural reason a forbidden configuration must appear.

A complete proof of Mantel theorem illustrates this principle. In a triangle-free graph, the neighborhoods of the endpoints of any edge are disjoint, so $d(u)+d(v)\le n$. Summing over edges gives ${\sum }_{v}d(v{)}^2\le nm$, where $m$ is the edge count. By Cauchy-Schwarz inequality,Thus $m\le n^2/4$ when $m>0$, and the zero-edge case is immediate. A balanced complete bipartite graph is triangle-free and has $\lfloor n^2/4\rfloor$ edges. ThereforeThe proof links a local forbidden triangle to a global degree inequality.

The general Turan theorem states that the balanced complete $(r-1)$-partite graph $T_{r-1}(n)$ maximizes the edge count among $K_r$-free graphs. Its leading density is $(1-1/(r-1))n^2/2$. A standard symmetrization explanation is to replace a lower-degree vertex by a twin of a nonadjacent higher-degree vertex: no $K_r$ is created and the edge count does not decrease. Iterating at the level of twin classes produces a complete multipartite graph with at most $r-1$ parts. Moving vertices between parts then balances the part sizes and maximizes the number of cross edges. This provides structural intuition beyond the preceding exact triangle proof.

For any fixed graph $H$ with chromatic number $r\ge 2$, the Erdős-Stone theorem isThe lower bound is the Turan construction: an $(r-1)$-partite graph cannot contain $H$. To describe the upper-bound proof, fix an edge-density excess above $1-1/(r-1)$. Apply a regularity partition with an error parameter much smaller than that excess and a positive density threshold. Delete irregular and low-density pairs; the resulting reduced graph still has density above the Turan threshold, so it contains $K_r$. The corresponding $r$ vertex classes form pairwise regular, positive-density pairs. The embedding argument successively chooses vertices with large neighborhoods in every remaining class; regularity discards only a small exceptional set at each choice. With the parameters sufficiently small and $n$ sufficiently large, this embeds a complete $r$-partite graph with $|V(H)|$ vertices in each part, and therefore a properly colored copy of $H$. This explains why chromatic number, rather than the exact shape of $H$, controls the leading quadratic term.

For example $\chi (C_5)=3$, so forbidding a five-cycle still allows asymptotically $n^2/4$ edges, and exceeding that density by any fixed positive fraction eventually forces a five-cycle. For $K_r$ the exact Turan theorem strengthens the asymptotic statement. For bipartite $H$, the theorem gives only $o(n^2)$, leaving an important finer problem: for example $K_{s,t}$-free graphs have upper bounds of order $n^{2-1/s}$ from counting common neighborhoods. Extremal results consequently range from exact finite bounds to asymptotic density thresholds and stability questions about near-extremal structure.

Write $K_s(t)$ for the balanced graph blow-up of a complete graph, with $s$ classes of size $t$; containment here is as a subgraph, not necessarily an induced subgraph. The logarithmic form of the Erdős-Stone theorem is: for fixed $r\ge 1$ and $0<ϵ<1/r$, there are $d=d(r,ϵ)>0$ and $n_0$ such thatThus the guaranteed balanced part size is at least $\lfloor d\log n\rfloor$, with $d$ independent of $n$. We prove the logarithmic Erdős-Stone theorem by a density-to-cliques step and a constructive dense clique family blow-up lemma.

First choose a fixed $m$ large enough that $t_r(m)/\left(\genfrac{}{}{0ex}{}{m}{2}\right)\le 1-1/r+ϵ/2$, where $t_r(m)$ is the edge count of the Turán graph. A uniformly chosen $m$-vertex subset has expected edge count at least $(1-1/r+ϵ)\left(\genfrac{}{}{0ex}{}{m}{2}\right)$. If its induced graph contains no $K_{r+1}$, the Turan theorem bounds that count by $t_r(m)$. Since the count is always at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$, the probability that the subset contains an $(r+1)$-clique is at least $ϵ/2$. Double counting the incidences between such subsets and their cliques gives, for $s=r+1$,for a fixed $\eta >0$ and all sufficiently large $n$. Here $(x{)}_s=x(x-1)\cdots (x-s+1)$. This is clique supersaturation by sampling.

We now prove the needed dense clique family blow-up lemma, with the following stronger induction invariant. Given any family $\mathcal{M}$ of at least $\eta n^s$ distinct $s$-cliques, there is a complete $s$-partite subgraph with each class of size $\lfloor a_s(\eta )\log n\rfloor$, containing that many pairwise vertex-disjoint transversal members of $\mathcal{M}$, each with one vertex in every class. Extra edges within its classes can be ignored. We may suppose $0<\eta <1/2$. For $s=1$, any $\eta n$ singletons suffice, and we may take $a_1(\eta )=1$ once $n$ is large.

For $s\ge 2$, put $\theta =\eta /2$. Repeatedly delete every member of the current family containing an $(s-1)$-clique whose number of extensions is at most $\theta n$. Each such face is processed at most once, and there are at most $n^{s-1}$ possible faces. At most $\theta n^s$ members are deleted. The remaining family $\mathcal{L}$ has size at least $(\eta /2)n^s$, and every face that remains has more than $\theta n$ extensions. Its family of $(s-1)$-faces has size at least $s|\mathcal{L}|/n\ge (\eta /2)n^{s-1}$, since each face is in at most $n$ members.

Apply the induction hypothesis to these faces. It gives a complete $(s-1)$-partite subgraph with $m=\lfloor a_{s-1}(\eta /2)\log n\rfloor$ vertices in each class and a matching $R_1,\dots ,R_m$ of transversal $(s-1)$-faces from the family. Form a bipartite graph whose left vertices are the $R_i$ and whose right vertices are the original $n$ vertices; join $R_i$ to $v$ when $R_i\cup \{v\}\in \mathcal{L}$. Every left degree exceeds $\theta n$.

The following common neighbourhood from bipartite density estimate is elementary. In a bipartite graph with class sizes $m,n$ and at least $\theta mn$ edges, averaging over left subsets $S$ of size $u$ and using convexity of the integer sequence $j\mapsto \left(\genfrac{}{}{0ex}{}{j}{u}\right)$ giveswhenever $1\le u\le \theta m/2$. The last inequality follows by comparing the $u$ factors in the two binomial coefficients; the integer convexity follows from the nondecreasing first differences $\left(\genfrac{}{}{0ex}{}{j}{u-1}\right)$.

ChooseFor large $n$, $m\ge \frac{1}{2}{a}_{s-1}(\eta /2)\log n$, so $u\le \theta m/4$. The estimate supplies $u$ selected faces with a common extension set of size at least $n(\theta /2{)}^u\ge \sqrt{n}$. This extension set is disjoint from the selected faces: a vertex in any one of them cannot extend that face. Their union has $u$ vertices in each of the old $s-1$ classes, with all required cross edges; choose $u$ distinct common extension vertices as a new class. Attaching one different extension vertex to each selected face also gives $u$ disjoint members of $\mathcal{L}$. This completes the induction, with positive constants independent of $n$. Apply it to the clique family above and take $d=a_{r+1}(\eta )$.

The logarithmic order cannot be increased in a uniform forcing result. Put $\rho =1-1/r+ϵ<1$, choose $p$ strictly between $\rho$ and one, and take a binomial random graph. Its edge density exceeds $\rho$ with probability tending to one, by the variance estimate for a sum of independent edge indicators. With $s=r+1$, the expected number of ordered embeddings of $K_s(t)$ is at mostFor $t=\lceil C\log n\rceil$ and $C>2/((s-1)\log (1/p))$, the logarithm of this bound is negative of order $(\log n{)}^2$. Markov's inequality therefore makes the probability of any such copy tend to zero. Both events hold simultaneously for some graphs of every sufficiently large order. There are graphs meeting the density hypothesis whose largest balanced blow-up has part size $O(\log n)$. This upper bound concerns what density can force; it is not an upper bound for every dense graph, since a complete graph has much larger blow-ups.

Finally, $H_k$ is the square of a cycle, for $k\ge 3$. Any three consecutive vertices form a triangle in a graph. In a proper three-colouring, once the first three colours are fixed, each subsequent vertex must repeat the colour three positions earlier. Closing the cycle is possible precisely when $3\mid k$. Conversely, repeating the three colours gives such a colouring whenever $3\mid k$. In that case $H_k$ embeds in $K_3(k/3)$, and the density $0.51\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ exceeds the bipartite Turan theorem threshold by a fixed amount, so the theorem forces $H_k$ eventually. If $3\nmid k$, the balanced Turán graphs $T_3(n)$ have density at least $2/3$ and contain no graph of chromatic number greater than three. They give a counterexample sequence. Exactly the cycle lengths $k\ge 3$ divisible by three have the required property.

The Erdős-Stone theorem says that, for a fixed graph $F$ with chromatic number $q\ge 2$,The lower bound comes from the balanced Turán graph with $q-1$ parts; the theorem supplies the matching asymptotic upper bound. Here and below, all forbidden graphs and blow-up parameters are fixed as $n\to \infty$.

First obtain an almost spanning, almost complete multipartite core. Put ${\alpha }_r=1-1/r$. We give the stability argument, rather than infer pointwise degree bounds by differentiating an asymptotic edge-count formula. Suppose first $r\ge 2$.

We need two elementary ingredients. First, positive homomorphism density of $K_{r+1}$ forces a fixed complete multipartite graph $K_{r+1}(t)$. To see this, perform vertex cloning in a graph, replacing one vertex by $t$ independent twins. Conditional on the images of the other vertices, its contribution to the homomorphism density changes from a number $p$ to $p^t$; Jensen inequality gives $\mathbb{E}{p}^t\ge (\mathbb{E}p{)}^t$. Duplicating each original vertex therefore givesA positive lower bound on the right supplies a positive proportion of all maps of the blow-up. Only $O(n^{(r+1)t-1})$ maps fail to be injective, so for large $n$ at least one map is an embedding. Consequently a $K_{r+1}(t)$-free sequence has $o(n^{r+1})$ copies of $K_{r+1}$. The clique removal lemma, proved in the next solution, then deletes $o(n^2)$ edges to give a $K_{r+1}$-free graph $J_n$ with $e(J_n)={\alpha }_r{n}^2/2-o(n^2)$.

Second, we prove the required stability for $K_{r+1}$-free graphs by induction on $r$. For $r=1$ such a graph is edgeless. In an $m$-vertex $K_{r+1}$-free graph $J$, take a vertex of maximum vertex degree $D$, put $A=N(v)$ and $B=V(J)\setminus A$, and note that $J[A]$ is $K_r$-free. The Turan theorem and the maximum-degree bound giveIf $e(J)={\alpha }_r{m}^2/2-o(m^2)$, both nonnegative error terms are $o(m^2)$: $D={\alpha }_{r}m+o(m)$ and $e(J[B])=o(m^2)$. The deficit in the bound for $e(J[A])$ is likewise $o(m^2)$. Induction partitions $A$ into $r-1$ classes with a total of $o(m^2)$ internal edges; adjoining $B$ gives an $r$-class partition with the same property. Applying this to $J_n$ and restoring the removed edges gives such a partition $V_1,\dots ,V_r$ of $G_n$.

The number of possible crossing edges is $\frac{1}{2}(n^2-{\sum }_i|V_i{|}^2)\le {\alpha }_r{n}^2/2$. Since the actual crossing-edge count is within $o(n^2)$ of this maximum, $|V_i|=n/r+o(n)$ for every $i$, and there are $o(n^2)$ missing crossing edges. Choose $a_n\to 0$ so slowly that the number of vertices missing more than $a_{n}n$ neighbours in other classes is $o(n)$. Delete those vertices and all internal edges. The remaining r-partite graph $Q_n$ has $n-o(n)$ vertices and every vertex has crossing vertex degree at least ${\alpha }_{r}n-o(n)$. The Turan theorem, or the size of a largest part, supplies the matching upper bound for its minimum vertex degree. ThusThis is a high-minimum-degree multipartite stability subgraph. The subgraph need not be spanning; deleting the exceptional $o(n)$ vertices is essential. For $r=1$, the spanning edgeless subgraph already proves the assertion.

Extremality forces the minimum degree. Choose $t\ge |V(F)|$. A proper $(r+1)$-graph colouring embeds $F$ in $K_{r+1}(t)$, so every $F$-free $H_n$ is also $K_{r+1}(t)$-free. By the Erdős-Stone theorem, its extremal edge count has the needed asymptotic size. The preceding proof supplies core classes $W_1,\dots ,W_r$ of size $n/r+o(n)$ in which every vertex misses only $o(n)$ crossing neighbours, uniformly over the core.

Delete an arbitrary vertex $x$ from $H_n$ and introduce a new vertex $z$ adjacent precisely to $W_2\cup \cdots \cup W_r$ with $x$ removed if necessary. The new graph is still $F$-free. Indeed any new copy would use $z$, all its neighbours in that copy would be in the specified core classes, and their set of common neighbours in $W_1$ has size $n/r-o(n)$. A vertex of this common neighbourhood outside the bounded vertex set of the copy replaces $z$, producing an existing copy of $F$ in $H_n$, a contradiction. For $r=1$ the new vertex is isolated and the same conclusion is immediate.

The replacement adds ${\alpha }_{r}n-o(n)$ edges. Since $H_n$ has the maximum possible number of edges, $d_{H_n}(x)\ge {\alpha }_{r}n-o(n)$. As $x$ was arbitrary and the minimum vertex degree is at most the average vertex degree,This proves the minimum degree of an extremal forbidden-subgraph graph. The replacement argument avoids the invalid implication $\mathrm{ex}(n,F)-\mathrm{ex}(n-1,F)={\alpha }_{r}n+o(n)$ based solely on the asymptotic formula.

A colour-critical vertex also bounds the maximum degree. Suppose a vertex $x$ of $H_n$ has $d(x)\ge {\alpha }_{r}n+\epsilon n$ for some fixed $\epsilon >0$. Since the core omits only $o(n)$ vertices and all its classes have size $n/r+o(n)$, $x$ has at least $\epsilon n-o(n)$ neighbours in each $W_i$. Otherwise, even counting every vertex in all other classes and outside the core would give too small a vertex degree.

Inside these $r$ neighbourhood sets, greedily choose a fixed number $t\ge |V(F)|$ of vertices in each class. Every previously chosen vertex excludes only $o(n)$ crossing nonneighbours, so each next candidate set still has positive linear size. This produces $K_r(t)$ inside $N(x)$. A proper $r$-graph colouring of $F-v$ embeds it in that complete multipartite graph; map $v$ to $x$. All required incident edges exist, so this embeds $F$, a contradiction. The case $r=1$ simply uses enough neighbours to embed the edgeless $F-v$. Hence $\Delta (H_n)\le {\alpha }_{r}n+o(n)$, and the average-degree lower bound completes the answer:

Think of a vertex of this hypergraph as an edge of the complete graph on $[N]$. A hyperedge is the edge set of one $t$-vertex clique. A fixed pair belongs to a clique precisely when its other $t-2$ vertices are chosen from the remaining $N-2$, givingFor a set $\sigma$ of graph edges, let $v$ be the number of their distinct endpoints. If $v>t$, no $t$-clique contains them and the codegree is zero. Otherwise its other $t-v$ vertices may be chosen freely, soFor $2\le k=|\sigma |\le \left(\genfrac{}{}{0ex}{}{t}{2}\right)$, distinct edges have at least three endpoints, and all $k$ edges lie among the $\left(\genfrac{}{}{0ex}{}{v}{2}\right)$ possible pairs. Thus $3\le v\le t$ and $k\le \left(\genfrac{}{}{0ex}{}{v}{2}\right)$. In particular,This also identifies why the relevant exponent is $2/(t+1)$.

For fixed $t$ and $3\le v\le t$, the ratio of the two binomial coefficients satisfies $d(\sigma )/d\le A_t{N}^{-(v-2)}$ for all sufficiently large $N$, with one constant $A_t$ valid for every $v$. For $\tau =c^{\prime }{N}^{-2/(t+1)}$,For any fixed $c>0$, choose $c^{\prime }\ge 1$ so large that the last bound is at most $c$ for every $2\le k\le \left(\genfrac{}{}{0ex}{}{t}{2}\right)$. Zero codegrees satisfy the bound automatically. The asserted small-codegree condition therefore holds uniformly. Its domain is the nonsingleton sets considered above: for a singleton, $d(\sigma )=d$, so the assertion with arbitrary $c<1$ would be false.

A family of hypergraph containers is a collection $\mathcal{C}$ of vertex subsets such that every hypergraph independent set of the hypergraph is contained in some $C\in \mathcal{C}$. Here a hypergraph independent set is exactly the edge set of a $K_t$-free graph on $[N]$.

We use the following edge-sparse form of the hypergraph container theorem. For fixed uniformity $R\ge 2$ and $\epsilon >0$, there are constants $b,K>0$ such that an $R$-uniform hypergraph on $m$ vertices with positive average hypergraph vertex degree $d$, $0<\tau$ sufficiently small, andhas a family $\mathcal{C}$ covering its hypergraph independent sets withOne obtains this form by iterating a degree-measure hypergraph container theorem, recording small container fingerprints at each step. To ensure the requested strict edge inequality, apply it with $\epsilon /2$.

For our clique hypergraph, $m=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$, $R=\left(\genfrac{}{}{0ex}{}{t}{2}\right)$ and $e(G)=\left(\genfrac{}{}{0ex}{}{N}{t}\right)$. The established codegree bound permits this choice of $\tau$, andEvery container, viewed as an ordinary graph, has at most $\epsilon \left(\genfrac{}{}{0ex}{}{N}{t}\right)$ copies of $K_t$.

We also use clique supersaturation: for each fixed $\gamma >0$, graphs with at least $(1-1/(t-1)+\gamma )\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ edges have at least $b_{\gamma }{N}^t$ copies of $K_t$, for some $b_{\gamma }>0$ and all sufficiently large $N$. For clarity, this follows already from the Erdős-Stone theorem: choose a fixed sample size $q$ with $\mathrm{ex}(q,K_t)\le (1-1/(t-1)+\gamma /2)\left(\genfrac{}{}{0ex}{}{q}{2}\right)$. A uniformly sampled $q$-set has expected value of the edge count above this bound by at least $(\gamma /2)\left(\genfrac{}{}{0ex}{}{q}{2}\right)$, forcing a positive proportion of samples to contain a clique. Counting each clique's extensions to $q$-sets then gives the claimed $b_{\gamma }{N}^t$ bound.

Choose $\epsilon$ smaller than the corresponding supersaturation constant after converting $\left(\genfrac{}{}{0ex}{}{N}{t}\right)$ to $N^t$. Each container has fewer than $(1-1/(t-1)+\gamma )\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ ordinary edges. Every $K_t$-free graph is a subgraph of one of these containers, so their number is at mostConversely, every subgraph of a balanced Turán graph with $t-1$ parts is $K_t$-free, giving at least $2^{(1-1/(t-1))\left(\genfrac{}{}{0ex}{}{N}{2}\right)-O(N)}$ possibilities. Letting $\gamma$ be arbitrarily small proves the enumeration formula:

Write $\alpha =1-1/r$. The Erdős-Stone theorem states that, for a fixed graph $F$ with chromatic number $\chi (F)=r+1\ge 2$,Here $\mathrm{ex}$ is the extremal number, and copies are subgraphs, not necessarily induced subgraphs. We write $K_a(b)$ for the balanced complete multipartite blow-up with $a$ classes of $b$ vertices each. All asymptotic errors below concern $n\to \infty$ with the forbidden graphs fixed.

The stability subgraph. We prove the high-minimum-degree multipartite stability subgraph assertion directly from the Erdős-Stone theorem. For $r=1$, the edgeless spanning subgraph suffices. Suppose $r\ge 2$.

First repeatedly remove a vertex whose degree of a vertex is less than $(\alpha -{\epsilon }_n)$ times the current order, where ${\epsilon }_n\to 0$ sufficiently slowly. The Erdős-Stone theorem gives, uniformly for every $K_{r+1}(t)$-free subgraph $J$ of order at most $n$,Indeed, apply the asymptotic bound at large orders; the contribution from bounded or sufficiently small orders is negligible relative to $n^2$. If $m$ vertices survive, the removed edges number at mostComparing with $e(G_n)=\alpha n^2/2+o(n^2)$ shows that ${\epsilon }_n(n^2-m^2)=o({\epsilon }_n{n}^2)$, provided ${\epsilon }_n$ dominates ${\eta }_n$, the initial relative error, and $1/n$. Consequently $m=n-o(n)$. The surviving induced subgraph $G^{\prime }$ satisfies $\delta (G^{\prime })\ge (\alpha -o(1))m$ and $e(G^{\prime })=\alpha m^2/2+o(m^2)$.

By the Erdős-Stone theorem, $G^{\prime }$ contains $K_r(L)$ for some $L=L_n\to \infty$ as slowly as necessary. This follows because $\alpha$ exceeds the extremal number density for each fixed $K_r(L)$ by the positive gap $1/(r(r-1))$. Choose $L$ so slowly that $rL=o(m)$ and ${\left(\genfrac{}{}{0ex}{}{L}{t}\right)}^r=o(m)$, and denote its root classes by $A_1,\dots ,A_r$.

An outside vertex having at least $t$ neighbours of a vertex in every $A_i$ determines one choice of a $t$-subset in each $A_i$. At most $t-1$ outside vertices can determine any fixed choice, since otherwise these vertices and the chosen root sets form $K_{r+1}(t)$. Thus at most $(t-1){\left(\genfrac{}{}{0ex}{}{L}{t}\right)}^r=o(m)$ outside vertices have this property. Exclude those vertices and the root classes; put each remaining vertex in a class $C_i$ for which it has fewer than $t$ neighbours of a vertex in $A_i$.

Write $\delta (G^{\prime })\ge (\alpha -{\gamma }_n)m$, with ${\gamma }_n\to 0$. Counting missing incidences with $A_i$ givesSince ${\sum }_i|C_i|=m-o(m)$, it follows that $|C_i|=m/r+o(m)$ for every $i$. The total missing incidences from all root vertices to assigned vertices are at most $(1+r{\gamma }_n)Lm$. At least $(L-t+1)(m-o(m))$ of them are incidences with a vertex's own assigned root class. Hence only $o(Lm)$ missing incidences go to other root classes.

Choose ${\rho }_n\to 0$ slowly and discard the $o(m)$ assigned vertices with more than ${\rho }_{n}L$ missing incidences to other root classes. Each remaining vertex of $C_i$ is adjacent to all but at most ${\rho }_{n}L$ vertices of every $A_j$, $j\ne i$. If its class contained a complete bipartite graph $K_{t,t}$, the $2t$ vertices of this copy would have at least $L-2t{\rho }_{n}L\ge t$ common neighbours of a vertex in each other root class. These sets extend the copy to $K_{r+1}(t)$, a contradiction. By the bipartite case of the Erdős-Stone theorem, the number of internal edges in each surviving class is $o(m^2)$.

The surviving graph still has $\alpha m^2/2+o(m^2)$ edges, whereas the total possible cross-class edges, with these balanced classes, is $\alpha m^2/2+o(m^2)$. Thus only $o(m^2)$ cross-class edges are missing. Discard the $o(m)$ vertices missing more than ${\sigma }_{n}m$ cross-class edges, with ${\sigma }_n\to 0$ slowly, and delete all internal edges. The resulting $r$-partite subgraph $H$ has classes $H_i$ of size $n/r+o(n)$ andFor the lower bound, every surviving vertex misses only $o(n)$ vertices outside its class; the upper bound follows from the class sizes. This also records the uniform cross-class error that we need next.

Minimum degree in an extremal graph. Fix $F$ with $\chi (F)=r+1$. Choose $t$ large enough that $F$ embeds in $K_{r+1}(t)$. An extremal $F$-free graph $G$ is therefore $K_{r+1}(t)$-free, and its edge count has the required asymptotics by the Erdős-Stone theorem. For $r\ge 2$ take $H$ as above.

For any vertex $v$, remove $v$ and introduce a new vertex $v^{\ast }$ whose vertex neighbourhood consists precisely of the vertices in $H_2\cup \cdots \cup H_r$ other than $v$. The new degree of a vertex is $\alpha n-o(n)$. This new graph remains $F$-free. Indeed, a new copy of $F$ must use $v^{\ast }$, and all its neighbours of a vertex in that copy lie in the other classes of $H$. There are only boundedly many of them. Each misses only $o(n)$ vertices in $H_1$, so an unused vertex $w\in H_1$ is adjacent to all of them. Replacing $v^{\ast }$ by $w$ would give $F$ in $G-v$, which is impossible.

Extremality now forces $d_G(v)\ge \alpha n-o(n)$, uniformly in $v$. The upper bound for the minimum degree of a graph follows from $\delta (G)\le 2e(G)/n$. For $r=1$, $e(G)=o(n^2)$ already gives $0\le \delta (G)=o(n)$. ThusThis is the minimum degree of an extremal forbidden-subgraph graph principle.

The exact extremal graph for disjoint cliques. DefineThe plus sign denotes the join of graphs. The Turán graph contains no $K_{r+1}$, so every such clique in $J_s(n)$ uses a vertex of $K_{s-1}$. Therefore $J_s(n)$ contains no $s$ vertex-disjoint such cliques, and the extremal number is at least $b_s(n)$.

Induct on $s$, with $s=1$ supplied by the Turan theorem, including its equality characterization. Let $s\ge 2$ and let $G$ be extremal for $s{K}_{r+1}$. The preceding results give $\delta (G)\ge \alpha n-o(n)$ and the $r$-partite subgraph $H$. Keep its classes $H_i$ fixed and assign each of the remaining $o(n)$ vertices to a class in which it has fewest neighbours of a vertex in $H$. Write the resulting classes as $C_i$; all have size $n/r+o(n)$. Choose a positive ${\tau }_n\to 0$ so slowly that ${\tau }_{n}n$ dominates the outside count, every cross-class error in $H$, and every error in the minimum degree of a graph bound.

Suppose some vertex $x\in C_i$ has at least ${\tau }_{n}n$ internal neighbours of a vertex. If $x\notin H$, the assignment rule shows that $x$ has at least ${\tau }_{n}n-o(n)$ neighbours of a vertex in every $H_j$. If $x\in H_i$, it has this many in $H_i$ and $n/r-o(n)$ in the other $H_j$. If $G-x$ contained $s-1$ disjoint $K_{r+1}$, we could choose one vertex in each $N(x)\cap H_j$, successively avoiding those copies and the $o(n)$ missing cross-neighbours of the already chosen vertices. This produces a further $K_{r+1}$ through $x$. For $r=1$, this just chooses an unused neighbour of $x$. Hence $G-x$ is $(s-1)K_{r+1}$-free, and induction givesSince the candidate attains $b_s(n)$, equality holds throughout: $x$ is a universal vertex and $G-x$ is the inductively unique extremal graph. Thus $G$ is isomorphic to $J_s(n)$.

It remains to show that this case must occur. Otherwise all internal vertex degrees are less than ${\tau }_{n}n=o(n)$. Together with the lower bound on $\delta (G)$ and $|C_i|=n/r+o(n)$, this implies that every vertex misses only $o(n)$ vertices outside its own class. If some $C_i$ contains a matching in a graph of $s$ edges, extend its edges one by one to $K_{r+1}$, choosing one vertex from each other class. At every step only $o(n)$ cross-neighbours and boundedly many used vertices are excluded. This gives $s$ disjoint forbidden cliques, a contradiction.

A maximal matching in each class therefore has at most $s-1$ edges, and its at most $2(s-1)$ endpoints form a vertex cover of the internal edges. Their internal vertex degrees are all $o(n)$, so the total internal edge count is $o(n)$. The cross-class edge count is at most $e(T_r(n))$, whenceBut the balanced part sizes of the Turán graph givecontradicting extremality for $s\ge 2$. This argument also works for $r=1$. Consequently, for all sufficiently large $n$,The uniqueness is up to isomorphic graphs, as usual for an extremal graph for disjoint cliques.

The Erdős-Stone theorem states that if the chromatic number of $H$ is $r+1\ge 2$, thenIf $H$ is a bipartite graph with at least one edge, its chromatic number is two, so $r=1$ and therefore

The Erdős-Stone theorem states precisely that, for every fixed graph $H$ with chromatic number $\chi (H)\ge 2$,If the bipartite graph $G$ has an edge, then $\chi (G)=2$. Substitution into the theorem givesIf $G$ has no edges, then every graph of sufficiently large order contains $G$ as a subgraph, so the conclusion is immediate.