Discrepancy of hypergraphs

From HandWiki

Discrepancy of hypergraphs is an area of discrepancy theory.

Definitions

In the classical setting, we aim at partitioning the vertices of a hypergraph [math]\displaystyle{ \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]\displaystyle{ \chi \colon V \rightarrow \{-1, +1\} }[/math]. We call −1 and +1 colors. The color-classes [math]\displaystyle{ \chi^{-1}(-1) }[/math] and [math]\displaystyle{ \chi^{-1}(+1) }[/math] form the corresponding partition. For a hyperedge [math]\displaystyle{ E \in \mathcal{E} }[/math], set

[math]\displaystyle{ \chi(E) := \sum_{v\in E} \chi(v). }[/math]

The discrepancy of [math]\displaystyle{ \mathcal{H} }[/math] with respect to [math]\displaystyle{ \chi }[/math] and the discrepancy of [math]\displaystyle{ \mathcal{H} }[/math] are defined by

[math]\displaystyle{ \operatorname{disc}(\mathcal{H},\chi) := \; \max_{E \in \mathcal{E}} |\chi(E)|, }[/math]
[math]\displaystyle{ \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 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 (described on p. 39).[5] 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.

  • If all edges of [math]\displaystyle{ \mathcal{H} }[/math] intersect trivially, i.e. [math]\displaystyle{ E_1 \cap E_2 = \varnothing }[/math] for any two distinct edges [math]\displaystyle{ 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]\displaystyle{ (V, 2^V) }[/math]. In this case the discrepancy is [math]\displaystyle{ \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]\displaystyle{ \chi }[/math] with color classes of size [math]\displaystyle{ \lceil \frac{1}{2} |V|\rceil }[/math] and [math]\displaystyle{ \lfloor \frac{1}{2} |V|\rfloor }[/math] proves that the discrepancy is not larger than [math]\displaystyle{ \lceil \frac{1}{2} |V|\rceil }[/math]. It seems that the discrepancy reflects how chaotic the hyperedges of [math]\displaystyle{ \mathcal{H} }[/math] intersect. Things are not that easy, however, as the following example shows.
  • Set [math]\displaystyle{ n=4k }[/math], [math]\displaystyle{ k \in \mathcal{N} }[/math] and [math]\displaystyle{ \mathcal{H}_n = ([n], \{E \subseteq [n] \mid | E \cap [2k]| = | E \setminus [2k]|\}) }[/math]. In words, [math]\displaystyle{ \mathcal{H}_n }[/math] 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}. Now [math]\displaystyle{ \mathcal{H}_n }[/math] has many (more than [math]\displaystyle{ \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,...,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.

Bounds on the discrepancy

General hypergraphs

1. For any hypergraph [math]\displaystyle{ \mathcal{H} }[/math] with n vertices and m edges:

  • [math]\displaystyle{ \operatorname{disc}(\mathcal{H}) \leq \sqrt{2n \ln (2m)}. }[/math]

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

[math]\displaystyle{ \Pr(\chi(v) = -1) = \Pr(\chi(v) = 1) = \frac{1}{2} }[/math]

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

[math]\displaystyle{ \Pr(\operatorname{disc}(\mathcal{H},\chi)\gt \lambda) \leq \sum_{E \in \mathcal{E}} \Pr(|\chi(E)| \gt \lambda) \lt 1. }[/math]

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

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

  • [math]\displaystyle{ \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]\displaystyle{ m = O(n) }[/math]. In the case [math]\displaystyle{ m=n }[/math], [math]\displaystyle{ \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 Matoušek and Spencer[6] or the upper bound in terms of the primal shatter function due to Matoušek.[7]

Hypergraphs of bounded degree

If each vertex of [math]\displaystyle{ \mathcal{H} }[/math] is contained in at most t edges, then

[math]\displaystyle{ \operatorname{disc}(\mathcal{H}) \lt 2t }[/math].

This result, the Beck–Fiala theorem, is due to Beck and Fiala.[8] They bound the discrepancy by the maximum degree of [math]\displaystyle{ \mathcal{H} }[/math]. 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 [math]\displaystyle{ \operatorname{disc}(\mathcal{H}) = O(\sqrt t) }[/math], 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 [math]\displaystyle{ \operatorname{disc}(\mathcal{H}) \leq 2t - 3 }[/math] (for a slightly restricted situation, i.e. [math]\displaystyle{ t \geq 3 }[/math]). Bukh[11] improved this in 2016 to [math]\displaystyle{ 2t - \log^* t }[/math], where [math]\displaystyle{ \log^* t }[/math] denotes the iterated logarithm. A corollary of Beck's paper[1] – the first time the notion of discrepancy explicitly appeared – shows [math]\displaystyle{ \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:[12] [math]\displaystyle{ \operatorname{disc}(\mathcal{H}) = O(\sqrt{t \log n}) }[/math].

Permutations hypergraphs

Suppose p1, ...,pm are permutations of [n]. Suppose [math]\displaystyle{ \mathcal{H} }[/math] 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 [math]\displaystyle{ \mathcal{H} }[/math] contains e.g. the edges (1,2), (1,2,3), (2,3), (2,3,4), etc. The discrepancy of [math]\displaystyle{ \mathcal{H} }[/math] 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, [math]\displaystyle{ \operatorname{disc}(\mathcal{H})= 2 }[/math].
  • For any m permutations, [math]\displaystyle{ \operatorname{disc}(\mathcal{H}) \leq 8 m\log {n} }[/math], and such a coloring can be computed efficiently.[13]
  • For any three permutations, Beck conjectures that [math]\displaystyle{ \operatorname{disc}(\mathcal{H})= \text{constant} }[/math]. However, this conjecture was refuted: for any n which is a power of 3, there exist 3 permutations whose discrepancy is [math]\displaystyle{ \lceil (\log_3{n})/3 + 1 \rceil }[/math]. 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 [math]\displaystyle{ (-\log_3{n} + 2 d - 2)/3 }[/math].[14]:Cor.2 This has implications for the bin packing problem.

Other classic theorems

  • 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)

Major open problems

  • Axis-parallel rectangles in dimensions three and higher (Folklore)
  • Komlós Conjecture

Applications

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

Notes

  1. ↑ 1.0 1.1 J. Beck: "Roth's estimate of the discrepancy of integer sequences is nearly sharp", page 319-325. Combinatorica, 1, 1981
  2. ↑ K. F. Roth: "Remark concerning integer sequences", pages 257–260. Acta Arithmetica 9, 1964
  3. ↑ J. Spencer: "A remark on coloring integers", pages 43–44. Canadian Mathematical Bulletin 15, 1972.
  4. ↑ P. Erdős and J. Spencer: "Imbalances in k-colorations", pages 379–385. Networks 1, 1972.
  5. ↑ P. Erdős and J. Spencer: "Probabilistic Methods in Combinatorics." Budapest: Akadémiai Kiadó, 1974.
  6. ↑ J. Matoušek and J. Spencer: "Discrepancy in arithmetic progressions", pages 195–204. Journal of the American Mathematical Society 9, 1996.
  7. ↑ J. Matoušek: "Tight upper bound for the discrepancy of half-spaces", pages 593–601. Discrepancy and Computational Geometry 13, 1995.
  8. ↑ J. Beck and T. Fiala: "Integer making theorems", pages 1–8. Discrete Applied Mathematics 3, 1981.
  9. ↑ D. Bednarchak and M. Helm: "A note on the Beck-Fiala theorem", pages 147–149. Combinatorica 17, 1997.
  10. ↑ M. Helm: "On the Beck-Fiala theorem", page 207. Discrete Mathematics 207, 1999.
  11. ↑ B. Bukh: "An Improvement of the Beck–Fiala Theorem", pp. 380-398. Combinatorics, Probability and Computing 25, 2016.
  12. ↑ 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.
  13. ↑ Bohus, Géza (1990). "On the discrepancy of 3 permutations" (in en). Random Structures & Algorithms 1 (2): 215–220. doi:10.1002/rsa.3240010208. ISSN 1098-2418. https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240010208. 
  14. ↑ Newman, A.; Neiman, O.; Nikolov, A. (2012-10-01). "Beck's Three Permutations Conjecture: A Counterexample and Some Consequences". 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. pp. 253–262. doi:10.1109/FOCS.2012.84. ISBN 978-0-7695-4874-6. https://ieeexplore.ieee.org/document/6375303. 

References

  • Beck, József; Chen, William W. L. (2009). Irregularities of Distribution. Cambridge University Press. ISBN 978-0-521-09300-2. 
  • Chazelle, Bernard (2000). The Discrepancy Method: Randomness and Complexity. Cambridge University Press. ISBN 0-521-77093-9. https://archive.org/details/discrepancymetho0000chaz. 
  • Doerr, Benjamin (2005). Integral Approximation (PDF) (Habilitation thesis). University of Kiel. OCLC 255383176. Retrieved 20 October 2019.
  • Matoušek, Jiří (1999). Geometric Discrepancy: An Illustrated Guide. Springer. ISBN 3-540-65528-X. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Discrepancy_of_hypergraphs&oldid=3388050"