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