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,\mathrm{\Sigma })$, where each element $x\in X$ lies in $t$ randomly selected sets of $\mathrm{\Sigma }$, where $t$ is an integer parameter. We provide new bounds in two regimes of parameters. We show that when $\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }\ge \mathrm{\mid }X\mathrm{\mid }$ the hereditary discrepancy of $(X,\mathrm{\Sigma })$ is with high probability $O(\sqrt{t\log t})$; and when $|X| \gg |\Sigma|^t$thehereditarydiscrepancyof$(X,\Sigma)$iswithhighprobability$O(1)$. The first bound combines the Lov{'a}sz Local Lemma with a new argument based on partial matchings; the second follows from an analysis of the lattice spanned by sparse vectors.