Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-10T09:45:32.212Z Has data issue: false hasContentIssue false
  • English
  • Français

An Improvement of the Beck–Fiala Theorem

Part of: Probabilistic theory: distribution modulo $1$; metric theory of algorithms Extremal combinatorics Graph theory

Published online by Cambridge University Press:  06 July 2015

BORIS BUKH
BORIS BUKH*
Affiliation:
Department of Mathematical Sciences, Wean Hall 6113, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: bbukh@math.cmu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In 1981 Beck and Fiala proved an upper bound for the discrepancy of a set system of degree d that is independent of the size of the ground set. In the intervening years the bound has been decreased from 2d − 2 to 2d − 4. We improve the bound to 2d − log*d.

MSC classification

Primary: 05D05: Extremal set theory
Secondary: 11K38: Irregularities of distribution, discrepancy 05C15: Coloring of graphs and hypergraphs

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 3 , May 2016 , pp. 380 - 398
Copyright
Copyright © Cambridge University Press 2015 

References

[1] Banaszczyk, W. (1998) Balancing vectors and Gaussian measures of n-dimensional convex bodies. Random Struct. Alg. 12 351–360.Google Scholar
[2] Beck, J. and Fiala, T. (1981) ‘Integer-making’ theorems. Discrete Appl. Math. 3 1–8.Google Scholar
[3] Bednarchak, D. and Helm, M. (1997) A note on the Beck–Fiala theorem. Combinatorica 17 147–149.Google Scholar
[4] Chazelle, B. (2000) The Discrepancy Method, Cambridge University Press.Google Scholar
[5] Helm, M. (1999) On the Beck–Fiala theorem. Discrete Math. 207 73–87.CrossRefGoogle Scholar
[6] Matoušek, J. (2010) Geometric Discrepancy , Vol. 18 of Algorithms and Combinatorics, Springer. An illustrated guide, Revised paperback reprint of the 1999 original.Google Scholar
[7] Nikolov, A. (2013) The Komlós conjecture holds for vector colorings. arXiv:1301.4039v2 Google Scholar
[8] Spencer, J. (1985) Six standard deviations suffice. Trans. Amer. Math. Soc. 289 679–706.Google Scholar