Sparse Geometric Set Systems and the Beck-Fiala Conjecture

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{(\log n+{(t^{c}g(n))}^{\frac{1}{1+c}})\log n}\right)\mathrm{.}$$ 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({(n^{c_1}g(n)t^c)}^{\frac{1}{1+c_1+c}}\right)\mathrm{.}$$ These are of independent interest.