Parameter $d$ that makes the probability of the graph $G(n,\frac{d}{n})$ being $k$-colorable tends to $0$, as $n \to \infty$ , for $k \leq 2$.

67 Views Asked by At

This is an exercise that I'm doing.

Let $\epsilon > 0$ and $d > 0$ be fixed. Prove that for $k \geq 2$, if $d \geq (1 + \epsilon)2k(\text{log} k + 1)$, then, $\lim\limits_{n \to \infty} \mathbb{P}\left[\text{G}\left(n,\frac{d}{n}\right) \text{ is $k$-colorable} \right] \to 0$.

I'm not sure I understand the statement. Wouldn't it be the case that as $n \to \infty$, $\frac{d}{n} \to 0$, the graph becomes more sparse, and thus easier to be properly $k$-colored? I'd like some hint if possible.

1

There are 1 best solutions below

0
On

Whether the graph becomes "more sparse" or not is a question of how you measure sparseness; certainly the fraction $\frac{\text{total edges}}{\text{possible edges}}$ goes to $0$, but on the other hand, the average degree remains fixed at $d$. (Well, almost; if we were pickier, we'd set the edge probability to $\frac{d}{n-1}$, but asymptotically that's the same.)

The reason that the random graph has high chromatic number is the lower bound $$\chi(G) \ge \frac{n}{\alpha(G)}$$ which comes from the fact that every color class is an independent set, and therefore contains at most $\alpha(G)$ vertices. To color all $n$ vertices, we need at least $\frac{n}{\alpha(G)}$ colors.

Show that with high probability, $G(n, \frac dn)$ has no independent set of size $\frac nk$, and you'll have shown that with high probability, it's not $k$-colorable.