On the Beck-Fiala Conjecture for Random Set Systems

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 \in 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 $|Σ| \ge |X|$ the hereditary discrepancy of $(X,Σ)$ is with high probability $O(\sqrt{t \log t})$; and when $|X| \gg |Σ|^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.

No reviews yet.

No comments yet.