= Discrepancy theory
{title2=$\operatorname{disc}(\mathcal F)$}
Discrepancy theory measures how evenly a finite configuration or coloring can satisfy many constraints at once. For a finite <set> $X$ and a family $\mathcal F$ of <subsets>, its two-color discrepancy is
$$
\operatorname{disc}(\mathcal F)=\min_{\chi:X\to\{-1,1\}}\max_{S\in\mathcal F}\left|\sum_{x\in S}\chi(x)\right|.
$$
The sum is the difference between the two color counts in $S$. A single balanced total does not guarantee small discrepancy on every constrained <subset>.
If $X=\{1,\ldots,n\}$ and $\mathcal F$ contains all contiguous intervals, alternating the colors gives discrepancy at most one: each even-length interval has equal counts, and each odd-length interval differs by one. Singleton constraints show that one is optimal. More complicated overlapping families can force much larger imbalance.
A related geometric formulation compares point counts in test regions with their expected volume. <Star discrepancy> uses boxes anchored at the origin. Such bounds quantify how well a deterministic point set approximates uniform integration, linking <combinatorics> with <numerical integration>.
Back to article page
