Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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
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

DOI: http://dx.doi.org/10.1090/S0002-9939-2012-11334-6
PII: S 0002-9939(2012)11334-6
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.