The Discrepancy of Three Permutations
[October, 2012] DIMACS researcher
Alantha Newman and graduate student Aleksandar Nikolov
discovered a counterexample to a long-standing a conjecture by
Jozsef Beck (
Beck’s “Three Permutations Conjecture” (c. 1982) states that when the set system is derived from three permutations, the discrepancy of the set system is a constant. The analogous result is true for the set system based on two permutations, and there is a simple, well-known proof demonstrating that fact.
Newman and Nikolov showed that this well studied conjecture is false for three permutations by providing a counterexample. For any positive integer n =3k , they exhibited three permutations whose corresponding set system has discrepancy (log(n)).
Professor Joel Spencer (NYU) stated Beck’s conjecture in his Ten Lectures on the Probabilistic Method in 1987 and offered a $100 reward for settling it. Newman and Nikolov are shown collecting this bounty.
One inspiration for Newman and Nikolov’s work was a paper by Eisenbrand, Palvolgyi and Rothvoss (SODA 2010) that showed that if Beck’s conjecture were true, then a well-studied linear programming (LP) relaxation for bin packing would yield a lower bound on the value of an optimal integer solution that is within an additive constant of optimal. Newman and Nikolov’s result closes that particular path to approximability of bin packing.
in joint work with Ofer Neiman (then a postdoctoral researcher
Contacting the Center