A Tighter Relation Between Hereditary Discrepancy and Determinant Lower Bound

Abstract

In seminal work, Lovász, Spencer, and Vesztergombi [European J. Combin., 1986] proved a lower bound for the hereditary discrepancy of a matrix $A\in {\mathbb{R}}^{m\times n}$ in terms of the maximum $|\det (B){|}^{1/k}$ over all $k\times k$ submatrices $B$ of $A$. We show algorithmically that this determinant lower bound can be off by at most a factor of $O(\sqrt{\log (m)\cdot \log (n)})$, improving over the previous bound of $O(\log (mn)\cdot \sqrt{\log (n)})$ given by Matoušek [Proc. of the AMS, 2013]. Our result immediately implies $\mathrm{herdisc}({\mathcal{F}}_1\cup {\mathcal{F}}_2)\le O(\sqrt{\log (m)\cdot \log (n)})\cdot \max (\mathrm{herdisc}({\mathcal{F}}_1),\mathrm{herdisc}({\mathcal{F}}_2))$, for any two set systems ${\mathcal{F}}_1,{\mathcal{F}}_2$ over $[n]$ satisfying $|{\mathcal{F}}_1\cup {\mathcal{F}}_2|=m$. Our bounds are tight up to constants when $m=O(\mathrm{poly}(n))$ due to a construction of Pálvölgyi [Discrete Comput. Geom., 2010] or the counterexample to Beck's three permutation conjecture by Newman, Neiman and Nikolov [FOCS, 2012].

To appear in SOSA 2022. 8 pages