Time: 1:00pm Tuesday 21 May.
Location: SIT 402
Speaker: Fabrizio Frati, University of Sydney
Paper: Beck’s three permutations conjecture: A counterexample and some consequences, by A. Newmann, and O. Neiman, and A. Nikolov.
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 permutations differs only by a constant.
The authors construct three permutations whose corresponding set system has discrepancy \Omega(\log n), thus disproving Beck’s conjecture. The counterexample is based on a simple recursive construction, and the proof of the discrepancy lower bound is by induction.
Consequences of this result for the bin packing problem will be discussed. This paper appeared at FOCS ’12.