Sparse Geometric Set Systems and the Beck-Fiala Conjecture

Abstract

We investigate the combinatorial discrepancy of geometric set systems having bounded shallow cell complexity in the \emph{Beck-Fiala} setting, where each point belongs to at most $t$ ranges. For set systems with shallow cell complexity $\psi (m,k)=g(m)k^c$, where $(i)$ $g(m)=o(m^{\epsilon })$ for any $\epsilon \in (0,1],$ $(ii)$ $\psi$ is non-decreasing in $m$, and $(iii)$ $c>0$ is independent of $m$ and $k$, we get a discrepancy bound of \[ O\left(\sqrt{\left(\log n+\left(t^{c}g(n)\right)^{\frac{1}{1+c}}\right)\log n}\right).\] For $t=\omega ({\log }^{2}n)$, in several cases, such as for set systems of points and half-planes / disks / pseudo-disks in ${\mathbb{R}}^2$, points and orthants in ${\mathbb{R}}^3$ etc., these bounds are $o(\sqrt{t})$, which verifies (and improves upon) the conjectured bound of Beck and Fiala~\emph{(Disc. Appl. Math., 1981)}. Our bounds are obtained by showing the existence of \emph{matchings with low crossing number}, using the multiplicative weights update method of Welzl \emph{(SoCG, 1988)}, together with the recent bound of Mustafa \emph{(Disc. Comp. Geom., 2015)} on \emph{shallow packings} of set systems in terms of their shallow cell complexity. For set systems of shallow cell complexity $\psi (m,k)=m^{c_1}g(m)k^c$, we obtain matchings with crossing number at most \[ O\left(\left(n^{c_1}g(n)t^{c}\right)^{\frac{1}{1+c_1+c}}\right).\] These are of independent interest.