Concentration inequalities for random sets $\newcommand{\abs}[1]{\left|#1\right|}$
There is a population $O$ with a countable (finite or infinite) number of subjects. The population is colored randomly: for each subject, an unbiased coin-toss is used to decide whether the subject is colored red or green. Then, a sub-population containing $t$ subjects are selected; denote this sub-population by $T$ (so $T\subseteq O$ and $|T|=t$). Denote by $T^R$ the set of red subjects in $T$ and by $T^G$ the set of green subjects. The difference $\abs{|T^R|-|T^G|}$ denotes the imbalance caused by the randomization process. What is high-probability upper bound on this imbalance, as a function of $t$?
There are two extreme cases:


*

*The easy case is when $T$ does not depend on the coloring, i.e, $T$ is a deterministic set defined before the coin-tosses. Then, both $|T^R|$ and $|T^G|$ are expected to be near $|T|/2$. The difference between them 
can be bounded using standard concentration inequalities, e.g, by Hoeffding's inequality, with probability $1-o(1/t)$, the imbalance is $O(\sqrt{t \ln t})$.

*The hard case is when $T$ can depend on the coloring in an arbitrary way. Then, no non-trivial upper bound exists. For example, an adversary can select $T$ to contain $t$ red subjects. In this case, $T^R=T$ and $T^L=\emptyset$ and the difference between their sizes is $t$, which is as large as can be.


I am are interested in an intermediate case, in which $T$ may depend on the coloring but only in a restricted way. As an example, suppose all the subjects in $O$ are placed on the real line, and $T$ must be an interval. $T$ may depend on the coloring, so it is a random variable and the standard concentration inequalities do not apply. However, the restriction to an interval means that an adversary cannot always select $T$ to contain $t$ red subjects. Therefore we may hope to have a non-trivial upper bound on the imbalance $\abs{|T^R|-|T^G|}$.
In this draft, I developed some high-probability concentration inequalities for some families of random-sets (including the interval case and some generalizations). I thought of submitting it for publication in some letters journal, but then I had a feeling that this might be a known result. 
So, my question is: what are some known concentration inequalities for random sets?
 A: I think a keyword to help you here is Rademacher Complexity.  Learning theorists know a lot about these kinds of questions.  In particular, for the intervals-on-a-line case, the high-probability bound for the maximum discrepancy should be $O(1/\sqrt{n})$, where $n =  |O|$.  More generally, if $O \subset \mathbb{R}^d$ and $T$ must be the intersection of $O$ with a halfspace, the bound should be $O(\sqrt{d/n})$, I think.  [I could be mistaken here, I didn't look at the details very carefully.]
A: To follow up on Ryan's answer, the combinatorial notion of VC-dimension characterizes the maximal deviation of an empirical average from the true mean. See my course notes here:
https://www.cs.bgu.ac.il/~asml162/Class_Material
in particular, lectures 05-05-2016--09-06-2016.
A: I'll combine Ryan's answer and my elaboration of it into a single (hopefully, coherent) answer.
I'll represent Erel's random R/G coloring as the assignment of a random $\sigma_i\in\{-1,1\}$ to each point $x_i\in O$. Put $n:=|O|$. I'll represent the set $T$ as a function $f:O\to\{0,1\}$, where $f$ is the characteristic (indicator) function of $T$. Finally, I'll represent by $F$ the collection of all permissible functions $f$. Erel's quantity of interest is
$$ \mathbb{E} \max_{f\in F} \sum_{i=1}^{n}\sigma_i f(x_i) \qquad (*).$$
(Now, Erel actually cares about the right tail of the random variable $\max_{f\in F} \sum_{i=1}^{n}\sigma_i f(x_i)$, but the latter is concentrated about the mean by McDiarmid's inequality -- so it suffices to bound the mean.) Up to a normalizing factor of $n$, the expression $(*)$ is just the Rademacher complexity of $F$, as Ryan pointed out. The latter can be bounded by the VC-dimension of $F$: denoting the latter by $D$, an upper bound on $(*)$ is
$ \Theta(\sqrt{nD})$
as shown, e.g., in my lecture notes.
