you're reading...

Reading group meeting: Beck’s three permutations conjecture

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.



No comments yet.

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: