Paper detail

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 $ψ(m,k)=g(m)k^{c}$, where $(i)$ $g(m) = o(m^{\varepsilon})$ for any $\varepsilon\in (0,1],$ $(ii)$ $ψ$ 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=ω(\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 $ψ(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.