The determinant bound for discrepancy is almost tight
From MaRDI portal
Publication:4908259
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.
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
Cites work
- scientific article; zbMATH DE number 3121286 (Why is no real title available?)
- scientific article; zbMATH DE number 3817889 (Why is no real title available?)
- scientific article; zbMATH DE number 863495 (Why is no real title available?)
- Approximation algorithms and semidefinite programming.
- Discrepancy after adding a single set
- Discrepancy of set-systems and matrices
- Geometric discrepancy. An illustrated guide
- Indecomposable coverings with concave polygons
- Semidefinite Programming
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
- scientific article; zbMATH DE number 7758358 (Why is no real title available?)
- Discrepancy theory and related algorithms
- A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
- A note on the discrepancy of matrices with bounded row and column sums
- Algorithmic aspects of combinatorial discrepancy
- Linear and hereditary discrepancy
- On the gap between hereditary discrepancy and the determinant lower bound
- 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)
