LIPIcs.APPROX-RANDOM.2016.29.pdf
- Filesize: 458 kB
- 10 pages
Document
On the Beck-Fiala Conjecture for Random Set Systems
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-09-06
File
Document Identifiers
Cite As Get BibTex
Esther Ezra and Shachar Lovett. On the Beck-Fiala Conjecture for Random Set Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 29:1-29:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.29
Abstract
Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems (X,Sigma), where each element x in X lies in t randomly selected sets of Sigma, where t is an integer parameter. We provide new bounds in two regimes of parameters. We show that when |\Sigma| >= |X| the hereditary discrepancy of (X,Sigma) is with high probability O(sqrt{t log t}); and when |X| >> |\Sigma|^t the hereditary discrepancy of (X,Sigma) is with high probability O(1). The first bound combines the Lovasz Local Lemma with a new argument based on partial matchings; the second follows from an analysis of the lattice spanned by sparse vectors.
Subject Classification
Keywords
- Discrepancy theory
- Beck-Fiala conjecture
- Random set systems
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Noga Alon and Joel H. Spencer. The probabilistic method. Wiley-Interscience series in discrete mathematics and optimization. Wiley, New York, Chichester, Weinheim, 2000.
-
Wojciech Banaszczyk. Balancing vectors and Gaussian measures of n-dimensional convex bodies. Random Structures &Algorithms, 12(4):351-360, 1998.
-
Nikhil Bansal, Daniel Dadush, and Shashwat Garg. An algorithm for Komlós conjecture matching Banaszczyk’s bound. arXiv preprint arXiv:1605.02882, 2016.
-
József Beck and Tibor Fiala. Integer-making theorems. Discrete Applied Mathematics, 3(1):1-8, 1981.
-
Debe Bednarchak and Martin Helm. A note on the Beck-Fiala theorem. Combinatorica, 17(1):147-149, 1997.
-
Boris Bukh. An improvement of the Beck-Fiala theorem. arXiv preprint arXiv:1306.6081, 2013.
-
Bernard Chazelle. The discrepancy method: randomness and complexity. Cambridge University Press, Cambridge, New York, 2000.
-
Paul Erdös and Rényi Alfréd. On a classical problem of probability theory. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 6:215-220, 1961.
-
Paul Erdös and Laszlo Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and Finite Sets (to Paul Erdös on his 60th birthday), II:609-627, 1975.
-
Martin Helm. On the Beck-Fiala theorem. Discrete mathematics, 207(1):73-87, 1999.
-
Jiri Matoušek. Geometric discrepancy: An illustrated guide, volume 18. Springer Science &Business Media, 2009.
-
Robin A Moser. A constructive proof of the Lovász local lemma. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 343-350. ACM, 2009.
-
Robin A Moser and Gábor Tardos. A constructive proof of the general Lovász local lemma. Journal of the ACM (JACM), 57(2):11, 2010.
-
Joel Spencer. Six standard deviations suffice. Transactions of the American Mathematical Society, 289(2):679-706, 1985.
-
Richard M. Wilson. A diagonal form for the incidence matrices of t-subsets vs. k-subsets. European Journal of Combinatorics, 11(6):609-615, 1990.