Monday, June 16, 2008
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
room MA 041
Lecture - 14:15
Skeleta of convex polytopes and their connectivity are a rich source of challenging combinatorial problems. A fundamental result, known as Balinski's theorem, provides a sharp lower bound on the vertex connectivity degree of the one-dimensional skeleton of a d-dimensional polytope. We will discuss one of many possible generalizations of this theorem by considering the vertex connectivity of the graph on the k-dimensional faces of a d-dimensional polytope P, in which two such faces are adjacent if there exists a face of P of dimension k+1 which contains both. We will also discuss related problems and possible generalizations to regular cell complexes.
Colloquium - 16:00
A D-polytope is a polytope which is closed under componentwise maximization and minimization. This is, the point set of a D-polytope forms a distributive lattice in the dominance order on the Euclidean space. We characterize D-polytopes in terms of their bounding halfspaces. Examples are given by order polytopes or more generally by the ''polytropes'' of Joswig and Kulas.
Besides being a nice combination of geometrical and order theoretical concepts, D-polytopes are a unifying generalization of several distributive lattices arising from graphs. In fact every D-polytope corresponds to a directed graph with edge parameters, such that every point in the polytope corresponds to a vertex potential of the graph. Alternatively an edge-based description of the point set can be given.
These models specialize to distributive lattices that have been found on flows of planar graphs by Khuller, Naor and Klein, \alpha-orientations of planar graphs by Felsner, and c-orientations of graphs by Propp.
(joint work with Stefan Felsner)