Discrepancy of hypergraphs

1. For any hypergraph ${\displaystyle {\mathcal {H}}}$ with n vertices and m edges:

• ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq {\sqrt {2n\ln(2m)}}.}$

The proof is a simple application of the probabilistic method: Let ${\displaystyle \chi :V\rightarrow \{-1,1\}}$ be a random coloring, i.e. we have

${\displaystyle \Pr(\chi (v)=-1)=\Pr(\chi (v)=1)={\frac {1}{2}}}$

independently for all ${\displaystyle v\in V}$. Since ${\displaystyle \chi (E)=\sum _{v\in E}\chi (v)}$ is a sum of independent −1, 1 random variables. So we have ${\displaystyle \Pr(|\chi (E)|>\lambda )<2\exp(-\lambda ^{2}/(2n))}$ for all ${\displaystyle E\subseteq V}$ and ${\displaystyle \lambda \geq 0}$. Put ${\displaystyle \lambda ={\sqrt {2n\ln(2m)}}}$ for convenience. Then

${\displaystyle \Pr(\operatorname {disc} ({\mathcal {H}},\chi )>\lambda )\leq \sum _{E\in {\mathcal {E}}}\Pr(|\chi (E)|>\lambda )<1.}$

Since a random coloring with positive probability has discrepancy at most ${\displaystyle \lambda }$, in particular, there are colorings that have discrepancy at most ${\displaystyle \lambda }$. Hence ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq \lambda .\ \Box }$

2. For any hypergraph ${\displaystyle {\mathcal {H}}}$ with n vertices and m edges such that ${\displaystyle m\geq n}$:

• ${\displaystyle \operatorname {disc} ({\mathcal {H}})\in O({\sqrt {n}}).}$

To prove this, a much more sophisticated approach using the entropy function was necessary. Of course this is particularly interesting for ${\displaystyle m=O(n)}$. In the case ${\displaystyle m=n}$, ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq 6{\sqrt {n}}}$ 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]

If each vertex of ${\displaystyle {\mathcal {H}}}$ is contained in at most t edges, then

${\displaystyle \operatorname {disc} ({\mathcal {H}})<2t}$.

This result, the Beck–Fiala theorem, is due to Beck and Fiala.[8] They bound the discrepancy by the maximum degree of ${\displaystyle {\mathcal {H}}}$. It is a famous open problem whether this bound can be improved asymptotically (modified versions of the original proof give 2t−1 or even 2t−3).

Beck and Fiala conjectured that ${\displaystyle \operatorname {disc} ({\mathcal {H}})=O({\sqrt {t}})}$, but little progress has been made so far in this direction. Bednarchak and Helm[9] and Helm[10] improved the Beck-Fiala bound in tiny steps to ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq 2t-3}$ (for a slightly restricted situation, i.e. ${\displaystyle t\geq 3}$). Bukh[11] improved this in 2016 to ${\displaystyle 2t-\log ^{*}t}$, where ${\displaystyle \log ^{*}t}$ denotes the iterated logarithm. A corollary of Beck's paper[1] – the first time the notion of discrepancy explicitly appeared – shows ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq C{\sqrt {t\log m}}\log n}$ for some constant C. The latest improvement in this direction is due to Banaszczyk:[12] ${\displaystyle \operatorname {disc} ({\mathcal {H}})=O({\sqrt {t\log n}})}$.

Suppose p₁, ...,p_m are permutations of [n]. Suppose ${\displaystyle {\mathcal {H}}}$ is the hypergraph on [n] whose edges are all the intervals of every permutation. For example, if one of the permutations is (1,2,3,4), then the hypergraph ${\displaystyle {\mathcal {H}}}$ contains e.g. the edges (1,2), (1,2,3), (2,3), (2,3,4), etc. The discrepancy of ${\displaystyle {\mathcal {H}}}$ is the minimum over all red-blue colorings of the integers in [n], of the maximum over all intervals, of the difference between the number of red and blue integers in the interval. Then:

• For any two permutations, ${\displaystyle \operatorname {disc} ({\mathcal {H}})=2}$.
• For any m permutations, ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq 8m\log {n}}$, and such a coloring can be computed efficiently.[13]
• For any three permutations, Beck conjectures that ${\displaystyle \operatorname {disc} ({\mathcal {H}})={\text{constant}}}$. However, this conjecture was refuted: for any n which is a power of 3, there exist 3 permutations whose discrepancy is ${\displaystyle \lceil (\log _{3}{n})/3+1\rceil }$. More precisely, for any {1,-1} coloring, if the sum of all colors is d, then there exists some integer q such that, in all three permutations, the sum of the first q colors is at most ${\displaystyle (-\log _{3}{n}+2d-2)/3}$.[14]^: Cor.2 This has implications for the bin packing problem.

• Axis-parallel rectangles in the plane (Roth, Schmidt)
• Discrepancy of half-planes (Alexander, Matoušek)
• Arithmetic progressions (Roth, Sárközy, Beck, Matoušek & Spencer)
• Six Standard Deviations Suffice (Spencer)