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?)

  • [Ban10] N. Bansal.
    Constructive algorithms for discrepancy minimization., also in FOCS'10: Proc. 51st IEEE Symposium on Foundations of Computer Science, pages 3-10, 2010.
  • [BJN83] P.B. Bhattacharya, S.K. Jain, and S.R. Nagpaul.
    First course in linear algebra.
    Wiley Eastern Limited, New Delhi, 1983. MR 719018 (84m:15001)
  • [BS95] J. Beck and V. Sós.
    Discrepancy theory.
    In Handbook of Combinatorics, pages 1405-1446. North-Holland, Amsterdam, 1995. MR 1373682 (96m:11060)
  • [Duf56] R.J. Duffin.
    Infinite programs.
    In H.W. Kuhn and A.W. Tucker, editors, Linear Inequalities and Related Systems, volume 38 of Annals of Mathematical Studies, pages 157-170, 1956. MR 0087573 (19:374a)
  • [GM12] B. Gärtner and J. Matoušek,
    Approximation algorithms and semidefinite programming.
    Springer, Heidelberg, 2012.
  • [KMV05] J.-H. Kim, J. Matoušek, and V.H. Vu.
    Discrepancy after adding a single set.
    Combinatorica, 25:499-501, 2005. MR 2143253 (2006d:05180)
  • [LSV86] L. Lovász, J. Spencer, and K. Vesztergombi.
    Discrepancy of set-systems and matrices.
    European J. Combin., 7:151-160, 1986. MR 856328 (88b:05036)
  • [Mat10] J. Matoušek.
    Geometric Discrepancy (An Illustrated Guide), 2nd printing.
    Springer-Verlag, Berlin, 2010. MR 2683232 (2011h:11081)
  • [Pál10] D. Pálvölgyi.
    Indecomposable coverings with concave polygons.
    Discrete Comput. Geom., 44(3):577-588, 2010. MR 2679054 (2011f:52008)
  • [VB96] L. Vandenberghe and S. Boyd.
    Semidefinite programming.
    SIAM Rev., 38:49-95, 1996. MR 1379041 (96m:90005)

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.

American Mathematical Society