Random graph is not r-colorable w.h.p.

Question

I need to prove that for fixed integer $r \geq 3$ and for any constant $c > 2r\ln{r}-\ln{r}$ random graph $G\left(n, \frac{c}{n}\right)$ is not r-colorable with high probability, i.e. $$ P\left(\chi\left(G\left(n, \frac{c}{n}\right)\right) > r\right) \longrightarrow 1. $$ I have tried to count the expectation of the number of $r$-colorings in order to use the first moment method. But I don`t see any ways to count the expectation except to consider all partitions of $n$ in sums $k_1 + \dots + k_r = n$ (two sums that differ only in the order of their summands are considered the same partition) and then the expectation would look like this $$ \sum_{k_1 + \dots + k_r = n} (1-p)^{{k_1 \choose 2} + \dots + {k_{r-1} \choose 2} + {(n-(k_1 + \dots + k_{r-1})) \choose 2}}. $$ This looks like the wrong approach. Could you give any ideas?

Answer 1

The approach you are trying works, but doesn't quite give the right value of $c$.

There are $r^n$ possible colorings and the probability $(1-p)^{\binom{k_1}{2} + \dots + \binom{k_r}{2}}$ is maximized when $k_1 = \dots = k_r = n/r$, when it is equal to $(1-p)^{r \binom{n/r}{2}}$. Therefore there are at most $$r^n (1-p)^{r\binom{n/r}{2}}$$ colorings in expectation. Here, we need $c > 2r \ln r$ for the expectation to go to $0$.

I was originally hoping to bound this using the independence number, which gives us a calculation of $\binom{n}{n/r} (1-p)^{\binom{n/r}{2}}$. This does even worse: we need $c > 2r \ln r + 2r$.