# Finite Playground

## Discrepancy theory

Let $(V,\mathcal{S})$ be a set system with $V = [n]$ and $\mathcal{S} \subseteq 2^{[n]}$. A ±1-coloring is a mapping $\chi : [n] \to \{1,-1\}$. The discrepancy of a set system $(V,\mathcal{S})$ is defined as

$\displaystyle{\text{disc}(S) = \min_{\chi} \{\max_{S \in \mathcal{S}} |\chi(S)|} \}$,

where $\chi(S) = \sum_{i \in S} \chi(i)$.

General bounds:
– Spencer ’85, Six standard deviations suffice, $O(\sqrt{n \log (2|\mathcal{S}|/n)})$.

If every element appears in at most $t$ sets,
– Beck-Fiala ’81, “Integer-making” theorems, $O(t)$.
– Srinivasan ’97, Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems, $O(\sqrt{t} \log n)$.
– Banaszczyk ’98, Balancing vectors and Gaussian measures of n-dimensional convex bodies, $O(\sqrt{t \log n})$.

Constructive bounds:
– Bansal ’10, Constructive algorithms for discrepancy minimization.