Monday, July 11, 2011
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
room MA 041
Lecture - 14:15
Abstract:
We introduce a natural abstraction of propositional proof systems that
are based on cutting planes. This new class of proof systems covers
well-known operators including Gomory-Chvátal cuts, lift-and-project
cuts, Sherali-Adams cuts, Lovász-Schrijver cuts, and split cuts. The
rank of such a proof system corresponds to the number of rounds needed
to show the nonexistence of integral solutions to a system of linear
inequalities. We present a family of polytopes in the unit cube
without integral points and show that it has a high rank for any proof
system in this class. In fact, we prove that whenever a specific
cutting-plane proof system has maximal rank on a particular family of
instances, then the rank of any cutting-plane proof system is close to
maximal. This result essentially implies that the rank of worst-case
examples does not depend on specific cutting-plane proof systems; it
is intrinsic to the respective family of instances.
This is joint work with Sebastian Pokutta.
Colloquium - 16:00
Abstract:
We consider the edge- and vertex-isoperimetric probem on finite and
infinite hexagonal grids:
For a subset A of the hexagonal grid of given cardinality, we give a
lower bound for the number of edges between A and its complement, and
lower bounds for the number of vertices in the neighborhood of A and for
the number of vertices in the boundary of A.
For the infinite hexagonal grid the given bounds are tight.