Alantha Newman and Alexandar Nikolov Disprove Beck’s 3-Permutations Conjecture

Alantha Newman and Alexandar Nikolov disproved a few months ago one of the most famous and frustrating open problem in discrepancy theory: Beck’s 3-permutations conjecture. Their paper  A counterexample to Beck’s conjecture on the discrepancy of three permutations is already on the arxive since April. (I was slow to get the news. Yuval Peres who heard it from Prasad Tetali told me about it today. You can read about it already on Joel Spencer’s homepage. Joel had offered 100$ prize for solving the conjecture that Alantha and Alexandar collected.)

The paper’s abstract tells the story.

Our previos post gives the basic definition of discrepancy of a hypergraph (=set-system), and describes a theorem by Beck and Fiala.

Abstract: 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 , we exhibit three permutations whose corresponding set system has discrepancy . 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 .