Chromatic number $\chi(G)=600$, $P(\chi(G|_S)\leq 200) \leq 2^{-10}$ 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.

Hints:


*

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

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

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

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