Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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