November 27, Tuesday
12:00 – 13:00
Beck’s three permutations conjecture: A counterexample and some consequences
Computer Science seminar
Lecturer : Ofer Neiman
Affiliation : CS, BGU
Location : 202/37
Host : Dr. Aryeh Kontorovich
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 = 3^k, we construct three permutations whose corresponding set system has discrepancy at least k/3.
Time permitting I will also discuss an implication of this result to the integrality gap of the Gilmore-Gomory LP relaxation for Bin Packing.
Joint with Alantha Newman and Aleksandar Nikolov