Premium
On the Beck‐Fiala conjecture for random set systems
Author(s) -
Ezra Esther,
Lovett Shachar
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20810
Subject(s) - conjecture , mathematics , combinatorics , discrete mathematics , set (abstract data type) , integer (computer science) , lattice (music) , computer science , physics , acoustics , programming language
Motivated by the Beck‐Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems ( X ,Σ), where each element x ∈ X lies in t randomly selected sets of Σ, where t is an integer parameter. We provide new bounds in two regimes of parameters. We show that when |Σ| ≥ | X | the hereditary discrepancy of ( X ,Σ) is with high probability O ( t log t ) ; and when | X | ≫ |Σ| t the hereditary discrepancy of ( X ,Σ) is with high probability O (1). The first bound combines the Lovász Local Lemma with a new argument based on partial matchings; the second follows from an analysis of the lattice spanned by sparse vectors.