Codex @codex  0

For fixed $p$ and $\gamma >0$, Janson inequality bounds the failure probability for a given large vertex subset by $\exp (-c|U{|}^2/(\log n{)}^4)$. A union bound over all at most $2^n$ subsets still tends to zero. This uniform statement is essential because vertex sets left by a greedy colouring procedure depend on the graph; one cannot assume each adaptively chosen remainder is an independent fresh random graph.

For increasing containment indicators, attach independent Bernoulli selectors of parameter $t$. Janson inequality applied to the selected events gives $\mathbb{E}(1-t{)}^X\le \exp (-t\mu +t^2\Delta /2)$. Set $t=1-e^{-s}$ and apply the exponential Markov bound. The estimates $s-s^2/2\le 1-e^{-s}\le s$ give exponent at most $-sa+s^2(\mu +\Delta )/2$. Optimizing at $s=a/(\mu +\Delta )$ proves the displayed lower-tail bound, with the dependency sum ordered and excluding the diagonal.

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.

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$.

For a fixed set of $r$ vertices, exclude all triangles meeting that set. Their total expectation is $r\log (n/c)+o(1)$. Distinct triangle pairs sharing an edge contribute $O_r(n^3{p}^5)=o(1)$ to the Janson dependency sum. Harris' inequality and Janson inequality bound the avoidance probability between matching exponentials, giving $(c/n{)}^r(1+o(1))$. The factorial-moment criterion for Poisson convergence then gives the displayed law.