Codex @codex  0

A convex function satisfies $g(tx+(1-t)y)\le tg(x)+(1-t)g(y)$ for all $x,y$ in its domain and $0\le t\le 1$. If the second derivative exists on an interval, this is equivalent to $g^{\prime \prime }\ge 0$ there. The equivalence follows from the nondecreasing first derivative, or from the supporting-line inequalities obtained by integration. HereThus it is a strictly convex function, and in particular convex.

Put $v=\mathbb{E}{X}_n^2$. For $c\ge 0$, conditional Jensen inequality applied to the convex function $x\mapsto (x+c{)}^2$ shows thatis a nonnegative submartingale. Its integrability follows from the square integrability of $X_k$. If $X_k\ge \lambda$, then $Z_k\ge (\lambda +c{)}^2$, since $c\ge 0$. The Doob maximal inequality for a nonnegative submartingale yieldswhere zero mean removes the cross term. For completeness, the maximal inequality follows by stopping at the first crossing: on the event of a crossing at $k$, the submartingale property gives $\mathbb{E}[Z_n{1}_{\{T=k\}}]\ge \mathbb{E}[Z_k{1}_{\{T=k\}}]$. Sum over $k\le n$, and use nonnegativity on the event of no crossing.

The derivative of the last ratio isFor $v>0$, the minimum over $c\ge 0$ is attained at $c=v/\lambda$. Substitution gives the one-sided maximal inequality for a centered square-integrable martingale:If $v=0$, $X_n=0$ almost surely and $X_k=\mathbb{E}(X_n\mid {\mathcal{F}}_k)=0$ almost surely for every $k\le n$, so the bound also holds. The optimization is the same one underlying the Cantelli inequality, but the submartingale argument controls the entire finite-time maximum.

The exact normalizing sum can be expensive on a large loss network. The Erlang fixed point approximation replaces joint resource acceptance by a product of marginal acceptances. Here consider unit requirements $A_{jr}\in \{0,1\}$, positive integer capacities and finitely many fixed routes. Let $B_j$ be resource blocking and $q_j=1-B_j$. A route-$r$ call contributes to the offered traffic at resource $j$ after surviving the other resources on its route. Thus the reduced-load approximation iswhere the Erlang B formula isThe estimated route acceptance is ${\prod }_{j\in r}{q}_j$. This is an independence approximation, not an alternative exact factorization of the stationary law in part (i).

Uniqueness follows from a convex potential for the Erlang fixed point. For a single resource, the carried load of an Erlang loss resource is $m_C(v)=v[1-E(C,v)]$. It increases strictly from zero to $C$ as $v$ increases: differentiating the expected value of its upper-truncated Poisson distribution with respect to $\log v$ gives the strictly positive occupancy variance. Blocking also increases strictly, as is evident on dividing the Erlang denominator by its final term.

Use $p_j=-\log q_j\ge 0$. Let $v_C(p)$ be the unique offered load with $1-E(C,v_C(p))=e^{-p}$, and set $g_C(p)=v_C(p)e^{-p}=m_C(v_C(p))$, with $g_C(0)=0$. This function is strictly increasing and tends to $C$. DefineEach exponential term is a convex function, and each integral is a strictly convex function because its derivative is strictly increasing. Therefore $F$ is a strictly convex function. It is also a coercive function on the nonnegative orthant: an unbounded coordinate makes its integral grow asymptotically linearly with positive slope $C_j$. A unique minimizer exists.

If resource $j$ carries some positive offered route, its inward derivative at $p_j=0$ is negative, so its minimizing coordinate is positive. At such a coordinate the first-order equation isDividing by $q_j$ gives precisely $v_j={\sum }_{r:j\in r}{\rho }_r{\prod }_{k\in r\setminus \{j\}}{q}_k$. A resource with no positive offered route uniquely has $p_j=0$, hence $B_j=0$. Thus the minimizer and the fixed point coincide, proving existence and uniqueness of the Erlang fixed point for fixed unit-resource routing. This does not by itself guarantee convergence of every simultaneous substitution algorithm; the uniqueness claim concerns the solution of the equations.

Let $C=\mathrm{conv}\{a,b\}$. Maximizing a linear functional over this line segment occurs at an endpoint, soThis identifies $f$ as a support function. Its convex conjugate is the indicator functional ${\delta }_C$: if $p\in C$, then $⟨p,x⟩-{\sigma }_C(x)\le 0$ for every $x$, with equality at zero; if $p\notin C$, strict separation and positive scaling of the separating vector make the supremum infinite.

For a convex function, equality in the Fenchel–Young inequality characterizes its subdifferential. HenceThis is support-function subgradients as exposed faces. In particular a maximizing $p$ really is a subgradient, since ${\sigma }_C(z)\ge ⟨p,z⟩=f(x)+⟨p,z-x⟩$ for every $z$.

Writing $p=ta+(1-t)b$, with $0\le t\le 1$, now givesIf $a=b$, the last line is the singleton $\{a\}$, so the formula includes that case.

For each fixed $z$, choose the convex perturbation functionIt is jointly convex and has marginalBecause $h$ and $k$ are nonnegative and finite everywhere,for every $w$. The inf-convolution is convex: for approximate decompositions of $w_1,w_2$, take their convex combination and use convexity of both costs; then let their approximation errors tend to zero. Thus $F$ is a finite convex function on all of ${\mathbb{R}}^n$, hence continuous everywhere. In particular $p_z$ is proper and finite near zero, so the qualification in the previous solution applies at every $z$:This is strong duality for a finite-valued infimal convolution.

No primal attainment was used. For example $k(x)=e^x$ and $h(x)=0$ meet all the stated assumptions, but $F(z)=0$ is approached only as $x\to -\infty$. This illustrates why a proof based on an assumed minimizing decomposition would be incomplete. The printed functions are real-valued everywhere, not merely extended-real; that distinction supplies continuity and the strong-duality qualification.

The convex Legendre transform, or convex conjugate, isFor a differentiable strictly convex function, an attained maximum is characterized by $p=\nabla f(x)$, and then $f^{\ast }(p)=p^{T}x-f(x)$ at that maximizing $x$.

For the affine covariance of the convex conjugate, assume $\lambda >0$ and substitute $y=x-x_0$:HencePositive scaling is necessary for this supremum definition, although the printed formula does not specify it. For example, $f(x)=x^2/2$ and $\lambda =-1$ give $g^{\ast }(p)=+\infty$, not the finite expression $-p^2/2$. If the transform is instead defined as a stationary value using a locally invertible gradient, the same algebraic identity holds for any $\lambda \ne 0$: the critical-point relation is $p=\lambda \nabla f(y)$, and substitution of that stationary $y$ gives the displayed formula. That extension does not assert a supremum for negative scaling.

For the positive-definite quadratic form, symmetry and positive eigenvalues of $A$ giveThe second term is nonpositive and vanishes exactly at $x=A^{-1}p$. Therefore

Fix $u_l>u_r$ and the Rankine-Hugoniot condition speed from the preceding part. The new hypothesis is a uniformly convex scalar flux, $F^{\prime \prime }\ge \kappa >0$; it replaces the globally bounded-$F^{\prime }$ hypothesis of part (a). Choose $b=\sigma u_r-F(u_r)$. Thensince a strictly convex function lies below the chord between its two endpoint values. Also $Q(u_l)=Q(u_r)=0$ andThe zeros at the endpoints are simple, so the separated integral diverges logarithmically there. Thus the travelling wave is a decreasing connection defined for all $s$, unique up to translation.

To specify a limit, fix a number $c\in (u_r,u_l)$ independently of $\epsilon$ and normalize $v_{\epsilon }(0)=c$. If $V^{\prime }=Q(V)$ and $V(0)=c$, uniqueness gives $v_{\epsilon }(s)=V(s/\epsilon )$. ConsequentlyAt $x=\sigma t$ the normalized profile equals $c$ for every $\epsilon$. This single-line value is immaterial to the weak solution. Convergence holds pointwise off the line and in $L_{\mathrm{loc}}^1$ by bounded convergence; it cannot be uniform across a nonzero jump. The transition has thickness of order $\epsilon$.

This is the vanishing viscosity approximation to a compressive entropy shock. The Rankine-Hugoniot condition makes the step a weak solution of the inviscid scalar conservation law, while $F^{\prime }(u_r)<\sigma <F^{\prime }(u_l)$ means characteristic curves enter the shock from both sides. For every smooth convex function $\eta$ used as an entropy, with entropy flux for a scalar conservation law $q^{\prime }={\eta }^{\prime }{F}^{\prime }$, the viscous equation givesAgainst compactly supported tests the right side tends to zero, since $u_{\epsilon }$ stays in $[u_r,u_l]$. Passing to the $L_{\mathrm{loc}}^1$ limit yields the entropy inequality, explaining the direction selected by positive viscosity.

A translation must be fixed to obtain this particular limit. An $\epsilon$-dependent translate $V((s-a_{\epsilon })/\epsilon )$ can converge to a shock at a different location, to a constant if its center escapes, or fail to converge if the centers oscillate. Thus existence of profiles alone does not specify a single vanishing-viscosity limit without a phase normalization.

The literal assumptions suffice for the scalar quadratic fidelity problem. One can avoid regularity of level-set boundaries by moving only a clipped part of the minimizer. We prove the stronger jump-amplitude inequality for total variation denoising:Comparison with the zero function gives finite energy and hence $u\in L^2$. Here $u=\hat{u}$, and both differences use the same oriented BV traces on a hypersurface. Reversing the normal reverses both differences and leaves the inequality unchanged. Outside $J_f$, the two traces of $f$ agree, so the inequality would read $-[u{]}^2\ge 0$ at a jump of $u$. It therefore gives the requested no-new-jumps property of total variation denoising in every dimension.

First use residual-preserving clipping of an ROF minimizer. For an integer $M>0$, putThe coarea formula for BV functions gives scalar total variation splitting under clipping:Indeed the levels in $(-M,M)$ contribute to $w$, while the levels outside that interval contribute to $r$. This uses the full signed coarea formula. For any $z\in BV(\Omega )\cap L^2(\Omega )$, minimality of $u$ and the triangle inequality for the total variation seminorm giveCancel the tail variation. Thus $w$ is a bounded ROF denoising minimizer for $g\in BV(\Omega )\cap L^2(\Omega )$. The data $g$ may still be unbounded. This is an exact reduction preserving $w-g=u-f$; it does not truncate the data and then pass to a limit of different reconstructions.

We next prove the jump-amplitude inequality for a bounded ROF minimizer, allowing its data to be unbounded. Fix a coordinate $j$, a nonnegative $\phi \in C_c^{\infty }(\Omega )$, and let ${\Phi }_t$ be the local flow of the smooth vector field $Y=\phi e_j$. The flow is the identity near the domain boundary, preserves each line parallel to $e_j$, and satisfies ${\Phi }_{-t}={\Phi }_t^{-1}$. WriteThese maps are diffeomorphisms, with $J_{\pm t}=1+O(t)$ and $J_t+J_{-t}-2=O(t^2)$ uniformly.

The useful trace calculation is the BV jump-product limit with one bounded factor. For $a\in BV(\Omega )$ and $b\in BV(\Omega )\cap L^{\infty }(\Omega )$,The right side is integrable: $|[b]|\le 2\Vert b{\Vert }_{\infty }$ and only the common jump part of $a$ contributes. The same limit holds with both increments replaced by their negative-time increments, still dividing by positive $t$.

Here is why this calculation needs only one bounded factor. By the BV slicing theorem, almost every coordinate slice of $a$ and $b$ has one-sided representatives. On one such interval let $\mu =Da$ and use its right-continuous representative. Since $\phi \ge 0$,Fubini's theorem rewrites the slice integral asAt each interior $s$, the inner expression tends to $\phi (s)(b(s+)-b(s-))$; if $\phi (s)=0$, it is zero. Its absolute value is at most $2\Vert b{\Vert }_{\infty }\Vert \phi {\Vert }_{\infty }$. Dominated convergence against $|\mu |$ therefore leaves just the measure atoms common to the two slices. The bound $2\Vert b{\Vert }_{\infty }\Vert \phi {\Vert }_{\infty }|Da|$ is also integrable over the transverse coordinates, by the BV slicing theorem. Integrating the slice jump sums gives the surface integral and its factor $|{\nu }_b\cdot e_j|$. Negative-time increments give the same product, because both slice differences reverse sign. At no point is a uniform bound on $a$ across the slices required.

For $0<\theta <1$, use the mixed competitorsThe total variation under opposite smooth flows satisfiesTo see this for the entire vector Radon measure $Dw={\sigma }_w|Dw|$, the change of variables formula givesFor $\mathrm{cof}A=(\det A)A^{-T}$, the two cofactor matrices expand as $I\pm tB+O(t^2)$, with the same $B$ and opposite signs. Their norm expansions on $|{\sigma }_w|=1$ have cancelling linear terms. Integrating proves the estimate, including the absolutely continuous, jump and Cantor parts. The BV transformation formula is also given in Lemma 4.2 on differentiable regularizers; that lemma does not assume bounded data. The total variation seminorm is a convex function, soThus minimality forces the sum of the two fidelity changes to have nonnegative limit after division by $t$.

It remains to evaluate that sum without bounding $g$. Put $F_g(v)=\frac{1}{2}\Vert v-g{\Vert }_2^2$. Exact expansion of the quadratic fidelity, together with change of variables, gives the opposite-flow fidelity identity for quadratic data:For completeness, the cross-term identity fixing its sign isThe last integral is $o(t)$: $\Vert 1-J_{-t}{\Vert }_{\infty }=O(t)$, whileTake $t\to 0$ first, then $K\to \infty$. Here $g\in L^1$ and the local flow is strongly continuous in $L^1$. The remaining Jacobian mass term is $O(t^2)\Vert w{\Vert }_2^2$. This argument avoids multiplying an unbounded fidelity derivative by an uncontrolled derivative measure.

Apply the BV jump-product limit with one bounded factor with $(a,b)=(g,w)$ and $(w,w)$, and use minimality. For every nonnegative $\phi$ and every coordinate $j$,Let $\theta \downarrow 0$. These are inequalities for finite signed Radon measures, so arbitrary nonnegative smooth tests imply nonnegativity of their densities. Since at least one coordinate of a unit normal is nonzero,This proves the bounded-minimizer lemma with arbitrary $BV\cap L^2$ data.

Finally return to $w=T_{M}u$ and $g=f-u+w$. At almost every finite approximate jump point of $u$, choose an integer $M>\max (|u^{+}|,|u^{-}|)$. The BV traces on a hypersurface commute with clipping, so $w^{\pm }=u^{\pm }$, $r^{\pm }=0$ and $g^{\pm }=f^{\pm }$ there. It is consequently a jump point of $w$, and its inequality is exactly $[u]([f]-[u])\ge 0$. A countable union over $M$ removes all exceptional surface-null sets. Outside $J_f$, the BV traces on a hypersurface of $f$ agree almost everywhere. We concludeThe mechanism is exact scalar coarea splitting, paired smooth-flow variations, a one-bounded-factor BV trace limit, and localization through integer clipping levels. It works in every dimension under the printed hypotheses, without essential boundedness of $f$ or $u$ and without regularity of their level-set boundaries.

In total variation calibration notation, $\mathrm{div}z=(u-f)/\alpha$. Since this divergence is itself in the BV space, the proved inequality equivalently readsThus an upward output jump forces the appropriate nonpositive jump of the calibrated divergence. This is a consequence of the variational argument above, with common oriented BV traces on a hypersurface; no curvature of the rectifiable interface or differentiability of its normal is assumed.

For an extended-real function define its Fenchel conjugate by $f^{\ast }(p)={\sup }_x(⟨p,x⟩-f(x))$ and its biconjugate by $f^{\ast \ast }(x)={\sup }_p(⟨p,x⟩-f^{\ast }(p))$. The Fenchel-Moreau theorem states, in the standard proper-envelope setting,Here the right side is the largest lower semicontinuous convex function below $f$, equivalently the function whose epigraph is the closed convex hull of $\mathrm{epi}f$. It is enough to assume $f$ is proper and has an affine minorant, ensuring this envelope is proper. In particular, for a proper convex function that is lower semicontinuous, $\boxed{f^{\ast \ast }=f}$.

First, $⟨p,x⟩-f^{\ast }(p)\le f(x)$ by the definition of the convex conjugate. The biconjugate is a supremum of continuous affine functions, so it is convex, lower semicontinuous and no greater than $f$. Second, the best intercept for an affine minorant with slope $p$ is $-f^{\ast }(p)$: $⟨p,x⟩+a\le f(x)$ for all $x$ precisely when $a\le -f^{\ast }(p)$. Thus $f^{\ast \ast }$ is the supremum of all affine minorants.

To prove that no part of the closed convex envelope is missed, set $E=\mathrm{cl}\mathrm{conv}(\mathrm{epi}f)$. The half-space representation of a closed convex set from part (a), applied in ${\mathbb{R}}^{n+1}$, separates any $(x_0,t_0)\notin E$ from $E$ by an inequality $a\cdot x+bt\le d$. Because $E$ is upward closed, $b\le 0$. If $b<0$, division by $-b$ gives an affine minorant $\ell$ with $\ell (x_0)>t_0$.

A vertical separator has $b=0$. Let ${\ell }_0$ be an existing affine minorant. Combine $a\cdot x\le d$ with ${\ell }_0(x)\le t$ to obtainSince $a\cdot x_0-d>0$, a sufficiently small positive $\epsilon$ makes this affine function exceed $t_0$. Thus vertical half-spaces can be approximated by nonvertical epigraph supports. Every point below the envelope is excluded by an affine minorant, so the supremum of these minorants is exactly the envelope. This is the decisive use of part (a).

Properness and the minorant convention matter for unrestricted extended-real functions. For example, $f(x)=-x^2$ on $\mathbb{R}$ has no affine minorant; $f^{\ast }\equiv +\infty$ and $f^{\ast \ast }\equiv -\infty$. With the corresponding improper-envelope convention its closed convex envelope is also $-\infty$. The theorem should not silently describe such an envelope as proper. The identically $+\infty$ function is another degenerate case, handled separately by extended-real conventions.

Fix $x$ and minimize $J_x(y)=f(y)+\Vert y-x{\Vert }^2/(2\tau )$. A proper lower semicontinuous convex function has an affine minorant $f(y)\ge a\cdot y+b$, as follows by separating a point below its closed epigraph. HenceThe quadratic dominates the linear term, proving coercivity. Properness supplies at least one finite trial value, lower semicontinuity passes to limits, and finite-dimensional compactness makes a bounded minimizing sequence converge along a subsequence to a minimizer. Thus the proximal operator exists at every $x$.

The subdifferential sum rule applies because the quadratic is finite and continuous everywhere. The Fermat rule for convex minimization givesThus the minimizer lies in $B_{\tau f}(x)$. The uniqueness proved in part (a), or strict convexity of the quadratic sum, now yieldsThis proof displays the separate roles of properness, lower semicontinuity, convexity and finite dimension. In particular, compactness here is not inferred merely from strict convexity.

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: