The determinant bound for discrepancy is almost tight

Details The determinant bound for discrepancy is almost tight The determinant bound for discrepancy is almost tight

2011-01-04

arxiv.org/abs/1101.0767v2

Mathematics

Combinatorics

9 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The determinant bound for discrepancy is almost tight does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The determinant bound for discrepancy is almost tight, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The determinant bound for discrepancy is almost tight will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-75270