Fetching the paper…

Reading the bibliography…

The determinant bound for discrepancy is almost tight · Around

2011

The determinant bound for discrepancy is almost tight

Matousek, Jiri

Original
PDF
Post on X

Understand

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, .

Built on

Infinite programs
R. J. Duffin · 1956
Earlier work this paper cites.
First course in linear algebra
P. B. Bhattacharya, S. K. Jain, and S. R. Nagpaul · 1983
Earlier work this paper cites.
Discrepancy of set-systems and matrices
L. Lovász, J. Spencer, and K. Vesztergombi · 1986
Earlier work this paper cites.

Similar

Discrepancy theory
J. Beck and V. Sós · 1995
Cited alongside, same era.
Discrepancy after adding a single set
J.-H. Kim, J. Matoušek, and V. H. Vu · 2005
Cited alongside, same era.
Constructive algorithms for discrepancy minimization
Original
N. Bansal · 2010
Cited alongside, same era.

Then

Geometric Discrepancy (An Illustrated Guide), 2nd printing
J. Matoušek · 2010
Later among the works it cites.
Indecomposable coverings with concave polygons
D. Pálvölgyi · 2010
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…