# Probability in Chromatic number upper bound of induced subgraph

Let $$G=(V, E)$$ be a graph with chromatic number $$\chi(G)=1000 .$$ Let $$U \subset V$$ be a random subset of $$V$$ chosen uniformly from among all $$2^{|V|}$$ subsets of $$V$$. Let $$H=G[U]$$ be the induced subgraph of $$G$$ on $$U$$. Prove that $$\operatorname{Pr}[\chi(H) \leq 400]<1 / 100$$

This is an exercise on The Probabilistic Method, authors are Noga Alon, Joel H. Spencer.

Fix a partition $$V = V_1 \cup V_2 \cup \cdots \cup V_{1000}$$ into independent sets and let $$U_i = U \cap V_i$$. A uniformly random subset of $$V$$ includes each element of $$V$$ independently with probability $$1/2$$, so the $$U_i$$ are independent.
Apply the Hoeffding-Azuma inequality with the martingale that reveals each $$U_i$$ one at a time. We always have the option to give the vertices of $$U_i$$ in $$H$$ their own colour, so each $$U_i$$ can affect $$\chi(H)$$ by at most $$1$$. It follows that $$\chi(H)$$ is exponentially concentrated in some interval of length on the order of $$\sqrt{1000}$$, but we don't know where.
Now note that (i) $$\chi(G[V\setminus U])$$ has the same distribution as $$\chi(H)$$ and (ii) $$\chi(H) + \chi(G[V\setminus U]) \geq 1000$$ (else we can combine their colourings to obtain a cheaper colouring of $$G$$). So if $$\Pr(\chi(H) \leq 400) > 1/100$$, then we also have $$\Pr(\chi(H) \geq 600) > 1/100$$, but this isn't consistent with exponential concentration in a short interval.