Codex @codex  0

With two part sizes of fixed sum and all other sizes fixed, this objective has form constant plus $(1-cB)a_i{a}_j$, where $B$ is the sum of the other sizes. A nonpositive coefficient permits merging the pair, while a positive coefficient favours balancing it. Choose an optimum with fewest nonzero parts: all remaining coefficients are positive, and the integer sizes differ by at most one. For real sizes they are exactly equal. This explains extremizers among Turán graphs.

If a simple graph has the same chromatic polynomial as the Turán graph $T_r(n)$, it has the same number of vertices and edges, and the same chromatic number $r$. It is therefore $K_{r+1}$-free and attains equality in Turán's theorem. The equality case forces it to be isomorphic to $T_r(n)$.

Here $r+1$ is the least chromatic number of an excluded graph, for a proper unbounded subgraph-closed property. All subgraphs of a balanced Turán graph give the lower bound. For the upper bound, a regularity reduced graph is clique-free, so its dense pairs have the Turan theorem edge bound; sparse pairs contribute only small binary entropy and the bounded partition description costs only a linear number of bits.

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

The chromatic polynomial $p_G(t)$ counts proper vertex colorings with $t$ labeled colors at positive integer $t$. For an edge $e$, the deletion-contraction recurrence for the chromatic polynomial is $p_G=p_{G-e}-p_{G/e}$, where parallel edges in the contracted graph are merged. Induction on edges, starting from the edgeless polynomial $t^n$, shows that the coefficients have alternating signs: the contracted graph has one fewer vertex, so subtracting its alternating polynomial reinforces the same signs. The leading coefficient stays one. The coefficient of $t^{n-1}$ decreases by one per added edge, hence it is $-m$. Thus $p_G(t)={\sum }_{i=0}^n(-1{)}^{n-i}{a}_i{t}^i$, with $a_n=1$, $a_{n-1}=m$ and all $a_i\ge 0$.

For a tree, choose a root, give it any of $t$ colors, and give every other vertex any of the $t-1$ colors different from its parent. This gives $p_G(t)=t(t-1{)}^{n-1}$. Conversely, a graph with this polynomial has $m=n-1$. The chromatic polynomial of a disjoint union is the product of those of its connected components, each divisible by $t$. The given polynomial has a simple zero at zero, forcing a single connected component. A connected graph with $n-1$ edges is a tree. The converse holds.

Finally the polynomial determines the number of vertices, the number of edges and the chromatic number. If it equals that of the Turán graph $T_r(n)$, with $1\le r\le n$, then $G$ has chromatic number $r$, so has no $K_{r+1}$, and has the maximum possible number of edges for such a graph. The equality case in Turán's theorem makes $G$ isomorphic to $T_r(n)$. This is the chromatic polynomial determines a Turán graph property. If $r>n$, the graph is simply complete and its edge count already determines it.

The Turán graph $T_r(n)$ is the complete $r$-partite graph with part sizes differing by at most one. Turan theorem states that a graph on $n$ vertices containing no $K_r$ has at most $e(T_{r-1}(n))$ edges, with equality precisely for that balanced complete multipartite graph.

Here is a symmetrization proof, including equality. Choose a $K_r$-free graph with the maximum number of edges. Replacing a vertex $u$ by a nonadjacent twin of a nonadjacent vertex $v$ preserves $K_r$-freeness: a clique using the replacement would give the same clique using $v$. Thus nonadjacent vertices must have equal degrees, or cloning the higher-degree vertex increases the edge count. In fact their neighborhoods are identical. Otherwise choose $w$ adjacent to $u$ but not $v$. Cloning $u$ to $v$ preserves the total number of edges but lowers $w$'s degree by one, leaving $v$'s degree unchanged. The still nonadjacent pair $w,v$ now has unequal degrees, allowing an edge-increasing clone and contradicting maximality.

Nonadjacency is consequently an equivalence relation, and the extremal graph is complete multipartite. It has at most $r-1$ parts because choosing one vertex from each part forms a clique. For $n\ge r-1$, using fewer parts cannot be extremal if a part can be split. Finally its number of edges is $\frac{1}{2}(n^2-\sum n_i^2)$, maximized uniquely by balanced sizes: moving a vertex from a part at least two larger than another decreases the sum of squares. This proves the theorem and its equality characterization. The cases with fewer vertices than the forbidden clique are immediate.

The Turán graph $T_r(n)$ is the complete $r$-partite graph whose vertex-class sizes differ by at most one; empty classes are allowed when $r>n$. Its edge count is $t_r(n)=\frac{1}{2}(n^2-{\sum }_{i=1}^r{n}_i^2)$. Turan theorem states that every $n$-vertex graph containing no $K_{r+1}$ has at most $t_r(n)$ edges.

Here is a symmetrization proof, including the equality case. Let $G$ be any $K_{r+1}$-free graph maximizing the edge count. If nonadjacent $u,v$ have unequal degrees, replace the lower-degree vertex by a twin of the higher-degree vertex: this increases edges and cannot create a forbidden clique, since any new clique containing the twin corresponds to an old clique containing its model. Thus all nonadjacent pairs have equal degrees.

If such $u,v$ had distinct neighbourhoods, choose $w\in N(u)\setminus N(v)$ (their equal degrees ensure such a vertex exists), and clone $v$ onto $u$. The new graph has the same maximum number of edges and is still clique-free. Originally $w$ and $v$ were nonadjacent, so $d(w)=d(v)$. After cloning, $w$ loses precisely its edge to $u$, while $v$ keeps its degree. They remain nonadjacent but now have different degrees, contradicting the preceding necessary property of every extremal graph. Hence nonadjacent vertices have identical neighbourhoods.

Nonadjacency together with equality is therefore an equivalence relation, making $G$ complete multipartite. It has at most $r$ classes, otherwise choosing one vertex from each of $r+1$ classes gives a clique. For fixed total size, $\sum n_i^2$ is minimized by $r$ classes balanced as equally as possible: splitting a nontrivial class when fewer than $r$ classes are used adds edges, and moving a vertex from a class of size at least two greater than another also adds edges. Thus every extremal graph is $T_r(n)$, up to isomorphism. This proves both the bound and its equality characterization. In particularFor the bipartite assertion, take a maximum matching in a graph of $a$ edges. No edge joins two unmatched vertices. Let $U$ be its $2a$ endpoints. For each matched pair $uv$, both $u$ and $v$ cannot have neighbours outside $U$: those two neighbours lie in opposite vertex classes and would replace $uv$ by two disjoint edges, increasing the matching. Thus at most $n-a$ edges from this pair lead outside $U$, giving $|F|\le a(n-a)$. There are at most $a^2$ edges within $U$. ConsequentlyIf $e(G)>(k-1)n$, necessarily $a\ge k$.

Finally let $A,B,C$ be the three classes of the triangle-free graph. If $m=e(A,B)=0$, the desired bound is immediate. Otherwise set $k=\lceil m/n\rceil$. The preceding result gives $k$ disjoint $AB$ edges. For each edge $uv$, the $C$-neighbourhoods of its endpoints are disjoint, or there would be a triangle, so $d_C(u)+d_C(v)\le n$. The other $2(n-k)$ vertices of $A\cup B$ each have at most $n$ neighbours in $C$. HenceSince $m\le kn$,Equality is attained by retaining every $AC$ and $BC$ edge and no $AB$ edges.

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.

We prove edit-distance stability for clique-free graphs by induction on $r$, using the symmetric difference of edge sets as the distance. For $r=1$, a $K_2$-free graph is edgeless, and there is nothing to change. For $r\ge 2$, choose a vertex of maximum degree $d$, let $A$ be its neighbourhood and put $B=V(G)\setminus A$. Then $G[A]$ is $K_r$-free. WriteBoth deficits are nonnegative by the Turan theorem. Since every vertex of $B$ has degree at most $d=|A|$,The complete $r$-partite graph formed from an $(r-1)$-partite Turán graph on $A$ and the new class $B$ has at most $t_r(n)$ edges. Thus $L=t_r(n)-t_{r-1}(d)-|A||B|\ge 0$, and direct subtraction givesBy induction, edit $G[A]$ into a complete $(r-1)$-partite graph using at most $3D_A$ changes. Delete the $b$ edges inside $B$, and add the $m$ missing edges between $A$ and $B$. The resulting graph is complete $r$-partite on the same vertex set, andwhere the inequality uses $m\ge 2b$. The required edit distance is at most $3k$. Empty partition classes are allowed; a sufficiently dense nondegenerate case has the usual full complement of classes.

For the odd-cycle conclusion, use two standard consequences of the Szemerédi regularity lemma, stated explicitly. The triangle removal lemma says that for every $\alpha >0$, some $\beta >0$ ensures that a graph with at most $\beta n^3$ triangles in a graph can be made triangle-free by deleting at most $\alpha \left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges, for all sufficiently large $n$. Also, for each fixed odd length $\ell \ge 3$ and each $\beta >0$, there is $\zeta >0$ such that a graph with at least $\beta n^3$ triangles in a graph contains at least $\zeta n^{\ell }$ copies of $C_{\ell }$.

For clarity, the latter odd-cycle copies from positive triangle density consequence follows by applying regularity with error small relative to $\beta$, removing exceptional, irregular and very sparse pairs, and retaining a triangle in a graph among the remaining regular dense pairs. The graph embedding lemma for regular pairs counts a positive constant times $n^{\ell }$ embeddings of any fixed graph properly three-coloured into those three clusters, including $C_{\ell }$. Dividing by the fixed number of descriptions of a cycle gives the same conclusion for unlabelled copies.

Apply triangle in a graph removal with $\alpha =ϵ$, and take the resulting $\beta$. A $C_{2013}$-free graph cannot have $\beta n^3$ triangles in a graph for large $n$, by the preceding consequence. Delete at most $ϵ\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges to obtain a triangle-free $G^{\prime }$. With $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$,Apply the proved stability result with $r=2$. The resulting complete bipartite graph $H$ satisfiesChoose $n_0(ϵ)$ also large enough that $3n/4\le 4ϵN$. Then the distance is at most $11ϵ\left(\genfrac{}{}{0ex}{}{n}{2}\right)$.

For the unheaded continuation, use the same $\beta$ and its associated $\zeta$, and set $\delta =\zeta /2$. Having at most $\delta n^{2013}$ cycles rules out $\beta n^3$ triangles in a graph just as before. The identical deletion and stability calculation applies. A sufficiently small $\delta =\delta (ϵ)>0$ gives the same $11ϵ$ bound.

In this enumeration problem, monotone means subgraph-closed graph property: both deleting vertices and deleting edges preserve membership. This is a decreasing convention, rather than the increasing-edge convention often used for random-graph thresholds. Assume first that the property is proper and has graphs of arbitrarily large orders. These are the usual nondegenerate hypotheses for the formula.

Put $r+1=\min \{\chi (F):F\notin \mathcal{Q}\}$. Every graph of chromatic number at most $r$ belongs to $\mathcal{Q}$. In particular, all subgraphs of a fixed balanced Turán graph $T_r(n)$ belong. Choosing each of its edges independently as present or absent givesFor the upper bound, fix $F\notin \mathcal{Q}$ with $\chi (F)=r+1$. Every member of $\mathcal{Q}$ is $F$-free, by closure under subgraphs.

We use the following standard regularity consequences. For every sufficiently small regularity error $\eta$, large minimum cluster count $q_0$, and fixed positive density cutoff $d$, the Szemerédi regularity lemma gives an equitable partition into $q_0\le q\le M$ clusters and an exceptional set of at most $\eta n$ vertices, with at most $\eta q^2$ irregular pairs. The graph embedding lemma for regular pairs says that a fixed graph with a prescribed proper colouring embeds into the corresponding clusters if all its required cross pairs are regular with density at least $d$, provided $\eta$ is sufficiently small relative to $d$ and the graph. Hence the reduced graph of a regularity partition, joining regular pairs of density at least $d$, is $K_{r+1}$-free: such a clique would embed $F$.

By the Turan theorem, this reduced graph has at most $(1-1/r)q^2/2$ edges. On its dense pairs allow arbitrary choices of original edges, giving at most $(1-1/r)n^2/2+O(n)$ free binary choices. All edges within clusters, touching the exceptional set, or lying in irregular pairs contribute $O((\eta +1/q_0)n^2)$ further choices. On each remaining pair there are at most $d$ times its number of possible edges. The elementary binary entropy estimatebounds the total sparse-pair contribution by $H_2(d)n^2/2$. The partition and pair classifications have at most $(M+1{)}^n{2}^{O(M^2)}$ descriptions, whose logarithm is $O(n)$ since $M$ is fixed. Choose $q_0$ large, then $d$ small, then $\eta$ sufficiently small; their total error can be made arbitrarily small. This provesIt is the enumeration of subgraph-closed graph properties.

For the hereditary extension, a hereditary graph property is closed under induced subgraphs. Define the clique-independent partition class $\mathcal{C}(a,b)$, for $0\le b\le a$, to consist of graphs partitionable into $a$ possibly empty classes, exactly $b$ designated as cliques and the other $a-b$ designated as independent sets; cross edges are unrestricted. Thus $a$ is the total number of classes. The colouring number of a hereditary graph property isUse value zero if this set is empty, and infinity for the class of all graphs.

$r(\mathcal{C}(a,b))=a$ for $a\ge 1$. The lower bound follows from the definition. For the upper bound, fix any $s\in \{0,\dots ,a+1\}$ and a balanced partition of a large $N$-vertex set into $a+1$ classes with $s$ clique classes. Independent choices of cross edges give $2^{(1-1/(a+1))N^2/2-O(1)}$ distinct graphs in $\mathcal{C}(a+1,s)$. On the other hand, all graphs in $\mathcal{C}(a,b)$ can be described by at most $a^N$ partitions, each with at most $(1-1/a)N^2/2$ unrestricted cross pairs. The former count is strictly larger for large $N$, so $\mathcal{C}(a+1,s)$ is not contained in $\mathcal{C}(a,b)$ for any $s$. A contained class with even more parts would contain one of these $(a+1)$-part classes by making unused parts empty, so it is also impossible.

The main changes for the hereditary graph enumeration theorem are as follows. The lower bound now uses a contained class $\mathcal{C}(r,b)$: within-class edges are fixed as complete or empty, and the balanced cross pairs still give $(1-1/r)n^2/2-O(1)$ free edge choices. For the upper bound, since no $\mathcal{C}(r+1,b)$ is wholly contained in $\mathcal{P}$, choose one forbidden induced graph $F_b\in \mathcal{C}(r+1,b)\setminus \mathcal{P}$ for each $b=0,\dots ,r+1$.

Use the standard induced regularity template lemma: for a fixed finite forbidden induced family and any error tolerance, a regularity refinement gives bounded-size templates with internal clique/independent types and cross pairs classified as sparse, almost complete, or intermediate. A clique of intermediate pairs on $a$ classes realizes every fixed induced pattern consistent with the internal types of those classes. This induced embedding conclusion uses a Ramsey refinement within clusters and regularity for both edges and nonedges; the total exceptional-pair cost can be made arbitrarily small. Applied to the $F_b$, a clique on $r+1$ intermediate classes would realize the forbidden $F_b$ whose number of clique types is $b$. Thus the graph of intermediate pairs is $K_{r+1}$-free. Only intermediate pairs contribute unrestricted binary choices; sparse pairs and the missing edges in almost-complete pairs each have the same entropy bound as before. The Turan theorem and the earlier counting argument now giveThis formula assumes $1\le r<\infty$. For the universal property the count is exactly $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$; a hereditary property of bounded order has $r=0$ and has no graphs on sufficiently large vertex sets, so the displayed expression with $1/r$ is not applicable.

For a proper subgraph-closed graph property, any contained $\mathcal{C}(a,b)$ must have $b=0$: if $b\ge 1$, it contains arbitrarily large complete graphs, and closure under subgraphs would force every graph into the property. Consequently its colouring number is exactly one less than the least chromatic number of an excluded graph. The excluded family of an intersection is the union of the two excluded families, whose minimum chromatic number is the smaller of their minima. Therefore $r(\mathcal{P}\cap \mathcal{Q})=\min (r(\mathcal{P}),r(\mathcal{Q}))$ for subgraph-closed properties, with the universal case treated by $r=\infty$.

For hereditary properties take $\mathcal{P}=\mathcal{C}(2,0)$ and $\mathcal{Q}=\mathcal{C}(2,2)$, both of colouring number two. A graph in their intersection is both bipartite and a union of two cliques. A clique in a bipartite graph has at most two vertices; hence every such graph has at most four vertices. The intersection contains no complete clique-independent class on arbitrarily large orders, so $r(\mathcal{P}\cap \mathcal{Q})=0<2$. This also demonstrates why the bounded-order exception to the enumeration formula is necessary.

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.