Chromatic Number Of A Random Graph

Question

Does anyone know what the chromatic number of a graph chosen randomly on n vertices is, as n tends to infinity?

I mean, almost all graphs have chromatic number greater than any fixed k. But in terms of estimates, is O(n), O(log n), O(sqrt(n)) a good estimate for the chromatic number of large random graphs?

Answer 1

I assume by your wording that you are concerned with $G(n,1/2)$. This is the uniform distribution over all graphs on vertex set $\{1,\ldots, n\}.$ Then $$\chi(G(n,1/2)) \sim \frac{n}{2\log_2(n)}.$$ So $\Theta(n/\log n)$ is the estimate you were asking about.

Answer 2

There is a rather annoying proof (Bollobás, 1987) that there is a function $d: \mathbb{N} \to \mathbb{N}$ such that as $n \to \infty$, $$\mathbb{P} \left(\text{$G$ has $\omega(G) \in \{ d(n), d(n)-1, d(n)+1\}$} \right) \to 1$$ where $\omega(G)$ is the clique number of $G$, and $G$ is drawn from $\mathcal{G}(n, p)$, the space of random graphs on $n$ vertices where each edge is present with probability $p$ independently at random. Moreover, that proof gives

$$\omega(G) \sim 2 \frac{\log(n)}{\log(1/p)}$$

Now, the chromatic number $\chi(G)$ is $\geq \frac{|G|}{\alpha(G)}$ where $\alpha$ is the independence number. That is, $\frac{n}{\omega(\bar{G})}$ where $\bar{G}$ is drawn from $\mathcal{G}(n, 1-p)$. This gives a lower bound of approximately $$\frac{n}{2 \log(n)} \log \left(\frac{1}{1-p} \right)$$

With even more annoying fiddling, we obtain $$\chi(G) = \left(\frac{1}{2} + o(1) \right) \log\left(\frac{1}{1-p}\right) \frac{n}{\log(n)}$$ for almost every $G$ as $n \to \infty$.

Answer 3

Bollobás proves in his book "Random Graphs" that for $p\in (0,1)$, almost every $G(n,p)$ satisfies the following: $$ \frac{n}{2\log_d{n}}\left( 1 + \frac{\log\log{n}}{\log{n}}\right) \le \chi(G(n,p)) \le \frac{n}{2\log_d{n}}\left( 1 + \frac{3\log\log{n}}{\log{n}}\right) $$ where $d=1/(1-p)$. Hence, for almost every $G(n,p)$, it is true that we have $$\chi(G(n,p)) \sim \frac{n}{2\log_d{n}}(1+o(1))$$ However, McDiarmid strengthened this in 1990 by proving that actually, we have $$ \frac{n}{s(n) + o(1)} \le \chi(G(n,p)) \le \frac{n}{s(n) - \frac{1}{2} - \frac{1}{1-\sqrt{1-p}}+ o(1)} $$ where $s(n) = 2\log_d{n} - 2\log_d\log_d{n} + 2\log_d{e/2}$, with $d$ as above. What's also interesting is that the chromatic number concentrates about its mean, which is to say that $$\mathbb{P}(|\chi(G(n,p)) - \mathbb{E}\chi(G(n,p))|\ge t) \le 2 e^{-t^2/2n}$$ for $t>0$, and one way to show this is with a cute application of Azuma's inequality.