↑ arvau

Wikipedia / Discrepancy of hypergraphs

Discrepancy of hypergraphs is an area of discrepancy theory that studies the discrepancy of general set systems.

Definitions

In the classical setting, we aim at partitioning the vertices of a hypergraph. We call −1 and +1 colors, set

The and the are defined by

These notions as well as the term 'discrepancy' seem to have appeared for the first time in a paper of Beck. Earlier results on this problem include the famous lower bound on the discrepancy of arithmetic progressions by Roth and upper bounds for this problem and other results by Erdős and Spencer and Sárközi. At that time, discrepancy problems were called quasi-Ramsey problems.

Examples

To get some intuition for this concept, let's have a look at a few examples.

  • , then the discrepancy is zero, if all edges have even cardinality, and one, if there is an odd cardinality edge.

  • The other extreme is marked by the complete hypergraph intersect. Things are not that easy, however, as the following example shows.

  • is the hypergraph on 4k vertices {1,...,4k}, whose edges are all subsets that have the same number of elements in {1,...,2k} as in {2k+1,...,4k) complicatedly intersecting edges. However, its discrepancy is zero, since we can color {1,...,2k} in one color and {2k+1,...,4k} in another color.

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.

General hypergraphs

1. For any hypergraph with n vertices and m edges:

The proof is a simple application of the probabilistic method be a random coloring, i.e. we have

gives

2. For any hypergraph with n vertices and m edges :

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 or the upper bound in terms of the primal shatter function due to Matoušek.

Hypergraphs of bounded degree

Better discrepancy bounds can be attained when the hypergraph has a bounded degree is contained in at most t edges, for some small t. In particular:

  • Beck and Fiala; this is known as the Beck–Fiala theorem.

  • Bednarchak and Helm and Helm).

  • Bukh denotes the iterated logarithm.

  • A corollary of Beck's paper for some constant C.

  • The latest improvement in this direction is due to Banaszczyk:.

Special hypergraphs

Better bounds on the discrepancy are possible for hypergraphs with a special structure, such as:

  • Discrepancy of permutations - when the vertices are the integers 1,...,n, and the hyperedges are all the intervals of some m given permutations on the integers.

  • Geometric discrepancy - when the vertices are points in a Euclidean space, and the hyperedges are geometric objects, such as rectangles or half-spaces.

  • Arithmetic progressions (Roth, Sárközy, Beck, Matoušek & Spencer)

  • Six Standard Deviations Suffice (Spencer)

Major open problems

Applications

Notes

References