On the Gap between Hereditary Discrepancy and the Determinant Lower BoundThe determinant lower bound of Lovasz, Spencer, and Vesztergombi [European
Journal of Combinatorics, 1986] is a powerful general way to prove lower bounds
on the hereditary discrepancy of a set system. In their paper, Lovasz, Spencer,
and Vesztergombi asked if hereditary discrepancy can also be bounded from above
by a function of the hereditary discrepancy. This was answered in the negative
by Hoffman, and the largest known multiplicative gap between the two quantities
for a set system of $m$ substes of a universe of size $n$ is on the order of
$\max\{\log n, \sqrt{\log m}\}$. On the other hand, building on work of
Matoušek [Proceedings of the AMS, 2013], recently Jiang and Reis [SOSA,
2022] showed that this gap is always bounded up to constants by
$\sqrt{\log(m)\log(n)}$. This is tight when $m$ is polynomial in $n$, but
leaves open what happens for large $m$. We show that the bound of Jiang and
Reis is tight for nearly the entire range of $m$. Our proof relies on a
technique of amplifying discrepancy via taking Kronecker products, and on
discrepancy lower bounds for a set system derived from the discrete Haar basis.
arxiv.org