The determinant bound for discrepancy is almost tight

2011/01/04 by Jiřı́ Matoušek, Jiri Matousek, Matousek, Jiri · 2 citations
Mathematics · #Mathematical Approximation and Integration #math.CO #msc:05B20 #msc:05D99

paper · pdf · doi:10.48550/arxiv.1101.0767

9 pages

arxiv created 2011/07/06 · arxiv updated 2011/07/07

Abstract

In 1986 Lovasz, Spencer, and Vesztergombi proved a lower bound for the hereditary a discrepancy of a set system F in terms of determinants of square submatrices of the incidence matrix of F. As shown by an example of Hoffman, this bound can differ from herdisc(F) by a multiplicative factor of order almost log n, where n is the size of the ground set of F. We prove that it never differs by more than O((log n)3/2), assuming |F| bounded by a polynomial in n. We also prove that if such an F is the union of t systems F₁, . . ., F_t, each of hereditary discrepancy at most D, then herdisc(F) ≤ O(t^(1/2)(log n)^(3/2) D). For t = 2, this almost answers a question of Sos. The proof is based on a recent algorithmic result of Bansal, which computes low-discrepancy colorings using semidefinite programming.

Cited by

• Coloring Geometric Hypergraphs: A Survey
• Diagonal Frobenius Number via Gomory's Relaxation and Discrepancy

Related

• A Tighter Relation Between Hereditary Discrepancy and Determinant Lower Bound
• On the Gap between Hereditary Discrepancy and the Determinant Lower Bound
• Factorization Norms and Hereditary Discrepancy
• Fast Discrepancy Minimization with Hereditary Guarantees
• Constructive Discrepancy Minimization with Hereditary L2 Guarantees