Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society, the Proceedings of the American Mathematical Society (PROC) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

The determinant bound for discrepancy is almost tight
HTML articles powered by AMS MathViewer

by Jiří Matoušek PDF
Proc. Amer. Math. Soc. 141 (2013), 451-460 Request permission

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
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
  • © Copyright 2012 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Proc. Amer. Math. Soc. 141 (2013), 451-460
  • MSC (2010): Primary 05D99
  • DOI: https://doi.org/10.1090/S0002-9939-2012-11334-6
  • MathSciNet review: 2996949