The determinant bound for discrepancy is almost tight

Abstract:

In 1986 Lovász, Spencer, and Vesztergombi proved a lower bound for the hereditary discrepancy of a set system $\mathcal {F}$ in terms of determinants of square submatrices of the incidence matrix of $\mathcal {F}$. As shown by an example of Hoffman, this bound can differ from $\mathrm {herdisc}(\mathcal {F})$ by a multiplicative factor of order almost $\log n$, where $n$ is the size of the ground set of $\mathcal {F}$. We prove that it never differs by more than $O((\log n)^{3/2})$, assuming $|\mathcal {F}|$ bounded by a polynomial in $n$. We also prove that if such an $\mathcal {F}$ is the union of $t$ systems $\mathcal {F}_1,\ldots ,\mathcal {F}_t$, each of hereditary discrepancy at most $D$, then $\mathrm {herdisc}(\mathcal {F})\le O(\sqrt t (\log n)^{3/2}D)$. For $t=2$, this almost answers a question of Sós. The proof is based on a recent algorithmic result of Bansal, which computes low-discrepancy colorings using semidefinite programming.