Discrepancy of hypergraphs is an area of discrepancy theory that studies the discrepancy of general set systems.
In the classical setting, we aim at partitioning the vertices of a hypergraph
into two classes in such a way that ideally each hyperedge contains the same number of vertices in both classes.
A partition into two classes can be represented by a coloring
We call −1 and +1 colors.
form the corresponding partition.
are defined by These notions as well as the term 'discrepancy' seem to have appeared for the first time in a paper of Beck.
[1] Earlier results on this problem include the famous lower bound on the discrepancy of arithmetic progressions by Roth[2] and upper bounds for this problem and other results by Erdős and Spencer[3][4] and Sárközi.
[5]: 39 At that time, discrepancy problems were called quasi-Ramsey problems.
To get some intuition for this concept, let's have a look at a few examples.
The last example shows that we cannot expect to determine the discrepancy by looking at a single parameter like the number of hyperedges.
Still, the size of the hypergraph yields first upper bounds.
with n vertices and m edges: The proof is a simple application of the probabilistic method.
be a random coloring, i.e. we have independently for all
is a sum of independent −1, 1 random variables.
> λ ) < 2 exp ( −
gives Since a random coloring with positive probability has discrepancy at most
: To prove this, a much more sophisticated approach using the entropy function was necessary.
can be shown for n large enough.
Therefore, this result is usually known to as 'Six Standard Deviations Suffice'.
It is considered to be one of the milestones of discrepancy theory.
The entropy method has seen numerous other applications, e.g. in the proof of the tight upper bound for the arithmetic progressions of Matoušek and Spencer[6] or the upper bound in terms of the primal shatter function due to Matoušek.
[7] Better discrepancy bounds can be attained when the hypergraph has a bounded degree, that is, each vertex of
is contained in at most t edges, for some small t. In particular: Better bounds on the discrepancy are possible for hypergraphs with a special structure, such as: