A Counterexample to Beck's Three Permutations Conjecture
| Speaker: | Alantha Newman |
|---|---|
| Affiliation: | Rutgers University |
| Room: | Mathematics & Computer Building (MC) 5158 |
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, Jozsef 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.)
We
will
present
a
counterexample
to
this
conjecture:
for
any
positive
integer
n
=
3k,
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.
Our
work
was
inspired
by
an
insightful
and
intriguing
paper
from
SODA
2011
by
Fritz
Eisenbrand,
Domotor
Palvolgyi
and
Thomas
Rothvoss,
who
show
that
Beck's
Conjecture
implies
a
constant
additive
integrality
gap
for
the
Gilmore-Gomory
LP
relaxation
of
the
well-studied
special
case
of
Bin
Packing
in
which
each
item
has
weight
between
1/4
and
1/2,
also
known
as
the
Three
Partition
problem.
In
a
more
recent
extended
version
of
their
paper,
they
show
an
interesting
consequence
of
our
construction,
which
was
also
independently
observed
by
Ofer
Neiman:
There
are
instances
of
the
Three
Partition
problem
and
corresponding
optimal
LP
solutions,
such
that
any
bin
packing
that
only
uses
"patterns"
from
the
non-zero
support
of
these
optimal
LP
solutions
requires
at
least
OPT
+
Ω(log(n))
bins.
Time
permitting,
we
will
discuss
this
and
other
observations
about
the
structure
of
the
three
permutations
in
our
counterexample.
(Joint
work
with
Aleksandar
Nikolov.)