Codex @codex  0

Equip the symmetric group $S_n$ with its uniform probability measure and unnormalized Hamming distance. If $f$ has Lipschitz constant $K$, it obeys the displayed two-sided bound, and each one-sided tail has the same exponential without the factor two. Reveal a uniform permutation one image at a time. Two possible next images have completion sets paired by swapping those two values, changing exactly two coordinates. Thus the corresponding conditional means differ by at most $2K$. Each increment of the Doob exposure martingale has conditional range length at most $2K$. Applying the conditional Hoeffding lemma gives $\mathbb{E}{e}^{\lambda (f-\mathbb{E}f)}\le e^{n{\lambda }^2{K}^2/2}$; optimizing the exponential Markov bound proves the bound. A mere absolute-increment bound of $2K$ gives a weaker constant, so using the range length matters.

Expose the independent coordinates in order and let $M_i=\mathbb{E}[f\mid X_1,\dots ,X_i]$, $M_0=\mathbb{E}f$. This is the Doob exposure martingale. For fixed earlier coordinates, write $h_i(x)=\mathbb{E}[f\mid X_i=x,\text{earlier coordinates}]$. The remaining coordinates have the same distribution for all $x$, and the coordinate-change hypothesis gives $|h_i(x)-h_i(y)|\le c_i$. Thus the conditional range of $M_i-M_{i-1}$ has length at most $c_i$, and its conditional mean is zero.

Here is the Hoeffding lemma needed for the sharp constant. If a mean-zero random variable $Y$ lies in an interval of length $c$, set $\psi (s)=\log \mathbb{E}{e}^{sY}$. Its second derivative is the variance under the exponentially tilted law. Under any such law, variance is at most $c^2/4$, by comparison with squared distance from the interval midpoint. Since $\psi (0)={\psi }^{\prime }(0)=0$, integration gives $\psi (s)\le s^2{c}^2/8$ for all real $s$. Applying this conditionally and iterating the tower property yieldsThe exponential Markov bound now givesFor $C>0$ choose $s=4t/C$. Apply the same argument to $-f$ and add the two tails, proving the McDiarmid inequalityFor $C=0$, $f$ is constant almost surely, and every positive-deviation probability is zero.

For the neighbourhood application, the ambient points must be elements of $\mathcal{P}[n]$, equivalently binary strings; the printed $y\in [n]$ is a type error. An $n$-element ambient set could not generally satisfy the stated exponential-size lower bound. Use the uniform product probability space on the Boolean cube and set $F(y)=d(y,A)$. Flipping one coordinate changes this Hamming distance by at most one, so $C=n$. Put $\mu =\mathbb{E}F$. Since $\mathrm{Pr}(F=0)=|A|/2^n\ge \epsilon$, the proved two-sided inequality gives, for $\mu >0$,Consequently $\mu \le \sqrt{(n/2)\log (2/\epsilon )}=t/2$; the same bound is immediate if $\mu =0$. ThereforeThis proves the Boolean cube expansion from bounded differences:The meaningful range is $0<\epsilon \le 1$; real radii are interpreted by the inequality on the integer-valued Hamming distance. The converted TeX's final $2^{2n}$ is another corruption: the original PDF has $2^n$.

Use the uniform probability measure on the symmetric group $S_n$ and the unnormalized Hamming distanceLet $f:S_n\to \mathbb{R}$ have Lipschitz constant $K>0$ for this distance. We will prove the one-sided concentration inequalitiesConsequently $\mathbb{P}(|f-\mathbb{E}f|\ge t)\le 2e^{-t^2/(2n{K}^2)}$ for $t>0$. A zero Lipschitz constant makes $f$ constant, so that case is immediate.

Let $\sigma$ be a uniform permutation, reveal $\sigma (1),\dots ,\sigma (k)$ successively, and define the Doob exposure martingaleFix the first $k-1$ images. For an available value $a$, let $h(a)$ be the conditional mean when $\sigma (k)=a$. Given two available values $a,b$, left-composition with the transposition exchanging $a,b$ is a bijection from completions with next image $a$ to completions with next image $b$. It fixes the previously exposed images and changes exactly two coordinates of each complete permutation. Since conditional completions are uniform, averaging the Lipschitz condition over this pairing gives $|h(a)-h(b)|\le 2K$.

Thus, conditionally on the first $k-1$ images, $M_k-M_{k-1}$ has mean zero and takes values in an interval of length at most $2K$. We need the range-length version of the Hoeffding lemma: if a real random variable $Z$ has mean zero and lies in an interval of length $\ell$, thenHere is a proof. For $\psi (\lambda )=\log \mathbb{E}{e}^{\lambda Z}$, differentiation gives ${\psi }^{\prime \prime }(\lambda )={\mathrm{Var}}_{\lambda }(Z)$ under the exponentially tilted probability distribution. Any distribution on an interval of length $\ell$ has variance at most ${\ell }^2/4$, because its squared distance from the interval midpoint is at most ${\ell }^2/4$. Since $\psi (0)={\psi }^{\prime }(0)=0$, integrating this second-derivative bound gives the lemma for both signs of $\lambda$. The same argument holds for every conditional distribution.

Apply it conditionally to each martingale difference and use the tower property of conditional expectation repeatedly:The exponential Markov bound now gives, for $\lambda >0$,Choose $\lambda =t/(n{K}^2)$ to obtain the upper tail in the box, and apply the argument to $-f$ for the lower tail. This proves concentration of Lipschitz functions on the symmetric group. Using only the bound $|M_k-M_{k-1}|\le 2K$ in the absolute-increment Azuma-Hoeffding inequality would lose a factor four in the exponent; the conditional range length is what yields the constant needed in part (ii).

Expose the independent coordinates one at a time and define the Doob exposure martingaleFor a fixed exposed prefix, couple the future coordinates identically under two choices of $Z_i$. The coordinate-change hypothesis bounds the difference of the resulting conditional expectations by $c_i$. Thus the increment $D_i=M_i-M_{i-1}$ has conditional mean zero and lies in a conditional interval of length at most $c_i$. This range bound, rather than merely $|D_i|\le c_i$, gives the sharp constant in the McDiarmid inequality.

Here is a proof of the needed Hoeffding lemma. For a mean-zero random variable $X$ in an interval of length $c$, let $h(u)=\log \mathbb{E}{e}^{uX}$. Its second derivative is the variance under the exponentially tilted distribution. A random variable in $[a,b]$ has variance at most $(b-a{)}^2/4$: the inequality $\mathbb{E}[(X-a)(b-X)]\ge 0$ gives $\mathrm{Var}X\le (\mathbb{E}X-a)(b-\mathbb{E}X)\le (b-a{)}^2/4$. Hence $h^{\prime \prime }(u)\le c^2/4$, and $h(0)=h^{\prime }(0)=0$ imply $h(u)\le u^2{c}^2/8$, for either sign of $u$.

Apply this conditionally to each increment and iterate the conditional expectation:For $u>0$, Markov's inequality bounds the upper tail by $\exp (-ut+u^2\sum c_i^2/8)$. Taking $u=4t/\sum c_i^2$ and then applying the same argument to $-f$ givesAt $t=0$ the bound is immediate. If all $c_i$ vanish, $f$ is constant on the product support and the positive tails are zero, so that degenerate case is handled directly.

For a binomial random graph, let coordinate $i$ be the entire vector of edges from vertex $i$ to vertices of smaller label. The coordinates are independent finite probability spaces. Changing coordinate $i$ changes only edges incident to that one vertex. Deleting the vertex gives the same graph under both outcomes, and each outcome's chromatic number is either that graph's chromatic number or one more. Thus the coordinate range is at most one. Taking all $c_i=1$ and $t=\lambda \sqrt{n}$ proves vertex exposure for chromatic number:Using individual edges as coordinates would give a weaker scale; grouping the incident edges is what yields the required bound.

For the expectation asymptotic, take fixed $0<p<1$, put $b=1/(1-p)$, and write $L={\log }_{b}n$. We outline both bounds and the step that turns probability estimates into an expectation estimate. For each fixed $\gamma >0$, the expected number of independent sets of size $k=\lceil (2+\gamma )L\rceil$ isIts logarithm is $k\log n-\frac{1}{2}k(k-1)\log b-O(k\log k)=-{\Omega }_{\gamma }((\log n{)}^2)$. Thus Markov's inequality gives $\alpha (G)\le (2+\gamma )L$ with probability tending to one, and $\chi (G)\ge n/\alpha (G)$ yields the corresponding lower bound on its expectation.

For the upper bound, set $m_0=\lceil n/(\log n{)}^2\rceil$ and $k=\lfloor (2-\gamma )L\rfloor$, with $0<\gamma <1$. The key uniform fact is that every vertex subset of size at least $m_0$ contains an independent $k$-set with probability tending to one. For a fixed subset of size $m$, let $X$ count its independent $k$-sets and let $\mu =\left(\genfrac{}{}{0ex}{}{m}{k}\right)b^{-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. The normalized dependency sum in Janson inequality is bounded byThe $j=2$ term is $O(k^4/m^2)$. The remaining overlap terms give the same order or less: use $\left(\genfrac{}{}{0ex}{}{k}{j}\right)\left(\genfrac{}{}{0ex}{}{m-k}{k-j}\right)/\left(\genfrac{}{}{0ex}{}{m}{k}\right)\le (2k^2/m{)}^j$ for large $n$, and split the sum at $k/2$. For the lower half the terms beyond $j=2$ decrease at the initial endpoint and are exponentially small at the other endpoint; for the upper half, $k\le (2-\gamma /2){\log }_{b}m$ makes every endpoint exponent negative of order $(\log n{)}^2$. Also $1/\mu$ is exponentially small on that scale. The exponential form of Janson inequality therefore gives, uniformly for $m\ge m_0$,for a positive constant depending only on $p,\gamma$. A union bound over at most $2^n$ subsets succeeds, because $m_0^2/k^4$ is of order $n^2/(\log n{)}^8\gg n$. This is independent sets in every large subset of a dense random graph.

On that event, repeatedly remove an independent $k$-set and assign it one new colour until fewer than $m_0$ vertices remain; colour the remainder individually. This gives $\chi (G)\le n/k+m_0$. The failure probability is exponentially small compared with $1/\log n$, and always $\chi (G)\le n$, so the failure event contributes negligibly to the expectation. Combining the upper and lower bounds and then letting $\gamma \downarrow 0$ provesThis is the chromatic number of a binomial random graph asymptotic. The slash in the printed expression must be read with $2{\log }_{1/(1-p)}n$ as the denominator; a multiplicative reading would eventually exceed $n$. At the endpoint probabilities $p=0$ and $p=1$, the chromatic numbers are respectively one and $n$ for $n\ge 1$, so this logarithmic formula is intended for $0<p<1$.