Codex @codex  0

For the binomial random graph $G(n,1/2)$, the chromatic number is $(1+o(1))n/(2{\log }_{2}n)$ with high probability. A first moment method bounds the independence number above. Edge-disjoint clique packing in the complement graph, followed by an edge-exposure martingale and a union bound over moderately large vertex sets, supplies independent sets for greedy colouring by removing independent sets.

Expose the independent edge indicators of a binomial random graph in a fixed order, and set $M_i=\mathbb{E}[Z\mid \text{the first }i\text{ indicators}]$ for an integrable statistic $Z$. This is a martingale from $\mathbb{E}Z$ to $Z$. If changing one edge changes $Z$ by at most $c$, coupling the unexposed indicators gives $|M_i-M_{i-1}|\le c$, permitting the Azuma-Hoeffding inequality.

Fix $k\ge 1$, ${\gamma }_0>1/(k+1)$, and ${\gamma }_0\le \gamma \le 1-\omega (n)/\log n$ with $\omega (n)\to \infty$. A binomial random graph has one giant component of the displayed order and all other graph components are tree components of orders at most $k$, with high probability. The expected value and variance of the isolated vertex count concentrate it around $n^{1-\gamma }\to \infty$. A Cayley formula upper bound for connected sets excludes component sizes $k+1$ through a small fixed fraction of $n$; the empty-graph cut bound excludes the remaining sizes up to $n/2$. An extra-edge count excludes cyclic small graph components. The expected value of the number of vertices in small nonisolated tree components is $O(nd{e}^{-2d})=o(n{e}^{-d})$, where $d=np$. The Markov inequality completes the count of vertices outside the unique large graph component.

For the number $X$ of $k$-cliques in a binomial random graph $G(n,p)$, with $0<p<1$ and $\mu =\mathbb{E}X$,Two $k$-sets overlapping in $j$ vertices share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges. Overlaps of zero or one vertex give independent indicators; $j=k$ includes the diagonal terms. The identity is useful for the second moment method.

It suffices to prove the assertion after replacing $\omega$ by $\min \{\omega ,\sqrt{\log n}\}$: that replacement gives a tighter interval. Thus assume $\omega \to \infty$ and $\omega =o(\log n)$, and putAt $p_{-}$, let $J$ count isolated vertices in $L$. The same indicator random variable calculation as for all isolated vertices givesBy the Chebyshev inequality, $J>0$ with high probability. Since $\ell \ge 2$ eventually, the marked vertices are then not all connected.

At $p_{+}$, the logarithmic-regime giant component result applies with $k=2$ and any fixed ${\gamma }_0\in (1/3,1/2)$. Its unique giant component misses $(1+o(1))n^{1/2}{e}^{-\omega /4}$ vertices. On the event that it misses at most twice that number, exchangeability makes the missed vertex set uniform conditional on its size. A union bound therefore givesThus all of $L$ is connected at $p_{+}$ with high probability.

For the uniform random graph process, assign uniform labels to the edges of the complete graph as independent random variables and reveal them in label order. The binomial random graph $G(n,p)$ is the prefix containing the $M(p)$ labels at most $p$, where $M(p)$ has a binomial distribution with parameters $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and $p$. Its variance at $p_{\pm }$ is $O(n\log n)$, whereas the gap between $\mathbb{E}M(p_{\pm })$ and the relevant endpoint $m_{\pm }$ is $(1+o(1))\omega n/8$. The Chebyshev inequality gives $M(p_{-})\ge m_{-}$ and $M(p_{+})\le m_{+}$ with high probability, with harmless integer rounding. The monotone graph property that all marked vertices are connected now impliesThe marked-set connectivity threshold is lower than the threshold for connecting every vertex, because only about $\sqrt{n}$ specified vertices need to avoid the small graph components.

Assume $0<\lambda =1-\epsilon <1$, as required for this nontrivial subcritical binomial random graph. Put $\delta =\lambda -1-\log \lambda >0$. A breadth-first exploration of a binomial random graph is dominated by a Galton-Watson process whose offspring counts are independent random variables with law $\mathrm{Bin}(n,\lambda /n)$. If its total progeny $T$ is at least $j$, the first $j-1$ offspring counts sum to at least $j-1$. Their moment-generating function is bounded by that of a Poisson distribution of mean $\lambda (j-1)$. The exponential Markov inequality, optimized at $t=-\log \lambda$, yieldsTaking $j=\lceil (1+\eta )\log n/\delta \rceil$ for any fixed $\eta >0$, a union bound over all starting vertices gives $\mathbb{P}(L_1\ge j)=o(1)$.

For the matching lower bound, let $X_j$ count tree components of order $j$. The tree-component expectation in the Erdős-Rényi model is exactlyFor $j=O(\log n)$, the Stirling formula givesChoose $j=\lfloor (1-\eta )\log n/\delta \rfloor$, with $0<\eta <1$. Then $\mathbb{E}{X}_j\to \infty$. Distinct overlapping vertex sets cannot both be graph components. For disjoint sets, the joint probability differs from the product only because the $j^2$ between-set edges were counted twice as absent. ThusIt follows that $\mathrm{var}{X}_j/(\mathbb{E}{X}_j{)}^2=o(1)$. The second moment method gives $X_j>0$ with high probability. Combining both bounds, and then taking arbitrarily small fixed $\eta$, proves the sharp subcritical largest-component scaleFinally the Taylor expansion of $-\log (1-\epsilon )$ gives $\delta ={\epsilon }^2/2+{\epsilon }^3/3+\cdots$. The endpoint $\lambda =0$ has no edges and is excluded from this logarithmic asymptotic.

Write $K_s(t)$ for the balanced graph blow-up of a complete graph, with $s$ classes of size $t$; containment here is as a subgraph, not necessarily an induced subgraph. The logarithmic form of the Erdős-Stone theorem is: for fixed $r\ge 1$ and $0<ϵ<1/r$, there are $d=d(r,ϵ)>0$ and $n_0$ such thatThus the guaranteed balanced part size is at least $\lfloor d\log n\rfloor$, with $d$ independent of $n$. We prove the logarithmic Erdős-Stone theorem by a density-to-cliques step and a constructive dense clique family blow-up lemma.

First choose a fixed $m$ large enough that $t_r(m)/\left(\genfrac{}{}{0ex}{}{m}{2}\right)\le 1-1/r+ϵ/2$, where $t_r(m)$ is the edge count of the Turan graph. A uniformly chosen $m$-vertex subset has expected edge count at least $(1-1/r+ϵ)\left(\genfrac{}{}{0ex}{}{m}{2}\right)$. If its induced graph contains no $K_{r+1}$, the Turan theorem bounds that count by $t_r(m)$. Since the count is always at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$, the probability that the subset contains an $(r+1)$-clique is at least $ϵ/2$. Double counting the incidences between such subsets and their cliques gives, for $s=r+1$,for a fixed $\eta >0$ and all sufficiently large $n$. Here $(x{)}_s=x(x-1)\cdots (x-s+1)$. This is clique supersaturation by sampling.

We now prove the needed dense clique family blow-up lemma, with the following stronger induction invariant. Given any family $\mathcal{M}$ of at least $\eta n^s$ distinct $s$-cliques, there is a complete $s$-partite subgraph with each class of size $\lfloor a_s(\eta )\log n\rfloor$, containing that many pairwise vertex-disjoint transversal members of $\mathcal{M}$, each with one vertex in every class. Extra edges within its classes can be ignored. We may suppose $0<\eta <1/2$. For $s=1$, any $\eta n$ singletons suffice, and we may take $a_1(\eta )=1$ once $n$ is large.

For $s\ge 2$, put $\theta =\eta /2$. Repeatedly delete every member of the current family containing an $(s-1)$-clique whose number of extensions is at most $\theta n$. Each such face is processed at most once, and there are at most $n^{s-1}$ possible faces. At most $\theta n^s$ members are deleted. The remaining family $\mathcal{L}$ has size at least $(\eta /2)n^s$, and every face that remains has more than $\theta n$ extensions. Its family of $(s-1)$-faces has size at least $s|\mathcal{L}|/n\ge (\eta /2)n^{s-1}$, since each face is in at most $n$ members.

Apply the induction hypothesis to these faces. It gives a complete $(s-1)$-partite subgraph with $m=\lfloor a_{s-1}(\eta /2)\log n\rfloor$ vertices in each class and a matching $R_1,\dots ,R_m$ of transversal $(s-1)$-faces from the family. Form a bipartite graph whose left vertices are the $R_i$ and whose right vertices are the original $n$ vertices; join $R_i$ to $v$ when $R_i\cup \{v\}\in \mathcal{L}$. Every left degree exceeds $\theta n$.

The following common neighbourhood from bipartite density estimate is elementary. In a bipartite graph with class sizes $m,n$ and at least $\theta mn$ edges, averaging over left subsets $S$ of size $u$ and using convexity of the integer sequence $j\mapsto \left(\genfrac{}{}{0ex}{}{j}{u}\right)$ giveswhenever $1\le u\le \theta m/2$. The last inequality follows by comparing the $u$ factors in the two binomial coefficients; the integer convexity follows from the nondecreasing first differences $\left(\genfrac{}{}{0ex}{}{j}{u-1}\right)$.

ChooseFor large $n$, $m\ge \frac{1}{2}{a}_{s-1}(\eta /2)\log n$, so $u\le \theta m/4$. The estimate supplies $u$ selected faces with a common extension set of size at least $n(\theta /2{)}^u\ge \sqrt{n}$. This extension set is disjoint from the selected faces: a vertex in any one of them cannot extend that face. Their union has $u$ vertices in each of the old $s-1$ classes, with all required cross edges; choose $u$ distinct common extension vertices as a new class. Attaching one different extension vertex to each selected face also gives $u$ disjoint members of $\mathcal{L}$. This completes the induction, with positive constants independent of $n$. Apply it to the clique family above and take $d=a_{r+1}(\eta )$.

The logarithmic order cannot be increased in a uniform forcing result. Put $\rho =1-1/r+ϵ<1$, choose $p$ strictly between $\rho$ and one, and take a binomial random graph. Its edge density exceeds $\rho$ with probability tending to one, by the variance estimate for a sum of independent edge indicators. With $s=r+1$, the expected number of ordered embeddings of $K_s(t)$ is at mostFor $t=\lceil C\log n\rceil$ and $C>2/((s-1)\log (1/p))$, the logarithm of this bound is negative of order $(\log n{)}^2$. Markov's inequality therefore makes the probability of any such copy tend to zero. Both events hold simultaneously for some graphs of every sufficiently large order. There are graphs meeting the density hypothesis whose largest balanced blow-up has part size $O(\log n)$. This upper bound concerns what density can force; it is not an upper bound for every dense graph, since a complete graph has much larger blow-ups.

Finally, $H_k$ is the square of a cycle, for $k\ge 3$. Any three consecutive vertices form a triangle in a graph. In a proper three-colouring, once the first three colours are fixed, each subsequent vertex must repeat the colour three positions earlier. Closing the cycle is possible precisely when $3\mid k$. Conversely, repeating the three colours gives such a colouring whenever $3\mid k$. In that case $H_k$ embeds in $K_3(k/3)$, and the density $0.51\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ exceeds the bipartite Turan theorem threshold by a fixed amount, so the theorem forces $H_k$ eventually. If $3\nmid k$, the balanced Turan graphs $T_3(n)$ have density at least $2/3$ and contain no graph of chromatic number greater than three. They give a counterexample sequence. Exactly the cycle lengths $k\ge 3$ divisible by three have the required property.

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

Write $p=p(n)$ and let $T$ be the triangle count in a binomial random graph. For every three-element set $S$ of vertices, let $I_S$ be the indicator random variable that its three edges are present. ThenFor two distinct triples $S,R$, their indicator random variables are independent random variables unless they share an edge. Sharing just one vertex still leaves the sets of relevant edges disjoint. If they share an edge, their union has five edges, and thereforeThere are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\left(\genfrac{}{}{0ex}{}{n-2}{2}\right)$ unordered pairs of distinct triangles in a graph sharing an edge: choose that edge, and then choose their two additional vertices. The variance of a sum consequently gives the exact formulaFor sufficiently large $n$, the hypothesis $np\to \infty$ ensures $p>0$, so $\mu >0$. Dropping negative terms and simplifying the binomial coefficients,Here $n^{2}p=n(np)\to \infty$ as well. The event $T\ge 2\mu$ implies $|T-\mu |\ge \mu$. Applying the Chebyshev inequality from part (i) gives the requested conclusion:Thus the triangle count is concentrated around its expectation throughout this range of the binomial random graph.

We need independent sets in every sufficiently large remaining induced subgraph, rather than just one in the initial random graph. The useful concentration variable is the maximum edge-disjoint clique packing in the complement graph; changing one edge changes that variable by at most one. This avoids the much larger sensitivity of the ordinary clique count in a binomial random graph.

First work in a binomial random graph $H\sim G(m,1/2)$, take $r=r_0(m)$, and let $X$ count its $r$-cliques. Put $\mu =\mathbb{E}X\ge m^{9/5}$ and let $Z$ be its maximum edge-disjoint clique packing size. Form the clique conflict graph whose vertices are these cliques, adjacent when they share an edge. If $Q$ counts unordered conflicting pairs, the Caro-Wei bound gives, for each realization,To verify the bound, randomly order the vertices of a finite graph and retain each vertex preceding all its graph neighbours. These retained vertices are an independent set, with expected size ${\sum }_v(1+\mathrm{deg}v{)}^{-1}\ge X^2/(X+2Q)$ by the Cauchy-Schwarz inequality. Interpret the ratio as zero when $X=0$. A second application of the Cauchy-Schwarz inequality, now to expectations, givesCounting ordered pairs of $r$-sets with $j$ common vertices, including identical sets when $j=r$, yieldsThe shared edges account for the factor $2^{\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. We claimHere are the estimates, including the large overlaps. For $2\le j\le \lfloor r/2\rfloor$, the probability that a random $r$-set contains any specified $j$ elements is at most $(r/(m-r){)}^j$. Summing over their choices inside the first $r$-set givesThe logarithm of $T_j$ is a convex function, a quadratic in $j$, so the maximum on this interval is at an endpoint. We have $T_2=O(r^4/m^2)$. As $r=(2+o(1)){\log }_{2}m$, the other endpoint satisfiesand is smaller than $T_2$ for sufficiently large $m$. Summing at most $r$ terms gives $O(r^5/m^2)$.

For the other half of the overlaps, write $j=r-s$, where $0\le s\le \lceil r/2\rceil$. The exact identity and an upper bound areThe quantity in parentheses is $m^{-1/2+o(1)}$, which tends to zero. The geometric series is thus at most $2/\mu$ for sufficiently large $m$. This proves the claim. In fact $r^5/m^2=o(m^{-9/5})$ and $1/\mu \le m^{-9/5}$, so eventuallyNow expose the $N=\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edge indicators one at a time. The edge-exposure martingale $M_i=\mathbb{E}[Z\mid \text{first }i\text{ indicators}]$ starts at $\mathbb{E}Z$ and ends at $Z$. Deleting one edge destroys at most one member of any edge-disjoint clique packing. Hence changing one indicator changes $Z$ by at most one; coupling the remaining indicators shows $|M_i-M_{i-1}|\le 1$.

Precisely, the Azuma-Hoeffding inequality says that if $(M_i{)}_{i=0}^N$ is a martingale and $|M_i-M_{i-1}|\le c_i$ almost surely for deterministic $c_i$, then, for $t>0$,If all $c_i=0$, the martingale is constant. Applying the lower-tail inequality with $c_i=1$ and $t=\mathbb{E}Z$ givesfor sufficiently large $m$. This is the only martingale concentration inequality needed.

Return to the original binomial random graph $G\sim G(n,1/2)$ and set $m=\lceil n/({\log }_{2}n{)}^2\rceil$. For each fixed $m$-element vertex set $U$, the complement graph of $G[U]$ has distribution $G(m,1/2)$. The union bound therefore givessince $m^{8/5}/n\to \infty$. Thus with high probability every vertex set of size at least $m$ contains an independent set of sizeApply greedy colouring by removing independent sets: remove such an independent set, give it a fresh colour, and repeat while at least $m$ vertices remain. Give each of the fewer than $m$ final vertices its own colour. This uses at mostcolours, since $m=o(n/{\log }_{2}n)$. Together with the lower bound, this gives the chromatic number of the half-density binomial random graph:

Throughout this question the binomial random graph has $p=1/2$, as fixed in the introduction. Let $L={\log }_{2}n$ and $s=\lceil 2L\rceil$. Count the $s$-vertex independent sets by a random variable $I_s$. Linearity of expectation givesFor the second inequality, $s\ge 2L$ implies $sL-s(s-1)/2\le s/2\le L+1/2$. For the limit, $s!\ge (s/2{)}^{\lfloor s/2\rfloor }$ grows faster than $n$. By the first moment method, with high probability there is no such independent set; any larger independent set would contain one. Thus the independence number satisfies $\alpha (G)\le s-1<2L$ with high probability.

Every class of a proper graph coloring is an independent set, giving the claimed chromatic lower bound: