A counterexample to Beck's conjecture on the discrepancy of three permutations

Details A counterexample to Beck's conjecture on the discrepancy of three permutations A counterexample to Beck's conjecture on the discrepancy of three permutations

2011-04-14

arxiv.org/abs/1104.2922v1

Computer Science

Discrete Mathematics

Scientific paper

Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations. Jozsef Beck conjectured (c. 1987) that the discrepancy of this set system is O(1). We give a counterexample to this conjecture: for any positive integer n = 3^k, we exhibit three permutations whose corresponding set system has discrepancy Omega(log(n)). Our counterexample is based on a simple recursive construction, and our proof of the discrepancy lower bound is by induction. This example also disproves a generalization of Beck's conjecture due to Spencer, Srinivasan and Tetali, who conjectured that a set system corresponding to l permutations has discrepancy O(sqrt(l)).

Affiliated with

Also associated with

No associations

Rating

A counterexample to Beck's conjecture on the discrepancy of three permutations 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 A counterexample to Beck's conjecture on the discrepancy of three permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A counterexample to Beck's conjecture on the discrepancy of three permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-7987