Collection of Graphs Let $n \in \mathbb{N}$ and $r \in \mathbb{R}$. We say that $(V, G_{1}, G_{2}, ..., G_{t})$ is a $(r,n)$-collection if $V$ is a set of $n$ vertices, and $G_{1}, G_{2}, ..., G_{t}$ are $t = n^{20}$ graphs on $V$ such that $\chi(G_{i}) \ge r$ for every $i$. 
We say that a $(r,n)$-collection $(V, G_{1}, G_{2}, ..., G_{t})$ is special if there exist $U \subseteq V$ such that $|U| \le 2n/3$ and $\chi(G_{i}[U]) \ge r/3$ for every $i$.
Is it true that for sufficiently large $n$, every $(r,n)$-collection is  special: (i) when $r = 3n^{0.1}$? (ii) when $r = 3\log_{2}(n)$?
Now I don't really know how to approach this question. I tried to use martingales but I don't understand how to use it here. I also don't know how to construct graphs with such chromatic numbers.
 A: For part (i) of the question, the statement is true, and in fact a (uniformly) randomly chosen $U \subseteq V$ will satisfy all the requirements with high probability. To do this, we need to know that if $G$ is a graph with $\chi(G) \ge r$, then there's a high probability that $\chi(G[U]) \ge \frac r3$.
First of all, the expectation $\mathbb E[\chi(G[U])]$ can't be too low. Let $\chi(G) = s$, for some $s \ge r$. Then $\mathbb E[\chi(G[U])] \ge \frac s2$ by a symmetry argument I elaborate on in response to this question.
This helps us start off a martingale argument: let $V_1, V_2, \dots, V_s$ be the $s$ color classes of a coloring of $G$, and consider the Doob martingale where we reveal $U \cap V_i$ at the $i^{\text{th}}$ step. (This is Lipschitz, since changing $U \cap V_i$ can change $\chi(G[U])$ by at most $1$.) After $s$ steps, we've revealed all of $U$, and by Azuma's inequality, $$\Pr[\chi(G[U)] \le \mathbb E[\chi(G[U])] - T] \le \exp\left(-\frac{T^2}{2s}\right).$$ Take $T = \frac s6$, and we conclude that $\Pr[\chi(G[U)] \le s/3] \le \exp(-s/72)$, which implies also the weaker claim that $\Pr[\chi(G[U)] \le r/3] \le \exp(-r/72)$.
When $r = 3n^{0.1}$, or in general when $r \gg \log n$, this probability is less than $n^{-20}$ or any other polynomial probability, provided $n$ is sufficiently large. Also, $|U| \le \frac23n$ with very high probability, so the union bound on all of our constraints finishes the argument.

For part (ii) of the question, this will not fly, because $r$ is too small. In fact, much more is true in this case: we can pick $G_1, \dots, G_t$ so that for every $U$, some $G_i[U]$ will have no edges at all.
Let each $G_i$ consist of a single copy of $K_r$ on a uniformly random $r$-subset of $V$; choose $n^{20}$ of these completely independently. For a fixed $U$ of size at most $\frac23 n$, there is a probability of $(\frac13)^r$ that $G_i$ misses $U$ entirely, and $(\frac13)^r = 3^{-3\log_2 n} \approx n^{-4.75}$. This is small, but not too small: with $n^{20}$ different $G_i$, the average number of $G_i$ that have no edges in $U$ is bigger than $n^{15}$. 
Moreover, because these are independent, the distribution of the number of such $G_i$ approaches the Poisson very rapidly, so the probability that no $G_i$ miss $U$ approaches $e^{-n^{15}}$. This is easily small enough for us to take a union bound over all $< 2^n$ choices of $U$.
