Monday, April 27, 2015
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
We prove a general duality theorem for width parameters in combinatorial structures such as graphs and matroids. It implies the classical such theorems for path-width, tree-width, branch-width and rank-width, and gives rise to new width parameters with associated duality theorems. The dense substructures witnessing large width are presented in a unified way akin to tangles, as orientations of separation systems satisfying certain consistency axioms.
Colloquium - 16:00
Abstract:
A polyhedron P is called integral if P is the convex hull of its
integral points; P is called lattice-free if the interior of P contains no
integral points. Integral lattice-free polyhedra occur in several
areas of research including cutting-plane theory for mixed-integer
optimization and the geometry of toric varieties.
We call an integral lattice-free polyhedron P integrally maximal if P
is not a proper subset of another integral lattice-free polyhedron. It
is known that, for each given dimension, there are essentially
finitely many integral lattice-free polyhedra that are integrally
maximal. However, classification of such polyhedra is a challenging
task for each dimension starting from three. Benjamin Nill and Günter
Ziegler (2011) asked whether in dimension three integrally maximal
integral lattice-free polyhedra are also maximal in a certain stronger
sense (that is, within the family of all lattice-free polyhedra). I
will present a result that answers the latter question in positive and
enables to carry out a complete classification in the case of
dimension three.
This is joint work with Jan Krümpelmann and Stefan Weltge.