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 in terms of determinants of square submatrices of the incidence matrix of . As shown by an example of Hoffman, this bound can differ from by a multiplicative factor of order almost , where is the size of the ground set of . We prove that it never differs by more than , assuming bounded by a polynomial in . We also prove that if such an is the union of systems , each of hereditary discrepancy at most , then . For , 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.

**[Ban10]**N. Bansal.

Constructive algorithms for discrepancy minimization.`http://arxiv.org/abs/1002.2259`, also in*FOCS'10: Proc. 51st IEEE Symposium on Foundations of Computer Science*, pages 3-10, 2010.**[BJN83]**Phani Bhushan Bhattacharya, Surender Kumar Jain, and S. R. Nagpaul,*First course in linear algebra*, A Halsted Press Book, John Wiley & Sons, Inc., New York, 1983. MR**719018****[BS95]**József Beck and Vera T. Sós,*Discrepancy theory*, Handbook of combinatorics, Vol. 1, 2, Elsevier, Amsterdam, 1995, pp. 1405–1446. MR**1373682****[Duf56]**R. J. Duffin,*Infinite programs*, Linear inequalities and related systems, Annals of Mathematics Studies, no. 38, Princeton University Press, Princeton, N. J., 1956, pp. 157–170. MR**0087573****[GM12]**B. Gärtner and J. Matoušek,*Approximation algorithms and semidefinite programming*.

Springer, Heidelberg, 2012.**[KMV05]**Jeong Han Kim, Jiří Matoušek, and Van H. Vu,*Discrepancy after adding a single set*, Combinatorica**25**(2005), no. 4, 499–501. MR**2143253**, 10.1007/s00493-005-0030-x**[LSV86]**L. Lovász, J. Spencer, and K. Vesztergombi,*Discrepancy of set-systems and matrices*, European J. Combin.**7**(1986), no. 2, 151–160. MR**856328**, 10.1016/S0195-6698(86)80041-5**[Mat10]**Jiří Matoušek,*Geometric discrepancy*, Algorithms and Combinatorics, vol. 18, Springer-Verlag, Berlin, 2010. An illustrated guide; Revised paperback reprint of the 1999 original. MR**2683232****[Pál10]**Dömötör Pálvölgyi,*Indecomposable coverings with concave polygons*, Discrete Comput. Geom.**44**(2010), no. 3, 577–588. MR**2679054**, 10.1007/s00454-009-9194-y**[VB96]**Lieven Vandenberghe and Stephen Boyd,*Semidefinite programming*, SIAM Rev.**38**(1996), no. 1, 49–95. MR**1379041**, 10.1137/1038003

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:
https://doi.org/10.1090/S0002-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.