**Wednesday, 15:15 - 15:40 h, Room: H 3004**

**Alantha Newman**

A counterexample to Beck's three permutations conjecture

**Coauthors: Ofer Neiman, Aleksandar Nikolov**

**Abstract:**

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, József Beck conjectured that the discrepancy

of this set system is *O(1)*. In other words, Beck conjectured that

for every three permutations, 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 permutation differs only by a constant. (The

discrepancy of a set system based on two permutations is two.)

In this talk, we give a counterexample to this conjecture: for any

positive integer *n = 3*^{k}, we construct three permutations whose

corresponding set system has discrepancy *Ω(**log*{n}). Our

counterexample is based on a simple recursive construction, and our

proof of the discrepancy lower bound is by induction.

We also present implications of this construction for the bin packing

problem: There are instances of bin packing problem and corresponding

basic feasible LP solutions, such that any packing that only uses

patterns from the support of these solutions requires at least *OPT + Ω{**log*(n)} bins.

Talk 1 of the contributed session Wed.3.H 3004

**"Knapsack and bin packing"** [...]

Cluster 2

**"Combinatorial optimization"** [...]