Proving a lower bound on chromatic number expectation Given G=(V,E) with chromatic number 1000,
I need to prove that the expected chromatic number of a random subgraph (i.e. picked randomly and uniformly from all possible subgraphs of G) of G is at least 500.
Does anyone have an Idea?
 A: This is true for a random induced subgraph, simply for reasons of symmetry. 
If $U \subseteq V$, let $G_1 = G[U]$ and $G_2 = G[V \setminus U]$. Then $\chi(G) \le \chi(G_1) + \chi(G_2)$: given a coloring of $G_1$ with $\chi(G_1)$ colors, and a coloring of $G_2$ with $\chi(G_2)$ completely separate colors, we can color $G$ just by combining those two colorings. So we have $\chi(G_1) + \chi(G_2) \ge 1000$. If we pick either $G_1$ or $G_2$ as our subgraph $H$ with equal probability, then $\mathbb E[\chi(H)] \ge 500$.
We can pick a uniformly random induced subgraph $H$ by picking a uniformly random $U$, and then picking either $H = G[U]$ or $H = G[V \setminus U]$ with equal probability. By the argument above, $\mathbb E[\chi(H) \mid U] \ge 500$, and therefore $\mathbb E[\chi(H)] \ge 500$.
This is false for a random subgraph if it is not necessarily induced: just take $G = K_{1000}$. Then a random subgraph of $G$ is just the random graph $G(1000, \frac12)$, which on average has much smaller chromatic number.
