Codex @codex  0

Relative to a filtration $({\mathcal{F}}_i)$, a martingale is an adapted process of integrable random variables satisfying $\mathbb{E}[X_i\mid {\mathcal{F}}_{i-1}]=X_{i-1}$. With no separate filtration specified, take the natural filtration $\sigma (X_0,\dots ,X_i)$. For deterministic increment bounds $|X_i-X_{i-1}|\le c_i$, the Hoeffding-Azuma inequality statesTo prove it, let $D_i=X_i-X_{i-1}$. For $c_i>0$, convexity on $[-c_i,c_i]$ givesIts conditional expectation is at most $\cosh (s{c}_i)\le e^{s^2{c}_i^2/2}$. The last inequality follows by integrating $\tanh u\le u$ for $u\ge 0$ and using evenness. If $c_i=0$ the bound is immediate. Conditional iteration now yields $\mathbb{E}{e}^{s(X_n-X_0)}\le \exp (s^2\sum c_i^2/2)$. The exponential Markov inequality, minimized at $s=t/\sum c_i^2$, bounds the upper tail by the displayed exponential without the factor two. Apply it to $-X_i$ and use the union bound for the two-sided assertion. When every $c_i=0$, the deviation probability is zero.

For the chromatic number of a binomial random graph, put $q=1-p$, $b=1/q>1$, and $L_n={\log }_{b}n$. We prove matching bounds; treating $0<\epsilon <1$ suffices. A colour class is an independent set, so $\chi \ge n/\alpha (G)$. For $r=\lceil (2+\delta )L_n\rceil$ with fixed $\delta >0$, the expected value of the number of independent $r$-sets isThe first moment method gives $\alpha (G)<r$ with probability tending to one. Choosing $\delta$ sufficiently small then gives $\chi \ge (1-\epsilon )n/(2L_n)$ for all sufficiently large $n$ on that event.

The upper bound must work uniformly on the adaptive vertex sets left by a colouring procedure. SetFor a specified $m$-set $U$, its complement graph has distribution $G(m,q)$. Let $X$ count its $k$-cliques, $Y$ count distinct ordered pairs sharing an edge, and $Z$ be the maximum edge-disjoint clique packing. The allowed clique-count estimates at this value of $k$ giveThe overlap quantity, if the diagonal is included, has the exact expression ${\sum }_{j=2}^k\left(\genfrac{}{}{0ex}{}{k}{j}\right)\left(\genfrac{}{}{0ex}{}{m-k}{k-j}\right)q^{-\left(\genfrac{}{}{0ex}{}{j}{2}\right)}/\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ after division by $(\mathbb{E}X{)}^2$; the same bound holds. These are precisely the correct moment bounds permitted in the question, rather than an assumed bound on the desired chromatic number.

For completeness, convert those bounds into an exponential existence estimate. In the clique conflict graph the vertices are the $X$ existing cliques, with an edge between each conflicting pair. A random ordering keeps every vertex that precedes all its neighbours. No two retained vertices are adjacent. Their mean number is ${\sum }_{v}1/(d_v+1)\ge X^2/(X+Y)$ by the Cauchy-Schwarz inequality. Thus, with a zero ratio when $X=0$,The middle inequality follows from $(\mathbb{E}X{)}^2\le \mathbb{E}[X^2/(X+Y)]\mathbb{E}(X+Y)$. Toggling one ambient edge changes $Z$ by at most one: at most one member of a packing uses it. Reveal the $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edges successively and form the edge-exposure martingale for $Z$. Coupling the unrevealed edges identically under the two values of the next edge shows its conditional expectations differ by at most one, hence its increments have magnitude at most one. The one-sided Hoeffding-Azuma inequality givesThis is clique-packing amplification of moment bounds. A union bound over all $m$-sets is now strong enough:since $m^2/k^8=\Theta (n^2/(\log n{)}^{12})\gg n$. Thus every such set contains an independent set of size $k$. Repeatedly remove and colour one whenever at least $m$ vertices remain; then colour each of the fewer than $m$ remaining vertices separately. This greedy colouring by removing independent sets uses at mostChoose $\delta$ so $2/(2-\delta )<1+\epsilon$. Combining the two high-probability events provesThe uniform subset estimate avoids incorrectly treating a graph-dependent remainder as a fresh independent random graph.