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 n = 3^k, we exhibit three permutations whose corresponding set system has discrepancy \Omega (\log (n)). 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 O(\sqrt l).

About these ads
This entry was posted in Combinatorics and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s