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 Free Access

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 $|\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.

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.