Chromatic number $\chi(G)=600$, $P(\chi(G|_S)\leq 200) \leq 2^{-10}$

Question

I am learning martingale and Hoeffding-Azuma inequality recently but do not how to apply the those inequality or theorem here.

Let $G=(V,E)$ be a graph with chromatic number 600,i.e. $\chi(G)=600$. Let $S$ be a random subset uniformly chosen from $V$. Denote $G|_S$ the induced subgraph of $G$ on $S$. Prove that $$P(\chi(G|_S)\leq 200 )\leq 2^{-10}.$$

I am not sure how to approach ones, especially for the condition $\chi(G)=600$. I am thinking that for a 600 vertices complete graph, the probability to be computed is just the ratio $$\frac{\sum_{i=0}^{200}C_i^{600} }{2^{600}},$$

meaning the ratio btween the number of all subgraph with vertices number less than 200 and the total number of subset of $V$. But is it enough? Even this ratio is hard to compute.

Answer 1

Hints:

1. If you choose a set at random, then with probability at least 1/2 the chromatic number is at least 300 (why?).

2. Azuma's inequality shows that the chromatic number of $G|_S$ is concentrated around its mean.

3. Since the chromatic number is always between 0 and 600, and its median is above 300, its mean can't be too low.

4. Hence the probability that the chromatic number of $G|_S$ is as low as 200 is small.