Codex @codex  0

For the Watts-Strogatz model, choose $n$ vertices on a ring, an even initial vertex degree $K<n$, and a rewiring probability $p$. Connect each vertex to its $K/2$ nearest neighbours on each side. Consider each original clockwise edge once: with probability $p$, retain its starting endpoint and replace its other endpoint uniformly, excluding self-loops and duplicate edges. The edge count remains $nK/2$, although individual vertex degrees change.

Increasing $n$ at fixed $K$ lengthens unrewired-ring graph distances. Increasing $K$ adds edges and shortens distances. Increasing $p$ introduces shortcuts, sharply reducing average shortest path length at first, then progressively reducing the clustering coefficient by destroying local triangles.

The small-world network regime occurs at intermediate $p$ with sufficient shortcuts, substantial clustering, and $K\ll n$. At $p=0$ distances are long; near $p=1$ the clustering advantage disappears. The degree distribution remains concentrated around $K$, so this is not a scale-free network.^[ref]

For the Erdős-Rényi model $G(n,p)$, choose the number $n$ of vertices and an edge probability $0\le p\le 1$. Visit every unordered pair of distinct vertices once and include its edge independently with probability $p$. This construction gives a simple graph with expected edge count $p\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and mean vertex degree $p(n-1)$.

Increasing $p$ at fixed $n$ makes the graph denser, increases typical vertex degree and local clustering coefficient, and tends to shorten graph distances and improve connectivity. Increasing $n$ at fixed $p$ also increases the mean vertex degree; to retain a sparse comparison one instead decreases $p$ approximately as $1/n$.

Its degree distribution is binomial distribution, approximately Poisson distribution in the sparse large-$n$ regime, so it is not a scale-free network. Connected realizations can have short average shortest path length, but their clustering coefficients are not elevated above the random baseline they themselves define. Thus they are not small-world networks under the high-clustering convention, although “small world” is sometimes used more loosely to mean only short distances.

Put $S={\sum }_{i=1}^N{x}_i$. Since the observations are independent random variables, their joint probability density function is a product. Therefore the likelihood function and log-likelihood areThese expressions assume positive observed values, as occurs with probability one under this continuous Erlang distribution.

This is the Nicholson-Bailey model for a host-parasitoid interaction with discrete generations. The factor $r$ is the host multiplication factor in the absence of parasitism; $a$ measures effective attack or searching intensity per parasitoid; and $b$ is the number of next-generation parasitoids produced per attacked host, with any survival or unit conversion absorbed into it.

If the number of attacks on a host has a Poisson distribution with expected value $a{P}_t$, then the probability of no attack is $e^{-a{P}_t}$. Consequently $e^{-a{P}_t}$ is the surviving, unparasitized host fraction, and $1-e^{-a{P}_t}$ is the attacked fraction. The two update equations count host descendants from surviving hosts and parasitoid descendants from attacked hosts, respectively.

The two colonies with no observed cheaters are right-censored after seven days. Each contributes $\mathrm{Pr}(X>7)=(1-p{)}^7$, not the probability of an event on day seven or eight. The four observed first events contribute four factors of $p$ and $(6-1)+(7-1)+(5-1)+(5-1)=19$ failures. Including the two censored exposures givesThe beta distribution prior therefore yieldsIts probability density function is proportional to $p^8(1-p{)}^{37}$ for $0<p<1$: it vanishes at both endpoints, is unimodal, and has its mode at $8/45\simeq 0.17778$. The right panel of the sketch in question 5(b) shows this moderately right-skewed density. The calculation assumes daily observations detect the first event and that stopping the experiment after seven days is independent censoring.

For a uniform random point in a disk, the event $R<x$ occupies a disk of area $\pi x^2$ when $0<x<1$. ThusThe radial probability density function is $f_R(r)=2r$ on $(0,1)$. Integrating givesChoose the polar angle $\Theta \in [0,2\pi )$. The Cartesian density is $1/\pi$ in the disk, and the polar coordinates Jacobian determinant is $r$. HenceThe product support and product density prove that $R$ and $\Theta$ are independent, with uniform angle.

Reflection symmetry gives $\mathbb{E}X=\mathbb{E}Y=0$ and $\mathbb{E}(XY)=0$, so $\mathrm{Cov}(X,Y)=0$. They are nevertheless not independent. The events $X>3/4$ and $Y>3/4$ each have positive probability, but their intersection is empty inside the disk, because it would require $X^2+Y^2>18/16>1$. Independence would give a positive product probability for that intersection.

Except at the probability-zero center, $X/R=\cos \Theta$ and $Y/R=\sin \Theta$. ThereforeAn arbitrary definition at the center does not change these expected values. This example distinguishes uncorrelated Cartesian coordinates from independent polar coordinates.

A loaded gun remains loaded after its visit with probability $1/2$. An unloaded gun is loaded and then not fired with probability $(3/4)(1/2)=3/8$. The visited gun's new loaded probability is thereforePreservation requires $p^{\prime }=p$, givingThis is product stationarity under single-coordinate Markov updates: the visited coordinate has the same Bernoulli distribution afterward, and its independent local random decisions do not affect the other coordinates. Thus the originally independent indicator random variables remain jointly independent after each scheduled visit, not merely equal in their marginal probabilities.

Let $X_j$ be the indicator random variable that gun $j$ is loaded. Then $N={\sum }_{j=1}^m{X}_j$ has binomial distribution with parameters $m,3/7$. By linearity of expectation and independence of the indicator random variables,

Fix any starting village and let $A$ be the pickup distance, $B$ the subsequent passenger distance. From each vertex, the four possible pickup distances are $0,5,10,15$, each with probability $1/4$. From each pickup village, the three other possible destinations have distances $5,10,15$, each with probability $1/3$.

Sharing the pickup village does not by itself give independence. Here it does hold because the conditional distribution of $B$ is the same for every pickup village: for all allowed $a,b$,Thus $D=A+B$ has the taxi distance convolution on a rectangular road cycle. Counting the twelve equally likely pairs givesNo other distances are possible. The probability distribution is the same for every starting village, so no assumption about the previous customer's destination is needed.

The separate moments are $\mathbb{E}A=15/2$, $\mathbb{E}B=10$, $\mathrm{Var}A=125/4$ and $\mathrm{Var}B=50/3$. Independence therefore givesAs a check from the displayed probability mass function, $\mathbb{E}{D}^2=2125/6$ and subtracting $(35/2{)}^2$ gives the same variance.

The side of the inscribed equilateral triangle has length $\sqrt{3}r$. If $d$ is the distance of a chord midpoint from the center, a right triangle gives chord length $2\sqrt{r^2-d^2}$. Thus a chord is sufficiently long exactly when $d<r/2$.

(a) Uniform midpoint area puts the midpoint in the radius-$r/2$ disk with probability(b) Fix the first endpoint by rotational symmetry. Independence and uniformity make the angle $\theta$ of the second endpoint uniform on $[0,2\pi )$. Its chord length is $2r\sin (\theta /2)$, so the required event is $2\pi /3<\theta <4\pi /3$. Hence(c) If the midpoint distance itself has uniform distribution on $[0,r]$, the event $d<r/2$ has probabilityThese are three different probability measures on chords. Their different answers are Bertrand's paradox: specifying what is uniform is indispensable. Uniform area, uniform endpoints and uniform radial distance are not interchangeable sampling rules. Equality at the length threshold has probability zero in all three models.

Use the equally likely release prior, and write $s$ for the probability that the guard names B when A is released. If B is released the guard cannot name B; if C is released the guard must name B. The law of total probability therefore givesA remains jailed and B is named precisely when C is released. Its probability is $1/3$, so the conditional probability isIn (a) unbiased naming has $s=1/2$, giving $2/3$: the guard's claim is false and A's chances have not improved. In (b) preferentially naming B has $s=1$, giving $1/2$: that naming rule makes the claim correct. In (c) preferentially naming C has $s=0$, giving $1$: naming B then reveals that C is the released person, so A certainly remains.

This is the three prisoners problem. The observed name includes information about how the guard selects a name; it is not merely the event that B remains. With general release priors ${\pi }_A,{\pi }_B,{\pi }_C$, the same calculation gives ${\pi }_C/(s{\pi }_A+{\pi }_C)$, making explicit where the equal-prior convention enters.

Let the win probabilities in games 1,2,3 be $u,v,w$. Independence makes a prescribed result pattern the product of its three win/loss probabilities. Taking a complement for event (a), inclusion-exclusion for overlapping pairs in (b) and (c), and disjoint exact-two patterns in (d) and (e), givesFor (b), a three-win outcome is counted three times in the pair sum and must be counted once, so subtract twice its probability. For (c), only the overlapping pairs 12 and 23 are allowed, so subtract the three-win intersection once. For (d), the two allowed exact patterns are 110 and 011. For (e), add 101 as well.

Substituting $(u,v,w)=(q,p,q)$ and $(p,q,p)$ gives the complete comparison:For (a) and (b), the differences $P_{MDM}-P_{DMD}$ are respectively $(p-q)(1-p)(1-q)>0$ and $(p-q)(p+q-2pq)>0$. For (c) and (d), the differences $P_{DMD}-P_{MDM}$ are $pq(p-q)>0$ and $2pq(p-q)>0$. For (e), $P_{MDM}-P_{DMD}=(p-q)(p+q-3pq)>0$ by the additional hypothesis. Thus all maximizing orders follow with strict inequalities.

For finite sets $A_1,\dots ,A_s$, the inclusion-exclusion principle statesTo prove it, count the contribution of an element lying in exactly $r\ge 1$ of the sets. Its total coefficient isby the binomial theorem. An element in none contributes zero. Summing these elementwise counts proves the formula. Applying the same argument to indicator functions and taking expectations proves the corresponding probability formula.

Factor $4199=13\cdot 17\cdot 19$. An integer is coprime to this product precisely when none of its three prime factors divides it. Inclusion-exclusion applied to the multiples of those prime numbers among $1,\dots ,4199$ gives Euler's totient functionFor the survey, let $H,D,S$ be the three detestation events and use proportions as probabilities. The union $H\cup D$ is the reported total union with the only-$S$ group removed, so $\mathbb{P}(H\cup D)=0.90-0.27=0.63$. The two-set inclusion-exclusion principle gives $\mathbb{P}(H\cap D)=0.45+0.28-0.63=0.10$. Removing the all-three group leavesThe required proportion is 4%. The separately reported total $S$ proportion is consistent with, but unnecessary for, this calculation.

Put $q=1-p=1/b$ and $L={\log }_{b}n$. For $s=\lceil 2L\rceil$, the expected number of independent $s$-sets isTaking logarithms gives $\log \mathbb{E}{X}_s\le -c_p\log n\log \log n$ for all sufficiently large $n$: the two quadratic-order terms cancel to within $O_p(\log n)$, leaving the negative term $-s\log s$. By the first moment method, with probability tending to one $\alpha (G)\le s-1<2L$. Hence

For the upper bound, an explicit greedy exposure rule suffices; the sharper factor two is not needed here. SetWhile at least $m_0$ vertices remain, construct a colour class by choosing a candidate, retaining its non-neighbours as candidates, and repeating for $r$ choices. Expose only edges incident to chosen vertices. They will all be removed with this colour class. By deferred edge exposure in greedy independent-set colouring, the remaining internal edges are still independent Bernoulli edges conditional on the history. This assertion depends on this particular rule; it is not true for an arbitrary adaptively selected remainder.

If $M_j$ candidates remain after $j$ choices, then conditionallyThe Chernoff bound gives, for $M_j\ge 1/\eta$,On the event that these lower bounds hold, a class started from $m\ge m_0$ hasIndeed $q^r\ge n^{-1}(\log n{)}^8$, while $(1-2/\log n{)}^r$ is bounded below by a positive constant depending on $p$. Thus each conditional failure probability is at most $\exp [-c_p(\log n{)}^4]$. A union bound over at most $nr$ candidate steps shows that all these classes can be formed with probability tending to one. Colour the final fewer than $m_0$ vertices individually. The number of colours is at mostTogether this provesThe failure estimates are summable in $n$. Thus they give both the usual asymptotically-almost-sure assertion and, on any common probability space carrying the sequence, eventual almost-sure validity by the first Borel-Cantelli lemma.

Use the random alteration method. Take arbitrarily large $n$ divisible by $2k$, and sample a binomial random graph with edge probability $p=n^{-1+1/(2g)}$. Let $Z$ count cycles of lengths $3,\dots ,g-1$. For each length $\ell$, its expected count is at most $(np{)}^{\ell }/(2\ell )$, soThe sum is empty if $g=3$. By the Markov inequality, $Z\le n/2$ with probability tending to one.

Set $s=n/(2k)$. The expected number of independent $s$-vertex sets isbecause the negative exponent has order $n^{1+1/(2g)}$, dominating the term of order $n$. Thus with probability tending to one there is no independent set of size $s$.

Choose a realization having both properties. Delete one vertex from each of its short cycles, using at most $Z$ deletions. The induced remaining graph $H$ has at least $n/2$ vertices and girth at least $g$. Deletion cannot create a new independent set, so $\alpha (H)\le s-1$. Every colour class is independent, givingIn particular a graph of the required girth and chromatic number exists. This proves graphs of arbitrarily high girth and chromatic number rather than invoking that existence theorem.

On an independent Bernoulli product measure, the Harris-Kleitman inequality states that increasing events $E,F$ obeyThe same holds for two decreasing events; an increasing and a decreasing event have the reversed inequality.

Prove the stronger function version by induction on the number of coordinates. For increasing bounded functions $f,g$, condition on the last coordinate $Z$, with $\mathrm{Pr}(Z=1)=p$. The law of total covariance givesThe first term is nonnegative by induction, and the other factors are nonnegative by monotonicity. The one-coordinate case is the same formula without the first term. Event indicators prove the assertion. Two decreasing functions follow by replacing both by their negatives; replacing only one gives negative correlation of increasing and decreasing events.

Here is a precise Janson inequality and its lower-tail concentration form. Let $I_i$ indicate containment of a specified set of independent Bernoulli coordinates, set $X={\sum }_i{I}_i$, $\mu =\mathbb{E}X$, and letThis Janson dependency sum is ordered and excludes the diagonal. ThenA zero denominator means the trivial case $X=0$ almost surely.

To prove the avoidance bound, expose the avoidance events in order. For a fixed $i$, separate earlier indices into those whose supports are disjoint from $S_i$ and those overlapping it. Write $C$ for avoidance of the first group and $D$ for avoidance of the second. The event $C$ is independent of $I_i$, while $C$ is decreasing and $\{I_i=I_j=1\}$ is increasing. The correlation inequality therefore givesThe first inequality divides a nonnegative numerator by $\mathrm{Pr}(D\mid C)\le 1$; the second uses a union bound and negative correlation with $C$. Conditioning events of zero probability already make full avoidance impossible. Multiply the resulting conditional avoidance bounds to obtain the Janson sequential product lemma. Taking logarithms and using $\log (1-u)\le -u$ gives $-\mu +\Delta /2$, since each unordered dependency pair is counted once in the sequential sum.

For the Janson lower-tail bound by independent thinning, attach independent selectors of probability $t$ to the events. Their total expectation and dependency sum are $t\mu ,t^2\Delta$, so avoidance of the selected events givesSet $t=1-e^{-s}$ and apply the exponential Markov bound to $e^{-sX}$. Using $s-s^2/2\le 1-e^{-s}\le s$ yieldsChoosing $s=a/(\mu +\Delta )$ proves the concentration assertion. For avoidance alone, optimizing $-t\mu +t^2\Delta /2$ also gives $e^{-{\mu }^2/(2\Delta )}$ when $\Delta \ge \mu$, and the original bound gives $e^{-\mu /2}$ when $\Delta \le \mu$.

To outline the sharp chromatic application, view an independent set of $G(n,p)$ as a clique of its complement, whose edge probability is $q=1-p$. Fix $0<\epsilon <1$, let $m=\lceil n/(\log n{)}^2\rceil$ and $r=\lfloor (2-\epsilon ){\log }_{b}n\rfloor$. For a particular $m$-vertex set, let $X$ count independent $r$-sets. Then $\mu =\left(\genfrac{}{}{0ex}{}{m}{r}\right)q^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$, and the overlap calculation givesOverlap of only one vertex shares no edge, hence is independent. For completeness, the summand is at most $(r^2/(m-r){)}^{\ell }{b}^{\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}/\ell !$. Since $r\le (2-\epsilon /2){\log }_{b}m$ eventually, large overlaps are bounded by $m^{-c_{\epsilon }\ell }$; finitely many smaller overlaps are dominated by $\ell =2$. Also $\log \mu ={\Omega }_{p,\epsilon }((\log m{)}^2)$, so the diagonal contribution $1/\mu$ is negligible. The concentration bound consequently givesA union bound over at most $2^n$ vertex sets still tends to zero. Thus independent sets in every large subset of a dense random graph are available uniformly, including adaptively obtained remainders. Repeatedly remove an independent $r$-set and give it a new colour, then colour the fewer than $m$ leftover vertices individually. This uses at most $n/r+m$ colours. Combining with the first-moment lower bound and letting fixed $\epsilon$ be arbitrarily small gives the accurate leading asymptoticThe uniform subset estimate, rather than merely the existence of one large independent set, is what makes the sharp upper bound possible.

The parameter relations give $\mu =\log (n/c)$ andFor each fixed integer $r\ge 1$, take an $r$-vertex set $S$ and let $X_S$ count triangles meeting $S$. The event that every vertex of $S$ is counted by $T$ is exactly $X_S=0$.

The number of such triangles isThus their total expected count is ${\mu }_S=N_S{p}^3=r\mu +O_r(n{p}^3)=r\mu +o(1)$.

Distinct triangles have dependent containment events only when they share an edge. If that common edge meets $S$, there are $O_r(n)$ choices for it and $O(n^2)$ choices for the two other vertices. If the common edge avoids $S$, both other vertices must lie in $S$, giving only $O_r(n^2)$ pairs. Each pair needs five edges. Consequently its ordered Janson dependency sum isJanson inequality gives the upper bound $\mathrm{Pr}(X_S=0)\le \exp (-{\mu }_S+{\Delta }_S/2)$. For the lower bound, the avoidance of each triangle is a decreasing event. Repeated application of Harris' inequality givesThe error $n^2{p}^6=O((\log n{)}^2/n^2)$ also tends to zero. The bounds match multiplicatively:Summing over ordered distinct vertices yields the factorial moments

Here is an explicit justification that these moments determine the limit. For every integer $t\ge 0$, the finite alternating sumsare upper bounds for $\mathrm{Pr}(T=t)$ when $L$ is even and lower bounds when $L$ is odd. This follows by applying the Bonferroni inequalities to $\left(\genfrac{}{}{0ex}{}{T}{t}\right){\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{T-t}{j})$; the full sum is precisely the indicator of $T=t$. First let $n\to \infty$ for a fixed truncation and use the factorial-moment limits. Then let the even and odd truncations grow. Both bounds tend toHence every point probability has the Poisson distribution limit, proving the Poisson threshold for vertices lying in no triangle:This is also the factorial-moment criterion for Poisson convergence, here justified rather than left as an unproved implication.

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 a submartingale $(Z_n)$ and $a<b$, let $U_N(a,b)$ count the completed upcrossings of $[a,b]$ by time $N$. The Doob upcrossing inequality givesFor a martingale $(X_n)$, a useful sharper form isHere $x^{+}=\max (x,0)$ and $x^{-}=\max (-x,0)$. To see the martingale form, use a bounded predictable process $H_k\in \{0,1\}$ that holds one unit after an observation at or below $a$ and releases it on the next observation at or above $b$. Its gain $G_N={\sum }_{k=1}^N{H}_k(X_k-X_{k-1})$ is at least $(b-a)U_N-(X_N-a{)}^{-}$: completed trades earn at least $b-a$, and any unfinished trade loses at most $(X_N-a{)}^{-}$. Since $\mathbb{E}{G}_N=0$, the bound follows. For the submartingale version, apply the same strategy to $(Z_n-a{)}^{+}$, itself a submartingale. Each purchase occurs at value zero, so its gain is at least $(b-a)U_N$. The complementary predictable strategy has nonnegative expected gain, bounding this strategy's expected gain by $\mathbb{E}(Z_N-a{)}^{+}-\mathbb{E}(Z_0-a{)}^{+}$, and in particular by the stated right side.