Codex @codex  0

Let $m$ be an integer median for the longest convex chain length of independent uniform points in a triangle. If $L_n(x)\ge a$, fix a certificate of $a$ coordinates. Every configuration with $L_n\le b$ must disagree with at least $a-b$ of those coordinates; equal weights $1/\sqrt{a}$ prove Talagrand convex distance separation at least $(a-b)/\sqrt{a}$. Talagrand's convex distance inequality then gives $\mathbb{P}(L_n\ge a)\mathbb{P}(L_n\le b)\le e^{-(a-b{)}^2/(4a)}$. Set $b=m$, then $a=m$, in the two respective applications to obtain the displayed tails for positive integer $t$. The exact chain-counting bound gives $m\le C{n}^{1/3}$. Hence any interval centred at $m$ with length $\omega (n)n^{1/6}$, where $\omega (n)\to \infty$, contains $L_n$ with high probability. No upper restriction on the growth of $\omega$ is required.

Use the independent product measure on the finite coordinate spaces. For $A\ne \varnothing$, let $V_A(x)$ be the convex hull of its mismatch vectors $(1_{x_i\ne y_i}{)}_{i=1}^n$, $y\in A$. The distance in the question equalsTo verify this, let $v_{\ast }$ be the nearest point. Any unit vector $\alpha$ satisfies ${\min }_{v\in V_A}\alpha \cdot v\le \alpha \cdot v_{\ast }\le \Vert v_{\ast }{\Vert }_2$. Conversely the projection property $v_{\ast }\cdot (v-v_{\ast })\ge 0$ gives equality for $\alpha =v_{\ast }/\Vert v_{\ast }{\Vert }_2$ when $v_{\ast }\ne 0$. If $v_{\ast }=0$, nonnegative weights give supremum zero. Linear functionals have the same minimum on the hull as on its original vectors, so this is exactly the quantified definition of the Talagrand convex distance.

We prove the stronger section induction for the Talagrand exponential moment,Zero-probability atoms may be discarded, replacing $A$ by its supported part: this preserves its probability and can only increase its distance. Thus assume all coordinate atoms have positive mass. The induction starts with zero coordinates, when a positive-probability event is the singleton space and its distance is zero.

Split the last coordinate into values $j$, with probabilities $q_j$, and write $A_j$ for the corresponding section in the first $n-1$ coordinates. Put $a_j=\mathrm{Pr}(A_j)$, choose a largest section $A_s$ of probability $a>0$, and set $r_j=a_j/a\in [0,1]$. For a point $(x^{\prime },j)$, mix nearest mismatch vectors from $A_j$ and $A_s$ with weights $\lambda ,1-\lambda$. Their final coordinates are zero and, if $j\ne s$, one. Convexity of the squared norm givesFor an empty $A_j$, use $\lambda =0$ directly. If $j=s$, the final-coordinate term is an unnecessary nonnegative allowance, so the bound still holds.

Exponentiate, integrate in $x^{\prime }$, and use Hölder's inequality and the induction hypothesis. For $r_j>0$ this givesWe supply the scalar estimate for Talagrand product induction used in the last step. Set $L=-\log r$. For $0\le L\le 1/2$, choose $1-\lambda =2L$, making the expression $e^{L-L^2}$. The functionhas $h(0)=h^{\prime }(0)=0$ andThus $e^{L-L^2}\le 2-e^{-L}$. For $L\ge 1/2$, choose $\lambda =0$, giving $e^{1/4}$; the already proved boundary case and monotonicity of $2-e^{-L}$ give the same bound. For $r=0$, the direct empty-section bound is $e^{1/4}/a\le 2/a$.

Now average over $j$. With $m={\sum }_j{q}_j{r}_j=\mathrm{Pr}(A)/a\in (0,1]$, the exponential integral is at most $(2-m)/a$. Since $m(2-m)\le 1$, this is at most $1/(am)=1/\mathrm{Pr}(A)$, closing the induction.

Finally apply the Markov inequality to the nonnegative exponential. For the distance-tail event ${\overline{A}}_t$,This proves Talagrand's convex distance inequality for the finite product. If $\mathrm{Pr}(A)=0$, the required probability-product inequality is immediate, including the empty-event case with distance defined as infinity; no finite exponential-moment assertion is needed there.

Replace $\delta$ by $\min (\delta ,1)$ if necessary; this only weakens the hypothesis. We prove the result for finite graphs using a random proper partial graph coloring, then a deterministic completion. All constants below may depend on this fixed positive $\delta$.

First record the extension of a partial colouring by neighbour-colour savings. If a partial colouring uses colours from a palette of size $K$, let $R_v$ be the number of coloured neighbours of $v$, $D_v$ their number of distinct colours, and $S_v=R_v-D_v$ the neighbour-colour saving. There are $K-D_v$ available colours and $d(v)-R_v$ uncoloured neighbours. Thusat every vertex suffices for greedy completion: each subsequently coloured neighbour removes at most one available colour while reducing the uncoloured-neighbour count by one.

Call $v$ high-degree if $d(v)\ge (1-\delta /8)\Delta$. Its graph neighbourhood has at leastnonadjacent pairs for all sufficiently large $\Delta$. Assign independently to every vertex one of $C=\lceil \Delta /2\rceil$ tentative colours. Erase the colour of every vertex having a neighbour with the same tentative colour. The remaining colouring is proper; erasure is based on the original assignments and is not an iterative cascade.

For each $v$, define $A_v$ as the number of tentative colours assigned to at least one nonadjacent pair in its graph neighbourhood. Let $B_v$ count those same colours for which at least one neighbour of $v$ loses its colour. Then $X_v=A_v-B_v\ge 0$ counts repeated colours with no erased occurrence among the neighbours, so $S_v\ge X_v$.

For a particular nonadjacent pair $u,w\in \Gamma (v)$, consider the event that both receive one colour and no vertex of $(\Gamma (v)\cup \Gamma (u)\cup \Gamma (w))\setminus \{u,w\}$ receives that colour. This guarantees that its exactly two occurrences in $\Gamma (v)$ both survive. Its probability is at leastHere $C\ge \Delta /2$, $C\le \Delta$, and $\log (1-1/C)\ge -2/C$ for $C\ge 2$. Different pairs cannot be counted by the same colour in this event, since each event specifies exactly two occurrences in the graph neighbourhood. Thereforefor every high-degree vertex. This is the expected colour savings from sparse neighbourhoods.

We need simultaneous concentration, not just a positive expectation. A single tentative-colour change can affect $A_v$ or $B_v$ only in the old and new colour categories, so each function changes by at most two. A witness for $A_v\ge s$ fixes two vertices for each of $s$ colours. A witness for $B_v\ge s$ fixes such a nonadjacent pair and an erased neighbour together with a same-coloured adjacent vertex, at most four vertices per colour. Thus both are certifiable functions with Lipschitz constant $2$ and certificate parameter at most $4$. Both are bounded by $C\le \Delta$.

To see exactly what concentration follows, let an integer-valued $Z$ change by at most $L$ per coordinate and have certificates of size at most $rb$. For an input with $Z\ge b$, fix such a certificate $J$. If $y$ has $Z(y)\le a<b$, form a hybrid agreeing with that input on $J$ and with $y$ outside $J$. The hybrid has value at least $b$, so at least $(b-a)/L$ certificate positions differ from $y$. Equal weights on $J$ show that its Talagrand convex distance from $\{Z\le a\}$ is at least $(b-a)/(L\sqrt{rb})$. Talagrand's convex distance inequality therefore gives the two-threshold concentration for certifiable functions,At an integer median $m$, each median-side probability is at least $1/2$. Taking thresholds $m-t,m$ or $m,m+t$ and using $0\le Z\le \Delta$ givesfor $L=2,r=4$. Summing these tails gives $|\mathbb{E}Z-m|=O(\sqrt{\Delta })$. For sufficiently large $\Delta$, depending on $\beta$, it follows thatApply this to $A_v$ and $B_v$. Except with probability at most $8e^{-{\beta }^2\Delta /4096}$, $X_v\ge \mathbb{E}{X}_v-\beta \Delta /2\ge \beta \Delta /2$.

A bad event at $v$ depends only on tentative colours at distance at most two. It is independent of the entire collection of bad events at distance greater than four. Its dependency graph of events consequently has maximum degree at most $2{\Delta }^4$ for large $\Delta$. The Lovász local lemma now makes all high-degree vertices good simultaneously: exponential decay beats this polynomial dependency bound.

The needed local-lemma step can be checked directly. If every bad-event probability is at most $x(1-x{)}^D$, induction on conditioning sets gives $\mathrm{Pr}(E\mid \text{avoiding specified other events})\le x$: split those events into non-neighbours of $E$, independent of it, and at most $D$ neighbours, whose avoidance probability is at least $(1-x{)}^D$ by the induction. Multiplying the resulting conditional avoidance probabilities makes total avoidance positive. Taking $x=1/(D+1)$ works whenever $ep(D+1)\le 1$, since $(1-1/(D+1){)}^D\ge e^{-1}$. Our bound satisfies this criterion once $\Delta \ge {\Delta }_0(\delta )$.

Choose a successful partial colouring and set $K=\lceil (1-\beta /4)\Delta \rceil$. This contains the original palette. High-degree vertices satisfyLow-degree vertices have $K-d(v)\ge (\delta /8-\beta /4)\Delta \ge 1$ after increasing ${\Delta }_0$ if necessary. Greedy completion therefore gives $\chi (H)\le K$. Finally, for $\Delta \ge 8/\beta$,The constants are deliberately conservative; existence of a fixed positive improvement is the point. The same proof uses an external maximum degree bound, so if infinite locally finite graphs are allowed, every finite subgraph has this uniform colouring bound and compactness extends the colouring to the whole graph.

For the stronger triangle-free result, the appropriate brief route is semi-random palette refinement for triangle-free colouring. Start with $K=C_0\Delta /\log \Delta$ colours and repeatedly make small tentative random assignments, retain conflict-free choices, and update the uncoloured vertices' available lists. Triangle-freeness makes each graph neighbourhood independent. Track list size and average residual neighbour congestion per colour, prune unusually congested colours, and use concentration inequalities and the Lovász local lemma to preserve these invariants through the rounds. The ratio of residual congestion to list size decreases until a final completion using the Lovász local lemma or greedy coloring succeeds. Average control and pruning are important: four-cycles are allowed, so assuming tight uniform concentration for every individual colour load would be unjustified. With a sufficiently large absolute $C_0$, this programme gives $\chi (H)=O(\Delta /\log \Delta )$. The one-round fixed-fraction saving proved above alone does not establish that logarithmic improvement.

To show the order is best possible, let $d\to \infty$ through integers and sample $G(n,d/n)$ with $n=d^7$. A Chernoff bound and union bound give maximum degree at most $2d$ with probability tending to one. The expected triangle count is at most $d^3/6=o(n)$, so fewer than $n/2$ vertices need be deleted to remove all triangles with high probability. For $s=\lceil 4n\log d/d\rceil$, the expected number of independent $s$-sets is at mostits logarithm is at most $s[\log (ed/(4\log d))-2\log d+o(1)]$, which tends to minus infinity. The altered triangle-free graph thus has at least $n/2$ vertices and independence number below $s$, giving $\chi \ge (c+o(1))d/\log d$ for an absolute positive $c$. Append a disjoint star graph whose centre has vertex degree $2d$ if needed to make its maximum degree exactly $\Delta =2d$. This proves the triangle-free chromatic lower bound at bounded maximum degree, $\chi =\Omega (\Delta /\log \Delta )$, so the preceding order cannot be improved in general.

For $x\in \Omega$ and nonempty $A$, letThe Talagrand convex distance isEquivalently,For completeness, let $v_{\ast }$ be a closest point of the finite convex hull to zero. If $v_{\ast }\ne 0$, minimality gives $v_{\ast }\cdot (v-v_{\ast })\ge 0$ for every $v\in V$. Taking $\alpha =v_{\ast }/\Vert v_{\ast }\Vert$ proves that the supremum is at least $\Vert v_{\ast }\Vert$. Conversely each permitted $\alpha$ has ${\inf }_{v\in V}\alpha \cdot v\le \alpha \cdot v_{\ast }\le \Vert v_{\ast }\Vert$ by Cauchy-Schwarz. The weights are nonnegative because the hull has nonnegative coordinates. If $v_{\ast }=0$, both sides are zero. This proves the dual definition used below.

We prove Talagrand's convex distance inequality by induction on the number of factors. Write $\Omega ={\Omega }^{\prime }\times X_n$, with measure $\mu \otimes \nu$, and $F_A=d_T(\cdot ,A{)}^2$. For a last-coordinate value $z$, let $A_z=\{y^{\prime }:(y^{\prime },z)\in A\}$. Choose a section $B=A_b$ of largest probability $m=\mu (B)>0$, and put $a_z=\mu (A_z)/m\in [0,1]$. The total event probability is $p=\mathrm{Pr}(A)=m{\sum }_z\nu (z)a_z$.

If $A_z$ has positive probability, combine mismatch vectors from $A_z$ and from $B$. A weight $t$ on the second section contributes at most $t$ in the last coordinate. Convexity of the squared Euclidean norm gives, for every $0\le t\le 1$,The last-coordinate contribution is actually zero if $z=b$, so the displayed upper bound remains valid. Hölder's inequality and the induction hypothesis yieldFor a zero-probability section use $t=1$ directly, so no division by zero or exponent of an infinite quantity is needed.

The scalar estimate for Talagrand product induction isHere is its proof. For $a>0$ set $L=-\log a$. If $L\le 1/2$, take $t=2L$; the logarithm of the left expression is $L-L^2$. Put $h(L)=\log (2-e^{-L})-L+L^2$. Then $h(0)=h^{\prime }(0)=0$ andsince $(2u-1{)}^2-u=(4u-1)(u-1)\ge 0$ for $u=e^L\ge 1$. Thus $h\ge 0$. If $L\ge 1/2$, choose $t=1$. The already proved boundary case gives $e^{1/4}\le 2-e^{-1/2}\le 2-a$. The same direct choice covers $a=0$.

Average the resulting section bounds over $z$:where the last inequality is equivalent to $(m-p{)}^2\ge 0$. The induction starts on the zero-coordinate singleton, where every positive-probability event is the whole space and the moment is one. HenceWe assume $\mathrm{Pr}(A)>0$; a zero-probability event has no finite right-hand bound to prove. Markov's inequality also gives

For the subsequence application, let $L(x)$ be the longest increasing subsequence length for independent sequence coordinates. A witness of length $\ell$ uses only $\ell$ positions. If $L(x)=\ell \ge b$ and $y$ satisfies $L(y)\le a<b$, at least $\ell -a$ witness positions must change: all unchanged witness positions remain in increasing order. Put weights $1/\sqrt{\ell }$ on the witness and zero elsewhere. The dual distance definition giveswhere the latter expression increases with $\ell$ for $a\ge 0$. Therefore the increasing-subsequence certificate concentration bound isIf the lower event has probability zero the conclusion is immediate.

Let $m$ be an integer median, so $\mathrm{Pr}(L\le m),\mathrm{Pr}(L\ge m)\ge 1/2$. Taking the two thresholds in the bound gives, for $t>0$,For $t>m$ the lower event is empty. In a nonempty sequence $m\ge 1$. Integration of these tails gives an explicit mean-median estimate: use $m+t\le 2m$ for $t\le m$ and $m+t\le 2t$ for $t\ge m$, obtainingWriting $\mu =\mathbb{E}L$, the median property also gives $m\le 2\mu$. Consequently, for a universal constant $C$, all $u\ge 0$ satisfyThus the subsequence length is concentrated near its mean on the scale $\sqrt{\mu }$, rather than the generic coordinate-exposure scale $\sqrt{n}$. This argument applies directly to finite-valued independent sequences. Independent continuous samples follow by refining finite coordinate discretizations; the strict-order pattern stabilizes almost surely when ties have probability zero. A uniform random permutation is the rank sequence of independent continuous samples, so it has the same subsequence-length concentration. Arbitrarily dependent random sequences are not covered by the product-space assumption.

We use the directed set version of the Talagrand convex distance:Here a coordinate is an entire sampled point, so $x_i\ne y_i$ means the two planar points differ. This is the distance from the upper event $A$ to the lower event $B$; its order is relevant because the convex distance need not be symmetric.

Fix $x\in A$ and choose exactly $a$ indices $I$ whose points form a convex chain with the endpoints. Such a choice exists even if $L_n(x)>a$, by taking a subchain. It is a certificate of the certifiable function $L_n$. For any $y\in B$, let $J=\{i\in I:x_i\ne y_i\}$. The $a-|J|$ unchanged selected points remain a convex chain in configuration $y$, soChoose the nonnegative weights ${\alpha }_i=a^{-1/2}$ for $i\in I$ and zero otherwise. They have squared sum one, and for every $y\in B$,Taking the infimum over $y$, then the supremum over weights, and finally the infimum over $x\in A$ provesThis proof also works for $b=0$ if zero-length chains are admitted, and gives the usual infinite separation when one of the events is empty. For the uniform sampling model, $L_n\ge 1$ almost surely when $n\ge 1$.

The useful form is Talagrand's convex distance inequality. Let $({\Omega }_i,{\mu }_i)$ be standard probability spaces, let $\Omega ={\prod }_{i=1}^n{\Omega }_i$ carry the product measure $\mu ={⨂}_i{\mu }_i$, and let $A\subset \Omega$ be a measurable event with $\mu (A)>0$. For $x\in \Omega$, form the mismatch vectorsThe Talagrand convex distance is the distance from zero to their closed convex hull:Equivalently, by the Hahn-Banach separation theorem for two convex sets,Nonnegative weights suffice because every mismatch vector has nonnegative coordinates. Talagrand's convex distance inequality statesIn particular, Markov's inequality gives the product-space concentration inequalityThe same conclusion is interpreted with outer probabilities if a distance set is not measurable; the continuous geometric function used below has measurable level sets. A median $M$ of a real random variable $Z$ means that $\mathbb{P}(Z\le M)\ge 1/2$ and $\mathbb{P}(Z\ge M)\ge 1/2$. Applying the displayed concentration inequality to suitable level sets will control deviations around a median.

For $a\in [0,1]$,where the endpoint $t=1$ is used directly if $a=0$. Put $L=-\log a$. For $L\le 1/2$, choose $t=2L$ and set $h(L)=\log (2-e^{-L})-L+L^2$. Then $h(0)=h^{\prime }(0)=0$ and $h^{\prime \prime }(L)=2-2e^L/(2e^L-1{)}^2\ge 0$, proving the bound. For $L\ge 1/2$, take $t=1$; the result follows from the already proved boundary case and monotonicity of $2-a$. This estimate closes the section-by-section induction for the exponential Talagrand convex distance moment.

On a finite product of standard probability spaces, for any measurable event $A$ of positive probability,Consequently $\mathbb{P}(A)\mathbb{P}(d_T(X,A)\ge s)\le e^{-s^2/4}$. Here $d_T$ is the Talagrand convex distance. The distance-event conclusion can be read with outer probability when necessary.

Suppose an integer-valued certifiable function is $L$-Lipschitz under one-coordinate changes and a value at least $b$ has a certificate of at most $rb$ coordinates. Any input with value at most $a<b$ must differ on at least $(b-a)/L$ certificate positions. Equal weights on those positions bound its Talagrand convex distance from the low-value event. Applying Talagrand's convex distance inequality gives the displayed product bound. For $0\le Z\le D$, median tails integrate to $|\mathbb{E}Z-\mathrm{med}Z|=O(L\sqrt{rD})$, and deviations of order $D$ have exponentially small probability.