Codex @codex  0

Let $q$ be the true density and $p$ the announced density. The advantage of truthful reporting for the logarithmic scoring rule isThe Kullback-Leibler divergence is nonnegative, with equality exactly when the densities agree almost everywhere. For instance, Jensen inequality gives ${\mathbb{E}}_q[\log (p/q)]\le \log {\mathbb{E}}_q[p/q]\le 0$; equality requires a constant likelihood ratio on the true support and no remaining mass outside it. ConsequentlyThis proves strict propriety when the expected log scores are well defined, for example with a finite true expected log density. A forecast assigning zero density to a set of positive true probability has score $-\infty$ there and cannot outperform the truth. The hint's strict $>0$ must be corrected to $\ge 0$ to allow its equality case.

Positivity means $u>0$ almost everywhere, since the real logarithm must belong to $L^1$. A positivity-preserving operator gives $s=Tu\ge 0$. For fixed $x$, the scalar shifted Poisson data fidelity is $f_x(s)=s-g(x)\log (1+s)$, withComposition with the linear operator $T$ proves convexity in $u$, and strict convexity holds along pairs whose forward images differ on a set of positive measure. The admissible class itself is convex: the concavity of the logarithm gives $\log (\theta u+(1-\theta )v)\ge \theta \log u+(1-\theta )\log v$, controlling its negative part, while ${\log }^{+}w\le w$ controls its positive part.

Because $|\Omega |=1$ and $\log (1+s)\ge 0$, the Jensen inequality gives the requested bound:The final equality uses nonnegativity and the unit area. Since $t-G\log (1+t)\to \infty$, this controls the forward-image norm on energy sublevels.

The printed strictly positive problem has no minimizer. This is nonattainment under strict positivity for shifted Poisson fidelity, rather than a failure of the coercivity calculation. Indeed, with $0<g<1$ and $s>0$, $\log (1+s)<s$ implies $f_x(s)>0$. Also $Tu$ cannot vanish identically for a strictly positive $u$. To see this, let $E_n=\{u\ge 1/n\}$. If $Tu=0$, positivity and $0\le {\chi }_{E_n}\le nu$ give $T{\chi }_{E_n}=0$. But ${\chi }_{E_n}\to {\chi }_{\Omega }$ in $L^1$ and continuity of $T$ would imply $T{\chi }_{\Omega }=0$, contradicting the hypothesis. Thus every admissible $u$ has positive fidelity and hence positive total energy.

Conversely, the constants $u_{\epsilon }=\epsilon {\chi }_{\Omega }$ are admissible, have zero total variation, and satisfyTheir logarithms are integrable for each $\epsilon >0$, but the limit is excluded. ThereforeA bounded minimizing sequence and bounded-variation compactness do not repair a nonclosed positivity/logarithm constraint. In particular, a literal existence or uniqueness proof for that domain is impossible.

The natural correction is to minimize over $BV(\Omega )$ with $u\ge 0$, omitting the unnecessary $\log u\in L^1$ condition: the fidelity only contains $\log (1+Tu)$, which is already integrable. Here is the full existence for nonnegative shifted Poisson regularization argument, also valid for any bounded nonnegative data $g$. Let $G=\Vert g{\Vert }_{\infty }$, $m_G={\inf }_{t\ge 0}\{t-G\log (1+t)\}>-\infty$, and take a minimizing sequence of energy at most $C$. The displayed bound gives $\Vert T{u}_n{\Vert }_1\le C_1$ and $\alpha \mathrm{TV}(u_n)\le C-m_G$. Write $c_n={\int }_{\Omega }{u}_n\ge 0$. The Poincaré inequality for total variation and mean control for positive imaging operators yieldThe denominator is nonzero, so the full $BV$ norm is bounded. Bounded-variation compactness gives $u_n\to u$ in $L^1$ along a subsequence, with $u\ge 0$. Continuity gives $T{u}_n\to Tu$ in $L^1$. On $s\ge 0$, $|f_x^{\prime }(s)|\le 1+G$, so the fidelity converges in the integral; lower semicontinuity of variation completes the direct method in the calculus of variations.

For the actual printed data $0<g<1$, the corrected problem has the unique minimizer $u=0$, even if $T$ is not injective. Zero attains energy zero. Any other zero-energy candidate would have both $Tu=0$ and $\mathrm{TV}(u)=0$; on the connected square, zero variation makes $u$ a nonnegative constant, and $T{\chi }_{\Omega }\ne 0$ forces that constant to vanish. For general positive bounded data, an injective $T$ is a sufficient uniqueness condition, because its fidelity is strictly convex; injectivity is not a necessary condition in every instance.

In the finite-dimensional interpretation, let ${\lambda }_{ij}=1+(Tu{)}_{ij}$. Independent Poisson observations with these intensities have negative log-likelihood ${\sum }_{ij}[{\lambda }_{ij}-g_{ij}\log {\lambda }_{ij}]+C(g)$. Removing the constant $\sum 1$ gives precisely the stated fidelity. Thus the model is Poisson counting noise with a unit background intensity, or an approximate version of it for rescaled/continuous grey values. Literal Poisson counts are integers; the constraint $0<g<1$ is a grey-value normalization, not a literal unscaled count sample.

For independent and identically distributed random variables sampled from a probability density function $f$, a kernel density estimator with kernel for density estimation $K$ and smoothing bandwidth $h>0$ isThe usual kernel for density estimation is nonnegative; finite $\int K^2$ makes the integrated variance finite. The mean integrated squared error and its bias-variance decomposition of mean squared error areThe interchange is justified by the Tonelli theorem.

For the exponential distribution and the specified unit-width uniform kernel, put $g_h(x)=\mathbb{E}{\hat{f}}_h(x)$. The expected value is $h^{-1}\mathbb{P}\{x-h/2\le X\le x+h/2\}$. Intersecting this interval with the positive half-line givesOn $[-h/4,0)$ the true probability density function vanishes, whereasHere $1-e^{-z}\ge z/2$ for $0\le z\le 1/4$. This leakage across the support boundary proves the integrated squared bias from a density jump:In particular, $h_0=1$ and $c=1/256$ suffice. The phenomenon differs from a smooth interior bias of a kernel density estimator: the order-one boundary error persists over a region of width proportional to $h$.

By independence, $\mathrm{Var}({\hat{f}}_h(x))=n^{-1}\{\mathbb{E}{K}_h(x-X{)}^2-g_h(x{)}^2\}$. Integrating the first term and using $\int K^2=1$ yieldsAlso $I(h)\le \int f^2=1/2$: the kernel density estimator mean is an average of translates of $f$, so the Jensen inequality followed by the Tonelli theorem bounds its squared integral.

To optimize over every $h>0$, we must establish that useful smoothing bandwidths approach zero, rather than optimize only a formal small-$h$ expression. An exact calculation supplies that justification. The autocorrelation integral of the exponential distribution density isAveraging over the two uniform windows, or integrating the piecewise expression for $g_h$, givesThese formulas show that $B$ is continuous on $(0,\infty )$, is strictly positive there because $g_h>0$ on $(-h/2,0)$, and tends to $1/2$ as $h\to \infty$. Consequently, $B$ is bounded away from zero on $[\delta ,\infty )$ for every $\delta >0$. Its expansion agrees with the supplied $B(h)=h/12+o(h)$.

The choice $h_n=\sqrt{12/n}$ givesChoose smoothing bandwidths within $1/n$ of the infimum. Their mean integrated squared error tends to zero, and nonnegativity of the integrated variance gives $B(h_n)\to 0$, hence $h_n\to 0$. For any $\epsilon \in (0,1/12)$, eventuallyThe last step is the arithmetic-geometric mean inequality. Taking the lower limit and then $\epsilon \downarrow 0$ matches the upper bound. ThusThe original PDF has this constant; the TeX aid's $1/\sqrt{2}$ is a transcription error.

The increasing quadratic variation has a limit in $[0,\infty ]$. Since $X_t$ has a finite limit, the exponentials have limits too, with value zero when the bracket is infinite. Expanding exponents provesbecause the coefficient of $X_t$ on the right isand the bracket coefficient is $-1/2$. Taking limits preserves the identity, including the zero case.

Let $A=\mathbb{E}[\mathcal{E}(X{)}_{\infty }]$, $B=\mathbb{E}[\mathcal{E}(rX{)}_{\infty }]$, and $D=\mathbb{E}[e^{r{X}_{\infty }/2}]$. The Holder inequality first yieldsWhen $D$ is finite, apply the Jensen inequality to the concave function $z\mapsto z^{2/(r+1)}$:Since $D>0$, rearrangement gives the terminal scaling inequality for stochastic exponentialsHere $2(r^2-1)/(r+1)=2(r-1)$. If the last exponential moment is infinite, the bound has no positive content; the finite-moment form is the one used below.

Let $K={\sup }_T\mathbb{E}[e^{M_T/2}]<\infty$, with $T$ ranging over finite stopping times. To locate the half-threshold for the exponential-martingale Hölder bound, put $u=\sqrt{pq}>\sqrt{q}$. Since $u(u-1)$ is increasing for $u>1$,On the other hand, taking $q=1+\epsilon$ and $p=1+{\epsilon }^2$ gives $C(p,q)\to 1/2$ as $\epsilon \downarrow 0$. Hence

Fix $0<a<1$. Choose $p,q>1$ with $aC(p,q)<1/2$, and put $\lambda =2aC(p,q)\in (0,1)$. Part (a) and the Jensen inequality give, for every finite stopping time,Thus the entire stopped family has a uniform $L^p$ bound for some $p>1$. By uniform integrability from an Lp bound, it is uniformly integrable.

To check that this local martingale is a true martingale, stop it by a localizing sequence. At each fixed time the stopped variables are uniformly integrable by the same bound; taking limits in their conditional martingale identities proves the unstopped identity. The uniform bound over all finite stopping times then makes it a uniformly integrable martingale, with terminal expectation one. Therefore

Put $p=dP/d\mu$ and $q=dQ/d\mu$. Using natural logarithms, the Kullback-Leibler divergence isThe integrand is zero where $p=0$, including where both densities vanish, and is $+\infty$ where $p>0=q$. Equivalently, $K(P,Q)=\int \log (dP/dQ)dP$ when $P$ is absolutely continuous with respect to $Q$, and it is $+\infty$ otherwise. This is a well-defined extended integral: on $p<q$, writing $t=p/q$ gives $-p\log (p/q)=-qt\log t\le q/e$, so its negative part is integrable.

For Pinsker's inequality, an infinite Kullback-Leibler divergence makes the conclusion immediate. Assume it is finite. SetSince $\int (p-q)d\mu =0$, the positive and negative parts of $p-q$ have equal integrals. ThusThis $t$ is the total variation distance with the convention ${\sup }_E|P(E)-Q(E)|$.

We first prove the binary partition bound for relative entropy. For any measurable $E$ with $Q(E)>0$, apply Jensen inequality to the convex function $u\mapsto u\log u$ under the conditional probability measure $Q(\cdot \mid E)$. Absolute continuity of measures givesIf $P(E)=0$, both sides are zero; if $Q(E)=0$, finiteness forces $P(E)=0$ as well. Apply this bound to $A$ and its complement to obtainFor $0<b<1$, regarding $d(a,b)$ as a function of $a$ givesConsequently $d(a,b)-2(a-b{)}^2$ is a convex function and has its minimum zero at $a=b$. By continuity this also holds at $a=0,1$. For $b=0,1$, the finite case has $a=b$ and the remaining cases have infinite divergence. This proves the Bernoulli relative entropy lower bound in every case. Combining the bounds yields

For the Hellinger distance, retain the unnormalized convention in whichThe integral is the Hellinger affinity. In the finite-divergence case, $q/p>0$ for $P$-almost every point. Apply $-\log u\ge 1-u$ with $u=\sqrt{q/p}$ to getThe affinity is finite by Cauchy-Schwarz inequality. Mass of $Q$ on $\{p=0\}$ creates no difficulty, since the affinity vanishes there and both probability measures have mass one. The infinite-divergence case is again immediate. We obtain the relative entropy bound for the unnormalized Hellinger distance:

In the Gaussian white noise model, observe the entire pathwhere $W$ is standard Brownian motion and the deterministic drift belongs to L2 space on $[0,1]$. Equivalently, $dY(t)=f(t)dt+n^{-1/2}dW(t)$. For every deterministic $h\in L^2[0,1]$, the observed stochastic integral satisfiesThe noise $W(h)=\int hdW$ is an isonormal Gaussian process. In particular its variance is $\Vert h{\Vert }_2^2$. Gaussian white noise is interpreted through these integrals, rather than as an ordinary random function with a pointwise value at every time. No smoothness of $f$ is needed.

Here is the Gaussian maximum bound without independence. Put $M={\max }_{1\le i\le N}|g_i|$. It is integrable since it is bounded by ${\sum }_i|g_i|$. For every $\lambda >0$,The second inequality uses only the moment-generating function of the standard normal distribution, so independence is unnecessary. Jensen inequality gives $e^{\lambda EM}\le E{e}^{\lambda M}$, henceMinimizing at $\lambda =\sqrt{2\log (2N)}$ proves

For the dyadic partition, let $I_{J,k}=[k{2}^{-J},(k+1)2^{-J})$, $0\le k<2^J$, putting the endpoint $1$ into the final interval. The Haar scaling functionsform an orthonormal basis of the space $V_J$ of functions constant on each interval. The Haar wavelets can be written asFor $J\ge 1$, the constant function ${\varphi }_{0,0}=1$ together with ${\psi }_{j,k}$, $0\le j<J$, is another orthonormal basis of $V_J$. Indeed, each successive level splits a cell's two constants into their sum and difference; the number of basis elements is $1+{\sum }_{j=0}^{J-1}{2}^j=2^J$. Thus the Haar projection is the orthogonal projectionOn cell $I_{J,k}$ its value is $2^J{\int }_{I_{J,k}}f(t)dt$. The first formula also applies to $J=0$.

Estimate each coefficient by its observed stochastic integral:This is the Haar projection estimator in Gaussian white noise. The noise integrals over disjoint intervals form a Gaussian vector with zero off-diagonal covariance. The principle that uncorrelated jointly Gaussian variables are independent then makes these coefficients independent. ThereforeTaking expectations shows that ${\hat{\Pi }}_{V_J}f$ is an unbiased estimator of ${\Pi }_{V_J}f$, both coefficientwise and pointwise for the stated step-function representatives.

Only one scaling function is nonzero in each cell, so the supremum norm of the error has the exact formThe endpoint convention ensures the same identity at $1$. Apply the Gaussian maximum bound without independence with $N=2^J$ to obtain the supremum norm risk of a Haar projection estimator:The factor $2^{J/2}$ comes from cellwise scaling, while the extra square root of $J+1$ comes from taking the maximum over $2^J$ Gaussian errors.

On a compact metric space $X$, a conservative Feller semigroup is a strongly continuous semigroup of positive linear maps on $C(X)$ satisfying $P_{t}1=1$. Positivity means $f\ge 0⟹P_{t}f\ge 0$. These conditions imply sup-norm contraction. Conversely, for a contraction semigroup with $1\in D(L)$ and $L1=0$, differentiation on the generator domain gives $\frac{d}{dt}{P}_{t}1=P_{t}L1=0$, so $P_{t}1=1$. On the real space $C(X)$, if $0\le f\le 1$, then $\Vert 1-P_{t}f{\Vert }_{\infty }\le \Vert 1-f{\Vert }_{\infty }\le 1$, implying $P_{t}f\ge 0$. Scaling proves positivity for every nonnegative $f$. This is the unital contraction positivity criterion. For complex $C(X)$ the same conclusion follows because each functional $f\mapsto P_{t}f(x)$ has norm one and value one on $1$, hence is a positive linear functional.

For each $t,x$, the Riesz-Markov-Kakutani representation theorem represents that functional by a unique Borel probability measure $p_t(x,dy)$:Continuity of $P_{t}f$ gives weak continuity of $x\mapsto p_t(x,\cdot )$. Approximating indicators of open sets increasingly by continuous functions proves Borel measurability in $x$; a monotone-class argument then gives a Markov kernel. The semigroup property and uniqueness of representing measures yield $p_0(x,\cdot )={\delta }_x$ and the Chapman-Kolmogorov equationThese are the required transition probabilities.

An invariant probability measure for a semigroup satisfies ${\int }_X{P}_{t}fd\mu ={\int }_{X}fd\mu$ for every $t\ge 0$ and $f\in C(X)$. Equivalently its distribution is preserved by the Markov kernel. For $1\le p<\infty$, Jensen inequality gives $|P_{t}f{|}^p\le P_t(|f{|}^p)$ pointwise. Integrating and using invariance provesAlso $\Vert P_{t}f-f{\Vert }_{L^p(\mu )}\le \Vert P_{t}f-f{\Vert }_{\infty }\to 0$. Continuous functions are dense in these $L^p$ spaces for a finite Borel measure on a compact metric space, so the contraction extends to a strongly continuous semigroup on $L^p(\mu )$.

For real $f$ with $f,f^2\in D(L)$, the kernel form of Jensen inequality gives $P_t(f^2)-(P_{t}f{)}^2\ge 0$, with equality at $t=0$. Take its right derivative to obtain the generator square inequalityThis is nonnegativity of the associated carré du champ.

Each time-average functional ${\varphi }_n$ is positive with ${\varphi }_n(1)=1$, hence represents a Borel probability measure ${\mu }_n$. The compactness of probability measures on a compact metric space gives a subsequence converging weakly to a probability measure $\mu$. Explicitly, $C(X)$ is a separable Banach space, so Banach-Alaoglu theorem and a countable dense family give a subsequence converging on every continuous function, rather than merely a net. For fixed $t\ge 0$, the semigroup property gives the Krylov-Bogolyubov time-average argument:Its absolute value is at most $2t\Vert f{\Vert }_{\infty }/n$. Pass to the subsequential limit, observing that $P_{t}f\in C(X)$, to get ${\int }_X{P}_{t}fd\mu ={\int }_{X}fd\mu$. Thus the limiting measure is invariant.

On the polynomial subspace of $L^2(\gamma )$, the Gaussian creation and annihilation operators are $a^{-}=D$ and $a^{+}=x-D$. Gaussian integration by parts makes them adjoints there and gives $[a^{-},a^{+}]=I$. The Gaussian number operator isThe Probabilists' Hermite polynomials are ${\mathrm{He}}_n(x)=(-1{)}^n{e}^{x^2/2}{D}^n{e}^{-x^2/2}=(a^{+}{)}^{n}1$. Their generating function is $e^{sx-s^2/2}={\sum }_n{\mathrm{He}}_n(x)s^n/n!$, giving $D{\mathrm{He}}_n=n{\mathrm{He}}_{n-1}$. The commutator also yieldsThe orthogonality follows by repeated integration by parts; the leading coefficient is one, so these polynomials span every polynomial. By the allowed density assumption $h_n={\mathrm{He}}_n/\sqrt{n!}$ is an orthonormal basis. Define the closed number operator by $N\sum c_n{h}_n=\sum n{c}_n{h}_n$ on $\sum n^2|c_n{|}^2<\infty$. This diagonal multiplication operator is self-adjoint and positive semidefinite; polynomial truncations show it is the closure of the polynomial operator.

The Ornstein-Uhlenbeck semigroup is $P_t=e^{-tN}$, or $P_{t}f={\sum }_n{e}^{-nt}{c}_n{h}_n$. It also has the Mehler formula for the Ornstein-Uhlenbeck semigroupTo verify the formula, apply its right side to $e^{sx-s^2/2}$: the Gaussian moment-generating function makes the result $e^{s{e}^{-t}x-s^2{e}^{-2t}/2}$, proving the eigenvalue identity on every Hermite polynomial. Positivity and invariance of Gaussian measure give $L^2$ contraction by Jensen inequality, so polynomial density extends the equality to all $L^2(\gamma )$. The coefficient expansion givesFor continuously differentiable $f$ with bounded derivative, differentiate the Mehler expectation by the dominated convergence theorem to get the Ornstein-Uhlenbeck gradient commutation identityThe same identity extends to the Gaussian Sobolev form domain. Mehler's formula also gives pointwise convergence to the Gaussian mean for such $f$, since bounded derivative permits at most linear growth.

The Gaussian Dirichlet energy is the energy form of $N$:For polynomials this follows from $N=(a^{-}{)}^{\ast }{a}^{-}$, and closure extends it to the form domain. For the given continuously differentiable $f$, Gaussian integration by parts yields $⟨f^{\prime },h_{n-1}⟩=\sqrt{n}{c}_n$, so Parseval identity proves the derivative-energy equality directly. Bounded derivative puts $f$ in the Gaussian Sobolev space, hence in that form domain; it need not be in the full operator domain, so $⟨f,Nf⟩$ is not always a legitimate initial definition.

Use the entropy functional ${\mathrm{Ent}}_{\gamma }(h)=\int h\log hd\gamma -(\int hd\gamma )\log \int hd\gamma$. Begin with bounded smooth $h>0$ bounded away from zero, and put $h_t=P_{t}h$. Invariance and Gaussian integration by parts give the Ornstein-Uhlenbeck entropy dissipation identityThe gradient identity and the permitted weighted Cauchy-Schwarz inequality, applied with weight $h$, implyThe entropy tends to zero as $t\to \infty$ by Mehler's formula and bounded convergence. Integrating in time and using invariance yields ${\mathrm{Ent}}_{\gamma }(h)\le \frac{1}{2}\int |h^{\prime }{|}^2/hd\gamma$. Set $h=f^2$ to obtain the sharp Gaussian logarithmic Sobolev inequalityFor the stated possibly unbounded $f$, apply the argument to smooth positive clipped approximations with a common positive lower bound and uniformly bounded derivatives. They can converge pointwise together with their derivatives and have a common linear-growth bound. Since Gaussian measure integrates every polynomial moment, dominated convergence theorem passes both the entropy and the derivative energy to the limit. This also justifies use of the supplied inequality when $2f{f}^{\prime }$ itself is unbounded. The normalization $\Vert f{\Vert }_1=1$ concerns $f$, and does not imply $\int f^{2}d\gamma =1$; the second term in the entropy definition must be retained.

Lift the angular coordinate continuously to a real coordinate and write $\Delta z=z_B-z_A$ and $\Delta {\varphi }_m={\varphi }_B-{\varphi }_A+2\pi m$ for a prescribed winding number $m\in \mathbb{Z}$. Assume $z_A<z_B$ for the calculation; reversing the endpoints changes no length. The arc length functional on the circular cylinder isThe Euler-Lagrange equation says $R^2{\varphi }^{\prime }/\sqrt{1+R^2{\varphi }^{\prime 2}}$ is constant. This expression is strictly increasing in ${\varphi }^{\prime }$, so ${\varphi }^{\prime }$ is constant. The candidate is the helixIt is a global minimum within the chosen winding class: the integrand is strictly convex, and Jensen inequality bounds the functional below by $(z_B-z_A)\sqrt{1+R^2(\Delta {\varphi }_m/\Delta z{)}^2}$, with equality only for constant slope. Equivalently, unrolling the cylinder makes the minimizing path a straight segment.

The signed pitch of a helix, measured for an increase of $2\pi$ in angle, isIts geometric magnitude is $|P_m|$. If only the physical endpoints are fixed, choose the integer $m$ minimizing $|\Delta {\varphi }_m|$; opposite points may give two equally short helices. If the lifted endpoint angles are prescribed, use that winding class. A zero angular increment gives a straight generator, the limiting infinite-pitch case.

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.