Title: Beck’s three permutations conjecture: A counterexample and some consequences
Authors: Alantha Newman, Ofer Neiman and Aleksandar Nikolov
Abstract: Given three permutations on the integers 1 through n, consider the set system consisting of
each interval in each of the three permutations. In 1982, Beck conjectured that the discrepancy
of this set system is O(1). In other words, the conjecture says that each integer from 1 through
n can be colored either red or blue so that the number of red and blue integers in each interval
of each permutation differs only by a constant. (The discrepancy of a set system based on two
permutations is at most two.)
Our main result is a counterexample to this conjecture: for any positive integer n = 3k, we
construct 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 construction also disproves a generalization of Beck’s conjec-
ture due to Spencer, Srinivasan and Tetali, who conjectured that a set system corresponding to
l permutations has discrepancy O(\sqrt{l}).
Our work was inspired by an intriguing paper from SODA 2011 by Eisenbrand, Palvolgyi
and Rothvoss, who show a surprising connection between the discrepancy of three permutations
and the bin packing problem: They show that Beck’s conjecture implies a constant worst-case
bound on the additive integrality gap for the Gilmore-Gomory LP relaxation for bin packing
in the special case when all items have sizes strictly between 1/4 and 1/2, also known as the
three partition problem. Our counterexample shows that this approach to bounding the additive
integrality gap for bin packing will not work. We can, however, prove an interesting implication
of our construction in the reverse direction: there are instances of bin packing and corresponding
optimal basic feasible solutions for the Gilmore-Gomory LP relaxation such that any packing
that contains only patterns from the support of these solutions requires at least OPT+\Omega(log m)
bins, where m is the number of items.
Finally, we discuss some implications that our construction has for other areas of discrepancy
theory.