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.
My copy of the book being in my locked-down office makes it easy to avoid checking which section this question is from for a hint of the expected method, so here's a sledge hammer.
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.
I haven't checked that the numbers work out in this case, but this method should at least solve some problems of this basic shape.
