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