The determinant bound for discrepancy is almost tight

DOI10.1090/S0002-9939-2012-11334-6zbMATH Open1259.05179arXiv1101.0767OpenAlexW1981295892MaRDI QIDQ4908259FDOQ4908259

Authors: Jiří Matoušek 

Publication date: 5 March 2013

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

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_1, . . ., F_t, each of hereditary discrepancy at most D, then herdisc(F) leq 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.

Full work available at URL: https://arxiv.org/abs/1101.0767

Recommendations

• A Bound on Determinants
• Upper and lower bounds for matrix discrepancy
• scientific article; zbMATH DE number 166798
• Publication:4934395
• A determinantal lower bound
• Lower bounds for \(L_1\) discrepancy
• Bounds for determinants of perturbed \(M\)-matrices
• Tight upper bounds for the discrepancy of half-spaces
• Upper bounds in discrepancy theory
• scientific article; zbMATH DE number 3959557

zbMATH Keywords

semidefinite programminghereditary discrepancy of a set systemlow-discrepancy colorings

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal set theory (05D05)

Cites Work

• Semidefinite Programming
• Title not available (Why is that?)
• Geometric discrepancy. An illustrated guide
• Indecomposable coverings with concave polygons
• Approximation algorithms and semidefinite programming.
• Title not available (Why is that?)
• Discrepancy of set-systems and matrices
• Discrepancy after adding a single set
• Title not available (Why is that?)

Cited In (20)

• Approximating hereditary discrepancy via small width ellipsoids
• A trace bound for the hereditary discrepancy
• Tight hardness results for minimizing discrepancy
• A simplified disproof of Beck’s three permutations conjecture and an application to root-mean-squared discrepancy
• Minimum and maximum order of magnitude of the discrepancy of (nα)
• Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
• Semidefinite optimization in discrepancy theory
• Deterministic discrepancy minimization
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• Title not available (Why is that?)
• Discrepancy theory and related algorithms
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• Algorithmic aspects of combinatorial discrepancy
• A note on the discrepancy of matrices with bounded row and column sums
• On the gap between hereditary discrepancy and the determinant lower bound
• Linear and hereditary discrepancy
• Factorization norms and hereditary discrepancy
• Quantum discrepancy: a non-commutative version of combinatorial discrepancy
• An algorithm for Komlós conjecture matching Banaszczyk's bound
• Deterministic discrepancy minimization

This page was built for publication: The determinant bound for discrepancy is almost tight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4908259)