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

Christos Athanasiadis - University of Athens

Connectivity and skeleta of convex polytopes

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

Kolja Knauer - TU Berlin

Distributive Polytopes

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)

Letzte Aktualisierung: 05.06.2008