View source for Discrepancy of hypergraphs

{{Short description|Area of discrepancy theory}}
'''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 [[Vertex (graph theory)|vertices]] of a [[hypergraph]] <math>\mathcal{H}=(V, \mathcal{E})</math> 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 <math>\chi \colon V \rightarrow \{-1, +1\}</math>. We call −1 and +1 ''colors''. The color-classes <math>\chi^{-1}(-1)</math> and <math>\chi^{-1}(+1)</math> form the corresponding partition. For a hyperedge <math>E \in \mathcal{E}</math>, set
:<math>\chi(E) := \sum_{v\in E} \chi(v).</math>
The ''discrepancy of <math>\mathcal{H}</math> with respect to <math>\chi</math>'' and the ''discrepancy of <math>\mathcal{H}</math>'' are defined by
:<math>\operatorname{disc}(\mathcal{H},\chi) := \; \max_{E \in \mathcal{E}} |\chi(E)|,</math>
:<math>\operatorname{disc}(\mathcal{H}) := \min_{\chi:V\rightarrow\{-1,+1\}} \operatorname{disc}(\mathcal{H}, \chi).</math>
These notions as well as the term 'discrepancy' seem to have appeared for the first time in a paper of [[József Beck|Beck]].<ref name="beck_roth_estimate">J. Beck: "Roth's estimate of the discrepancy of integer sequences is nearly sharp", page 319-325. [[Combinatorica]], 1, 1981</ref> Earlier results on this problem include the famous lower bound on the discrepancy of arithmetic progressions by Roth<ref>K. F. Roth: "Remark concerning integer sequences", pages 257–260. [[Acta Arithmetica]] 9, 1964</ref> and upper bounds for this problem and other results by [[Paul Erdős|Erdős]] and Spencer<ref>J. Spencer: "A remark on coloring integers", pages 43–44. [[Canadian Mathematical Bulletin]] 15, 1972.</ref><ref>P. Erdős and J. Spencer: "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.210.7286&rep=rep1&type=pdf Imbalances in k-colorations]", pages 379–385. Networks 1, 1972.</ref> and Sárközi.<ref>P. Erdős and J. Spencer: "Probabilistic Methods in Combinatorics."  Budapest: [[Akadémiai Kiadó]], 1974.</ref>{{Rp|page=39}} At that time, discrepancy problems were called ''quasi-[[Ramsey theory|Ramsey]] problems''.

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

* If all edges of <math>\mathcal{H}</math> intersect trivially, i.e. <math>E_1 \cap E_2 = \varnothing</math> for any two distinct edges <math>E_1, E_2 \in \mathcal{E}</math>, 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'' <math>(V, 2^V)</math>. In this case the discrepancy is <math>\lceil \frac{1}{2} |V|\rceil</math>. Any 2-coloring will have a color class of at least this size, and this set is also an edge. On the other hand, any coloring <math>\chi</math> with color classes of size <math>\lceil \frac{1}{2} |V|\rceil</math> and <math>\lfloor \frac{1}{2} |V|\rfloor</math> proves that the discrepancy is not larger than <math>\lceil \frac{1}{2} |V|\rceil</math>. It seems that the discrepancy reflects how chaotic the hyperedges of <math>\mathcal{H}</math> intersect. Things are not that easy, however, as the following example shows.
* Set <math>n=4k</math>, <math>k \in \mathcal{N}</math> and <math>\mathcal{H}_n = ([n], \{E \subseteq [n] \mid | E \cap [2k]| = | E \setminus [2k]|\})</math>. In words, <math>\mathcal{H}_n</math> is the hypergraph on 4''k'' vertices {1,...,4''k''}, whose edges are all subsets that have the same number of elements in {1,...,2''k''} as in {2''k''+1,...,4''k''}. Now <math>\mathcal{H}_n</math> has many (more than <math>\binom{n/2}{n/4}^2 = \Theta(\frac 1 n 2^n)</math>) complicatedly intersecting edges. However, its discrepancy is zero, since we can color {1,...,2''k''} in one color and {2''k''+1,...,4''k''} 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  ''<math>\mathcal{H}</math> '' with ''n'' vertices and ''m'' edges:
*<math>\operatorname{disc}(\mathcal{H}) \leq \sqrt{2n \ln (2m)}.</math>
The proof is a simple application of the probabilistic method. Let <math>\chi:V \rightarrow \{-1,1\}</math> be a random coloring, i.e. we have
:<math>\Pr(\chi(v) = -1) = \Pr(\chi(v) = 1) = \frac{1}{2}</math>
independently for all <math>v \in V</math>. Since <math>\chi(E) = \sum_{v \in E} \chi(v)</math> is a sum of independent −1, 1 random variables. So we have <math>\Pr(|\chi(E)|>\lambda)<2 \exp(-\lambda^2/(2n))</math> for all <math>E \subseteq V</math> and <math>\lambda \geq 0</math>. Taking <math>\lambda = \sqrt{2n \ln (2m)}</math> gives
:<math>\Pr(\operatorname{disc}(\mathcal{H},\chi)> \lambda) \leq \sum_{E \in \mathcal{E}} \Pr(|\chi(E)| > \lambda) < 1.</math>
Since a random coloring with positive probability has discrepancy at most <math>\lambda</math>, in particular, there are colorings that have discrepancy at most <math>\lambda</math>. Hence <math>\operatorname{disc}(\mathcal{H}) \leq \lambda. \  \Box</math>

'''2.''' For any hypergraph  ''<math>\mathcal{H}</math>  ''with ''n'' vertices and ''m'' edges ''such that <math>m \geq n</math>:''

* ''<math>\operatorname{disc}(\mathcal{H}) \in  O(\sqrt{n}).</math>''

To prove this, a much more sophisticated approach using the entropy function was necessary.
Of course this is particularly interesting for <math>m = O(n)</math>. In the case <math>m=n</math>, <math>\operatorname{disc}(\mathcal{H}) \leq 6 \sqrt{n}</math> 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 [[Jiří Matoušek (mathematician)|Matoušek]] and Spencer<ref>J. Matoušek and J. Spencer: "Discrepancy in arithmetic progressions", pages 195–204. [[Journal of the American Mathematical Society]] 9, 1996.</ref> or the upper bound in terms of the primal shatter function due to Matoušek.<ref>J. Matoušek: "Tight upper bound for the discrepancy of half-spaces", pages 593–601. Discrepancy and Computational Geometry 13, 1995.</ref>

== Hypergraphs of bounded degree ==
Better discrepancy bounds can be attained when the hypergraph has a ''bounded degree'', that is, each vertex of <math>\mathcal{H}</math> is contained in at most ''t'' edges, for some small ''t''. In particular:

* Beck and Fiala<ref>J. Beck and T. Fiala: "Integer making theorems", pages 1–8. [[Discrete Applied Mathematics]] 3, 1981.</ref> proved that <math>\operatorname{disc}(\mathcal{H}) < 2t</math>; this is known as the [[Beck–Fiala theorem]]. They conjectured that <math>\operatorname{disc}(\mathcal{H}) = O(\sqrt t)</math>.
* Bednarchak and Helm<ref>D. Bednarchak and M. Helm: "A note on the Beck-Fiala theorem", pages 147–149. [[Combinatorica]] 17, 1997.</ref> and Helm<ref>M. Helm: "On the Beck-Fiala theorem", page 207.  [[Discrete Mathematics (journal)|Discrete Mathematics]] 207, 1999.</ref> improved the Beck-Fiala bound in tiny steps to <math>\operatorname{disc}(\mathcal{H}) \leq 2t - 3</math> (for a slightly restricted situation, i.e. <math> t \geq 3 </math>).
* Bukh<ref>B. Bukh: "An Improvement of the Beck–Fiala Theorem", pp. 380-398.  [[Combinatorics, Probability and Computing]] 25, 2016.</ref> improved this in 2016 to <math>2t - \log^* t</math>, where <math>\log^* t</math> denotes the [[iterated logarithm]].
* A corollary of Beck's paper<ref name="beck_roth_estimate" /> – the first time the notion of discrepancy explicitly appeared – shows <math>\operatorname{disc}(\mathcal{H}) \leq C \sqrt{t \log m} \log n</math> for some constant C.
* The latest improvement in this direction is due to Banaszczyk:<ref>Banaszczyk, W. (1998), "Balancing vectors and Gaussian measure of ''n''-dimensional convex bodies", ''Random Structures & Algorithms'', 12: 351–360, {{doi|10.1002/(SICI)1098-2418(199807)12:4<351::AID-RSA3>3.0.CO;2-S}}.</ref> <math>\operatorname{disc}(\mathcal{H}) = O(\sqrt{t \log n})</math>.

== 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, [[Jozsef Beck|Beck]], Matoušek & [[Joel Spencer|Spencer]])
* Six Standard Deviations Suffice (Spencer)

== Major open problems ==

* [[Komlós Conjecture]]<ref>{{Cite journal |last=Bansal |first=Nikhil |last2=Dadush |first2=Daniel |last3=Garg |first3=Shashwat |date=January 2019 |title=An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound |url=https://epubs.siam.org/doi/10.1137/17M1126795 |journal=SIAM Journal on Computing |language=en |volume=48 |issue=2 |pages=534–553 |doi=10.1137/17M1126795 |issn=0097-5397}}</ref>

== Applications ==

* Numerical Integration: Monte Carlo methods in high dimensions.
* Computational Geometry: [[Divide and conquer algorithms]].
* Image Processing: Halftoning

== Notes ==

<references/>

== References ==
* {{cite book|title=Irregularities of Distribution|last1=Beck|first1=József|author1-link=József Beck|last2=Chen|first2=William W. L.|publisher=Cambridge University Press|year=2009|isbn=978-0-521-09300-2}}
* {{cite book|title=The Discrepancy Method: Randomness and Complexity|last=Chazelle|first=Bernard|author-link=Bernard Chazelle|publisher=Cambridge University Press|year=2000|isbn=0-521-77093-9|url-access=registration|url=https://archive.org/details/discrepancymetho0000chaz}}
* {{Cite thesis |degree=[[Habilitation]]|title=Integral Approximation|url=http://www.mpi-inf.mpg.de/~doerr/papers/habil.pdf |last=Doerr|first=Benjamin|year=2005|publisher=[[University of Kiel]]|accessdate= 20 October 2019|oclc= 255383176}}
* {{cite book|title=Geometric Discrepancy: An Illustrated Guide|last= Matoušek|first= Jiří|author-link=Jiří Matoušek (mathematician)|publisher=Springer|year=1999|isbn= 3-540-65528-X}}

{{DEFAULTSORT:Discrepancy Of Hypergraphs}}
[[Category:Diophantine approximation]]
[[Category:Unsolved problems in mathematics]]
[[Category:Discrepancy theory]]
[[Category:Hypergraphs]]