A Tighter Relation Between Hereditary Discrepancy and Determinant Lower Bound

2021/08/18 by Haotian Jiang, Jiang, Haotian, Víctor Machado Reis +1 · 1 citation
Mathematics · Computer Science · #Mathematical Approximation and Integration #Coding theory and cryptography #Analytic Number Theory Research

paper · pdf · doi:10.48550/arxiv.2108.07945

Abstract

In seminal work, Lovász, Spencer, and Vesztergombi [European J. Combin., 1986] proved a lower bound for the hereditary discrepancy of a matrix A ∈ ℝ^{m × n} in terms of the maximum |det(B)|^1/k over all k × k submatrices B of A. We show algorithmically that this determinant lower bound can be off by at most a factor of O(√(log (m) ⋅ log (n))), improving over the previous bound of O(log(mn) ⋅ √(log (n))) given by Matoušek [Proc. of the AMS, 2013]. Our result immediately implies herdisc(F₁ ∪ F₂) ≤ O(√(log (m) ⋅ log (n))) ⋅ max(herdisc(F₁), herdisc(F₂)), for any two set systems F₁, F₂ over [n] satisfying |F₁ ∪ F₂| = m. Our bounds are tight up to constants when m = O(poly(n)) due to a construction of Pálvölgyi [Discrete Comput. Geom., 2010] or the counterexample to Beck's three permutation conjecture by Newman, Neiman and Nikolov [FOCS, 2012].

Cited by

• Diagonal Frobenius Number via Gomory's Relaxation and Discrepancy

Related

• The determinant bound for discrepancy is almost tight
• On the Gap between Hereditary Discrepancy and the Determinant Lower Bound
• Factorization Norms and Hereditary Discrepancy
• Approximating Hereditary Discrepancy via Small Width Ellipsoids
• On The Hereditary Discrepancy of Homogeneous Arithmetic Progressions