Discrepancy theory is a branch of mathematics and statistical theory that deals with the differences or discrepancies between two or more sets of data, distributions, or mathematical objects. It is often concerned with quantifying how much two sets differ from each other, which can be particularly useful in various fields such as statistics, optimization, and machine learning.
The Beck–Fiala theorem is a result in the field of combinatorial geometry, specifically concerning the covering of points by convex sets.
The discrepancy of hypergraphs is a concept in combinatorial mathematics that deals with how evenly one can color or distribute a set of points (or elements) among different subsets (or hyperedges) of a hypergraph. More formally, it is concerned with the maximum imbalance that can arise when assigning colors, typically two colors, to the vertices of the hypergraph with respect to the hyperedges.
Articles by others on the same topic
Discrepancy theory measures how evenly a finite configuration or coloring can satisfy many constraints at once. For a finite set and a family of subsets, its two-color discrepancy isThe sum is the difference between the two color counts in . A single balanced total does not guarantee small discrepancy on every constrained subset.
If and 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.