Tutte seminar - Alantha Newman

A Counterexample to Beck's Three Permutations Conjecture

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, Jozsef Beck conjectured that the discrepancy of this set system is O(1). In other words, Beck conjectured that for every three permutations, 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 two.) 

We will present a counterexample to this conjecture: for any positive integer n = 3^k, we construct three permutations whose corresponding set system has discrepancy Ω(log(n)). Our counterexample is based on a simple recursive construction, and our proof of the discrepancy lower bound is by induction. 

Our work was inspired by an insightful and intriguing paper from SODA 2011 by Fritz Eisenbrand, Domotor Palvolgyi and Thomas Rothvoss, who show that Beck's Conjecture implies a constant additive integrality gap for the Gilmore-Gomory LP relaxation of the well-studied special case of Bin Packing in which each item has weight between 1/4 and 1/2, also known as the Three Partition problem. 

In a more recent extended version of their paper, they show an interesting consequence of our construction, which was also independently observed by Ofer Neiman: There are instances of the Three Partition problem and corresponding optimal LP solutions, such that any bin packing that only uses "patterns" from the non-zero support of these optimal LP solutions requires at least OPT + Ω(log(n)) bins. 

Time permitting, we will discuss this and other observations about the structure of the three permutations in our counterexample. 

(Joint work with Aleksandar Nikolov.)