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
Abstract:
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
Abstract:
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)