#
Monday Lecture and Colloquium

**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**

###
Andreas S. Schulz - MIT, Cambridge, USA

### On the rank of cutting-plane proof systems

*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**

###
Berit Grußien - HU Berlin

### Isoperimetric Inequalities on Hexagonal Grids

*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.

Letzte Aktualisierung:
21.06.2011