Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



The determinant bound for discrepancy is almost tight

Author: Jiří Matoušek
Journal: Proc. Amer. Math. Soc. 141 (2013), 451-460
MSC (2010): Primary 05D99
Published electronically: June 18, 2012
MathSciNet review: 2996949
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 $ \vert\mathcal {F}\vert$ 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05D99

Retrieve articles in all journals with MSC (2010): 05D99

Additional Information

Jiří Matoušek
Affiliation: Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic

Received by editor(s): January 4, 2011
Received by editor(s) in revised form: July 2, 2011
Published electronically: June 18, 2012
Additional Notes: The author was partially supported by the ERC Advanced Grant No. 267165.
Communicated by: Jim Haglund
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.