# Chromatic number of a subgraph of a random graph

Suppose that we have a random graph G(n,p) with $$n$$ vertices and each edge exists with probability $$p = n^{-\alpha}, \alpha>\frac{5}{6}$$. Prove that with high probability, say $$1-\delta$$, every subgraph with $$o(\sqrt{n})$$ vertices has a chromatic number equal to 3.

This is the first part of a problem that I'm stuck at it.

• Is this a step in the proof of two-point concentration of the chromatic number $\chi(G(n,p))$? – Misha Lavrov Apr 16 at 20:32
• @MishaLavrov It is the first step in the proof of a concentration for the chromatic number. What do you mean by two-point? – SMA.D Apr 16 at 20:39
• By two-point I mean the result that for some range of $p$ (I do not remember which) the chromatic number has one of two values with high probability. – Misha Lavrov Apr 16 at 21:38
• @MishaLavrov In my problem it was asked to prove $u\le\chi(G)\le u+3$ with high probability. – SMA.D Apr 17 at 4:40
• That's also pretty good! The $u \le \chi(G) \le u+1$ result can be found in this paper by Luczak. – Misha Lavrov Apr 17 at 5:07

For any $$k$$, the expected number of sets of $$k$$ vertices with at least $$\frac32k$$ edges between them is no more than $$\binom nk \binom{\binom k2}{\frac32 k} p^{\frac32k} \le \binom nk \binom{\frac12 k^2}{\frac32 k} p^{\frac32k}.$$ Using the inequality $$\binom nk \le \left(\frac{ne}{k}\right)^k$$, we can show that when $$k \le \sqrt n$$, this is bounded by $$f(n)^k$$ for some function $$f(n)$$ such that $$f(n) \to 0$$ as $$n \to \infty$$. (Try this!) In particular, if we sum over all $$k \le \sqrt n$$, the sum is bounded by $$\frac{f(n)}{1-f(n)}$$, which is still tending to $$0$$ as $$n \to \infty$$.
So with high probability, there are no sets of $$k\le \sqrt n$$ vertices with $$\frac32k$$ edges between them: in other words, the average degree of any subgraph on at most $$\sqrt n$$ vertices is less than $$3$$.
Then we can $$3$$-color any such subgraph by choosing a vertex $$v$$ of degree $$2$$, removing it, coloring the rest inductively, and putting $$v$$ back in with a color different from either of its neighbors.