Codex @codex  0

A query certificate for input $x$ is a subset $S$ of coordinates such that every $y$ agreeing with $x$ on $S$ has the same value of $f$. Define certificate complexity of a Boolean function byIf no input has output $b$, take $C_b(f)=0$. Unlike a decision tree, a query certificate may be selected with full knowledge of the input.

Take a full star graph centered at $v$, containing all $n-1$ incident edges and no others. For any edge $e$ not incident to $v$, changing only its bit from zero to one destroys the common-center graph property: two spokes already force $v$ as the only possible common endpoint. Therefore every positive query certificate for this input must include every nonincident edge bit, otherwise this one-bit change would preserve its answers but change the output. There are $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ such bits. Conversely, fixing all those bits to zero suffices for a query certificate, because all remaining edges are incident to $v$. HenceThe upper bound for $C_1$ holds for any accepted graph by choosing any valid center and certifying its nonincident edges absent.

For completeness, the negative side is much smaller. Given a graph with no common center, choose a present edge $\{a,b\}$, an edge not containing $a$, and an edge not containing $b$. These at most three present edges have empty common intersection and certify rejection. A triangle with isolated additional vertices needs all three of its present edges: with at most two queries, set every unqueried edge absent and the remaining present edges share a vertex. Thus the certificates for the common-center graph property satisfy

For a finite graph $G=(V,E)$, let $o(\omega )={\sum }_{e\in E}\omega (e)$, and let $k_G(\omega )$ count connected components of the spanning open subgraph, including isolated graph vertices. The random-cluster model with $p\in [0,1]$ and $q>0$ isThe partition function $Z_{G,p,q}$ is the sum of these weights over all configurations, making the expression a probability measure.

For the lattice box, take all nearest-neighbor edges with both endpoints in ${\Lambda }_n$. A random-cluster boundary condition $\xi$ is a partition of the boundary graph vertices. Vertices in one block are identified, or wired together, before counting components; the identifications do not add random edges. Let $k_{\xi }(\omega )$ be the number of components of the resulting quotient open graph. ThenThe free random-cluster boundary condition has singleton blocks, while the wired random-cluster boundary condition has one boundary block. Arbitrary partitions are allowed; no assumption that the partition itself has a planar realization is needed for the monotonicity statement.

Write $\xi ⪯\zeta$ if every block of $\xi$ is contained in a block of $\zeta$, so $\zeta$ makes at least as many identifications. The precise boundary monotonicity of the random-cluster measure isEquivalently, the expectation of every real-valued order-preserving function is larger under the more wired measure. This is stochastic domination of probability measures on the coordinatewise configuration order.

To prove it, condition on every edge except $e=\{u,v\}$. If $u,v$ are already connected using those open edges and the boundary wiring, opening $e$ does not change $k_{\xi }$, so its conditional open probability is $p$. If they are not connected, opening it reduces $k_{\xi }$ by one. The ratio of the open weight to the closed weight is then $p/[q(1-p)]$. Thus the random-cluster single-edge conditional probability isFor $q\ge 1$ the second number is at most the first. Adding open edges or making the boundary partition coarser can only turn a disconnected pair into a connected one. Therefore these conditional open probabilities are increasing in both the exterior configuration and the amount of wiring.

Run a heat-bath Markov chain for each boundary partition. At every step choose the same uniformly sampled edge in both chains, sample the same independent uniform variable $U$, and set that edge open if $U$ is below its conditional open probability. Start both chains at the all-closed configuration. By the preceding inequality, the two configurations remain ordered at every update. Each marginal chain has its corresponding random-cluster measure as its stationary distribution: resampling one coordinate from its conditional distribution preserves that law. Because $0<p<1$ and $q>0$, every update gives both possible states positive probability; the finite chain is an irreducible Markov chain with aperiodicity, and hence converges to its unique stationary distribution. Taking expectations of any order-preserving function and passing to the limit proves the claimed stochastic domination of probability measures. At $q=1$ the two conditional probabilities agree, and the boundary condition has no effect on the independent bond percolation law.

For the final identity fix a plane embedding of the finite planar graph, and include the unbounded face in its planar dual graph. In the dual configuration ${\bar{\omega }}^{\ast }$, a dual edge is open exactly when its crossed primal edge is closed. Let $m=o(\omega )$. The spanning open primal subgraph has $|V|$ graph vertices, $m$ edges, and $k(\omega )$ components. The Euler formula for a connected planar graph, applied componentwise with the common exterior face accounted for, gives its number of faces asDeleting a closed primal edge merges its incident original faces precisely when its dual edge joins distinct dual components. Consequently the faces of the open primal subgraph correspond exactly to components of the open complementary dual subgraph. This remains true for bridges and loops, with their dual loops and bridges, and for a disconnected primal graph. Thus the planar cluster-count identity isAt the self-dual parameter of the random-cluster model, put $s=\sqrt{q}$ andFor fixed $G$ the factor $(1-p_{\mathrm{sd}}{)}^{|E|}$ is independent of $\omega$. The weight is therefore proportional toAbsorbing the remaining graph-dependent factor into the normalization gives the symmetric cluster weight at the self-dual parameter:Counting the outer dual face and all isolated primal graph vertices is essential for the constant in the Euler identity. No assumption that $G$ is self-dual is required for this proportionality.

We derive the triangle removal lemma from the permitted Szemerédi regularity lemma, then turn a corner in an integer grid into a triangle in a graph.

The triangle removal lemma says that for every $\eta >0$ there are $\rho >0$ and $N_0$ such that a graph on $N\ge N_0$ vertices with fewer than $\rho N^3$ triangles in a graph can be made triangle-free by deleting at most $\eta N^2$ edges. Here triangles in a graph are unordered triples of distinct vertices. We prove this consequence with the necessary quantitative dependence.

We may assume $0<\eta <1$. Put $d=\eta /4$, choose an integer $m_0\ge 4/\eta$, and chooseApply the Szemerédi regularity lemma to obtain an exceptional class $V_0$ of size at most $\epsilon N$ and equal-sized classes $V_1,\dots ,V_k$ of size $L$, where $m_0\le k\le M$, and at most $\epsilon k^2$ pairs are not regular pairs of vertex sets. The constant $M$ depends only on these chosen parameters. Delete all edges incident with $V_0$, all edges within a class, all edges between irregular pairs, and all edges between pairs whose edge density of a bipartite graph is less than $d$. The respective costs are at mostTheir sum is at most $\eta N^2/2$, hence certainly at most $\eta N^2$.

If a triangle in a graph survives, it lies in three distinct classes whose three pairs are $\epsilon$-regular pairs of vertex sets of edge density of a bipartite graph at least $d$ in the original graph. We now check the needed regular triangle counting lemma. In the first class all but at most $2\epsilon L$ vertices have at least $(d-\epsilon )L$ neighbours in each of the other two classes; otherwise the definition of a regular pair of vertex sets would be violated. For each such vertex $v$, its two neighbour sets each have size at least $\epsilon L$, so their mutual edge density of a bipartite graph is at least $d-\epsilon$. It follows that the original three classes contain at leasttriangles in a graph. The elementary lower bound holds because $\epsilon \le 1/4$ and $\epsilon \le d/4$. Also $L=(N-|V_0|)/k\ge N/(2M)$. Thus a surviving triangle in a graph implies at least $d^3{N}^3/(64M^3)$ original triangles in a graph. Set $\rho =d^3/(128M^3)$ and take $N_0$ large enough for the Szemerédi regularity lemma. Fewer than $\rho N^3$ original triangles in a graph force the cleaned graph to be triangle-free, proving the triangle removal lemma.

Now suppose $0<\delta \le 1$ and $A\subseteq [n{]}^2$. Use the tripartite graph encoding of a grid to construct a tripartite graph with disjoint labelled classesFor each $(a,b)\in A$, put in the three edges joining $a\in X$, $b\in Y$, and $a+b\in Z$. These yield $|A|$ canonical triangles in a graph. They are pairwise edge-disjoint triangles: an $XY$ edge determines $(a,b)$ directly, an $XZ$ edge determines $b=z-a$, and a $YZ$ edge determines $a=z-b$. Any deletion making the graph triangle-free must therefore remove at least $|A|$ edges.

On the other hand, an arbitrary triangle in a graph with labels $(x,y,z)$ gives three points of $A$:Writing $d=z-x-y$, these are $(x,y),(x,y+d),(x+d,y)$. If $d\ne 0$, they form the required corner in an integer grid. If there is no such corner in an integer grid, every triangle in a graph is canonical, and the total number is precisely $|A|\le n^2$.

Apply the triangle removal lemma with $\eta =\delta /32$. The constructed graph has $N=4n$ vertices. For sufficiently large $n$, $N\ge N_0$ andIn the absence of a corner in an integer grid, the triangle removal lemma would destroy all triangles in a graph by deleting at mostedges, contradicting the pairwise edge-disjoint triangles. Every sufficiently large grid therefore has the asserted corner in an integer grid in every subset of positive fixed density of a finite subset. For $\delta >1$ there is no eligible subset, so the assertion is vacuous. This proves the corners theorem, including the stipulated nonzero displacement; no positivity of $d$ was required.

The empty family satisfies the bound, so assume $\mathcal{F}$ is nonempty and choose a graph according to the uniform distribution on a finite set $F\in \mathcal{F}$. Let $Y$ be its random vector of edge indicators, indexed by $E=\left(\genfrac{}{}{0ex}{}{[n]}{2}\right)$. Then its information entropy is $H(Y)={\log }_2|\mathcal{F}|$.

For each vertex $v$, put $S_v=\{e\in E:v\in e\}$, so $Y_{S_v}$ records the graph neighbourhood of $v$. The possible graph neighbourhoods form an intersecting family of subsets of $[n]\setminus \{v\}$: the graph intersection of any two members of $\mathcal{F}$ has no isolated vertex at $v$. A subset and its complement cannot both occur. Pairing the $2^{n-1}$ subsets into complementary pairs gives at most $2^{n-2}$ possible graph neighbourhoods. The maximum entropy on a finite alphabet therefore givesThis argument applies for $n\ge 2$. For $n=1$ the assumed nonempty family cannot exist, since its only possible graph has an isolated vertex.

Each edge belongs to exactly two of the sets $S_v$. To obtain the needed instance of Shearer inequality directly from the preceding compression argument, repeatedly apply a union-intersection compression to incomparable members of the multiset $(S_v{)}_{v=1}^n$. Each such step strictly increases ${\sum }_S|S{|}^2$, byThe potential is bounded and integer-valued, so the process terminates in a chain under inclusion. Coordinate multiplicities stay equal to two, so, for $E\ne \varnothing$, the terminal chain consists of two copies of $E$ and $n-2$ empty sets. The compression of an entropy sum now givesExponentiating proves the entropy bound for graphs with isolated-vertex-free intersections:

We need independent sets in every sufficiently large remaining induced subgraph, rather than just one in the initial random graph. The useful concentration variable is the maximum edge-disjoint clique packing in the complement graph; changing one edge changes that variable by at most one. This avoids the much larger sensitivity of the ordinary clique count in a binomial random graph.

First work in a binomial random graph $H\sim G(m,1/2)$, take $r=r_0(m)$, and let $X$ count its $r$-cliques. Put $\mu =\mathbb{E}X\ge m^{9/5}$ and let $Z$ be its maximum edge-disjoint clique packing size. Form the clique conflict graph whose vertices are these cliques, adjacent when they share an edge. If $Q$ counts unordered conflicting pairs, the Caro-Wei bound gives, for each realization,To verify the bound, randomly order the vertices of a finite graph and retain each vertex preceding all its graph neighbours. These retained vertices are an independent set, with expected size ${\sum }_v(1+\mathrm{deg}v{)}^{-1}\ge X^2/(X+2Q)$ by the Cauchy-Schwarz inequality. Interpret the ratio as zero when $X=0$. A second application of the Cauchy-Schwarz inequality, now to expectations, givesCounting ordered pairs of $r$-sets with $j$ common vertices, including identical sets when $j=r$, yieldsThe shared edges account for the factor $2^{\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. We claimHere are the estimates, including the large overlaps. For $2\le j\le \lfloor r/2\rfloor$, the probability that a random $r$-set contains any specified $j$ elements is at most $(r/(m-r){)}^j$. Summing over their choices inside the first $r$-set givesThe logarithm of $T_j$ is a convex function, a quadratic in $j$, so the maximum on this interval is at an endpoint. We have $T_2=O(r^4/m^2)$. As $r=(2+o(1)){\log }_{2}m$, the other endpoint satisfiesand is smaller than $T_2$ for sufficiently large $m$. Summing at most $r$ terms gives $O(r^5/m^2)$.

For the other half of the overlaps, write $j=r-s$, where $0\le s\le \lceil r/2\rceil$. The exact identity and an upper bound areThe quantity in parentheses is $m^{-1/2+o(1)}$, which tends to zero. The geometric series is thus at most $2/\mu$ for sufficiently large $m$. This proves the claim. In fact $r^5/m^2=o(m^{-9/5})$ and $1/\mu \le m^{-9/5}$, so eventuallyNow expose the $N=\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edge indicators one at a time. The edge-exposure martingale $M_i=\mathbb{E}[Z\mid \text{first }i\text{ indicators}]$ starts at $\mathbb{E}Z$ and ends at $Z$. Deleting one edge destroys at most one member of any edge-disjoint clique packing. Hence changing one indicator changes $Z$ by at most one; coupling the remaining indicators shows $|M_i-M_{i-1}|\le 1$.

Precisely, the Azuma-Hoeffding inequality says that if $(M_i{)}_{i=0}^N$ is a martingale and $|M_i-M_{i-1}|\le c_i$ almost surely for deterministic $c_i$, then, for $t>0$,If all $c_i=0$, the martingale is constant. Applying the lower-tail inequality with $c_i=1$ and $t=\mathbb{E}Z$ givesfor sufficiently large $m$. This is the only martingale concentration inequality needed.

Return to the original binomial random graph $G\sim G(n,1/2)$ and set $m=\lceil n/({\log }_{2}n{)}^2\rceil$. For each fixed $m$-element vertex set $U$, the complement graph of $G[U]$ has distribution $G(m,1/2)$. The union bound therefore givessince $m^{8/5}/n\to \infty$. Thus with high probability every vertex set of size at least $m$ contains an independent set of sizeApply greedy colouring by removing independent sets: remove such an independent set, give it a fresh colour, and repeat while at least $m$ vertices remain. Give each of the fewer than $m$ final vertices its own colour. This uses at mostcolours, since $m=o(n/{\log }_{2}n)$. Together with the lower bound, this gives the chromatic number of the half-density binomial random graph:

The graph Ramsey number $R(s,t)$ is the least $N$ for which every graph on $N$ vertices has a clique of size $s$ or an independent set of size $t$; $R(s)=R(s,s)$ is the diagonal Ramsey number. The base cases are $R(2,t)=t$ and $R(s,2)=s$.

Assume the smaller parameters already have finite graph Ramsey numbers, and take $N=R(s-1,t)+R(s,t-1)$. For any vertex, either its neighbourhood has at least $R(s-1,t)$ vertices, or its nonneighbourhood has at least $R(s,t-1)$ vertices. In the first case it contains an independent $t$-set, or an $(s-1)$-clique which extends with the chosen vertex. In the second it contains an $s$-clique, or a $(t-1)$-independent set which extends with that vertex. Induction proves existence and

Induction with Pascal's identity gives the binomial upper bound for a Ramsey number $R(s,t)\le \left(\genfrac{}{}{0ex}{}{s+t-2}{s-1}\right)$. Thus $R(s)\le \left(\genfrac{}{}{0ex}{}{2s-2}{s-1}\right)\le 4^{s-1}$, proving $R(s)=O(4^s)$.

For the lower bound, take a binomial random graph $G(n,1/2)$. The expected total number of $s$-cliques and independent $s$-sets isFor $n=\lfloor 2^{s/2}/2\rfloor$, this is at most $2^{1-s/2}/s!<1$ for all sufficiently large $s$. Some graph therefore has neither forbidden set, so $R(s)>n$. This proves $R(s)=\Omega (2^{s/2})$ by the probabilistic method.

The binomial upper bound for a Ramsey number gives $R(3,t)\le \left(\genfrac{}{}{0ex}{}{t+1}{2}\right)=O(t^2)$. For the triangle-free Ramsey lower bound by alteration, a binomial random graph $G(n,p)$ has expected triangle count $\left(\genfrac{}{}{0ex}{}{n}{3}\right)p^3$ and expected independent $t$-set count $\left(\genfrac{}{}{0ex}{}{n}{t}\right)(1-p{)}^{\left(\genfrac{}{}{0ex}{}{t}{2}\right)}$. Choose a realization whose sum of these counts is at most its expectation. Delete one vertex from each surviving forbidden set, iterating through the originally listed sets. The remaining graph has neither a triangle nor an independent $t$-set. This random alteration method provesFor large $t$, set $n=\lfloor (t/(4\log t){)}^{3/2}\rfloor$ and $p=n^{-2/3}$. The triangle term is at most $n/6$. Using $\left(\genfrac{}{}{0ex}{}{n}{t}\right)\le (en/t{)}^t$ and $1-p\le e^{-p}$, the logarithm of the independent-set term divided by $t$ is at mostwhich tends to $-\infty$. That term is eventually below $1$. Thus $R(3,t)>5n/6-1$ and

For a family $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$, let its lower shadow $\partial \mathcal{F}$ consist of all $(r-1)$-sets contained in members of $\mathcal{F}$. The local LYM inequality isTo prove it, use double counting on the pairs $(T,S)$ with $S\in \mathcal{F}$, $T\subset S$ and $|T|=r-1$. Each $S$ contributes $r$ pairs; each $T\in \partial \mathcal{F}$ contributes at most $n-r+1$. Hence $r|\mathcal{F}|\le (n-r+1)|\partial \mathcal{F}|$, exactly the displayed Local LYM inequality after using $r\left(\genfrac{}{}{0ex}{}{n}{r}\right)=(n-r+1)\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$.

To deduce the LYM inequality, start with an antichain $\mathcal{A}$ in the Boolean lattice and assign it weight ${\sum }_{S\in \mathcal{A}}{\left(\genfrac{}{}{0ex}{}{n}{|S|}\right)}^{-1}$. If its largest occupied rank is $r>0$, replace that whole rank by its lower shadow. The result remains an antichain: if an old lower-rank member were contained in a new shadow member, it would also be contained in an original rank-$r$ member, contradicting the original antichain property. Nor can a new member be contained in an old one, since every old member has size at most $r-1$ and equality would give the same contradiction. The Local LYM inequality shows that this replacement does not decrease the weight. Repeating eventually leaves an antichain on rank zero, whose weight is at most one. ThereforeFor the empty family the conclusion is immediate; the same argument includes the singleton family containing the empty set.

The antichains of maximum size are exactly the full middle levels. More precisely, for even $n$ only $\left(\genfrac{}{}{0ex}{}{[n]}{n/2}\right)$ attains the bound in Sperner theorem; for odd $n$ either $\left(\genfrac{}{}{0ex}{}{[n]}{(n-1)/2}\right)$ or $\left(\genfrac{}{}{0ex}{}{[n]}{(n+1)/2}\right)$ does. To prove that there are no others, put $M=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$. If $|\mathcal{A}|=M$, the LYM inequality and $\left(\genfrac{}{}{0ex}{}{n}{r}\right)\le M$ imply equality in every term's bound $1/\left(\genfrac{}{}{0ex}{}{n}{r}\right)\ge 1/M$. Thus every member lies on a middle level. For even $n$, there is only one such level, so it must be full.

For odd $n=2r+1$, let $X$ be the rank-$r$ members and $Y$ the rank-$(r+1)$ members. Consider the bipartite graph of inclusions between those levels. Both parts have size $M$, and the degree of a vertex is $r+1$. If $N(X)$ is the neighbourhood of $X$, double counting gives $|N(X)|\ge |X|$. Since the family is an antichain, $Y$ avoids $N(X)$; equality $|X|+|Y|=M$ forces $|N(X)|=|X|$ and $Y$ to be the full complement of $N(X)$. Equality in the degree count means that every edge into $N(X)$ comes from $X$, so there are no edges between $X\cup N(X)$ and its complement.

This inclusion graph is connected: any two $r$-sets can be joined by successively exchanging one element, and each exchange passes through their $(r+1)$-set union. Every upper vertex has a lower neighbour. Thus $X$ must be empty or the whole lower level, proving the classification. For $n=1$ the graph is just one edge, and for $n=0$ the unique maximum family is $\{\varnothing \}$. This establishes equality in Sperner theorem without assuming that equality in the LYM inequality alone always forces a middle level.

For the set-pair bound, choose a uniformly random permutation of $[n]$, and let $E_i$ be the event that every element of $A_i$ appears before every element of $B_i$. Since $A_i\cap B_i=\varnothing$, their relative order is uniform, andFor distinct $i,j$, choose $a\in A_i\cap B_j$ and $b\in A_j\cap B_i$. These are distinct because $A_i\cap B_i$ is empty. On $E_i$, $a$ precedes $b$; on $E_j$, $b$ precedes $a$. Thus the events are pairwise disjoint events, giving the Bollobas set-pairs inequalityThis Bollobas set-pairs inequality immediately gives another proof of the LYM inequality: enumerate the members $S_i$ of an antichain, and take $A_i=S_i$, $B_i=[n]\setminus S_i$. For $i\ne j$, incomparability means $S_i\setminus S_j\ne \varnothing$, while $A_i\cap B_i=\varnothing$. The set-pair hypotheses therefore hold, and $|A_i|+|B_i|=n$ makes the resulting sum exactly the LYM inequality.

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 Turan 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: