[home] - [up]


Lectures and Colloquia during the semester



July 14, 2003

Freie Universität Berlin - Institut für Informatik
Takustraße 9
14195 Berlin
Room 005           - map -
Lecture - 14:15

Ileana Streinu -Smith College, Northampton

Orienting the Rigidity Matroid

Abstract: In dimension two, infinitesimally (minimally) rigid graphs have a well understood combinatorial structure captured by Laman's condition. Morover, they form a matroid which is always realizable.

In this talk I will discuss an approach for orienting the 2-rigidity matroid via its circuits and a few related problems that emerged from this direction of research.


Colloquium - 16:00

Volker Kaibel - Technische Universität Berlin

On the Graph-Density of Random 0/1-Polytopes

Abstract: One of the discoveries that were especially exciting for the early polyhedral combinatorialists was the observation that many 0/1-polytopes associated with combinatorial optimization problems have graphs with very small diameters. Particularly striking examples are the cut-polytopes, whose graphs turned out to be complete. Thus, the density (i.e., the quotient of the number of edges and the number of two-element subsets of the node set) of the graph of any cut-polytope equals one.

In this talk, we demonstrate that high graph-density is not a feature that is special to "combinatorial" 0/1-polytopes. In fact, the graph density of a d-dimensional random 0/1-polytope with n(d) vertices tends to one (with d going to infinity) if n(d)<= (\sqrt{2}-\varepsilon)^d holds for some varepsilon>0, while it tends to zero in case of n(d)>= (sqrt{2}+varepsilon)^d. The cut-polytopes have n(d)<= const^{\sqrt{d}} vertices. The talk is based on joint work with Anja Remshagen (State University of West Georgia).


[home] - [up] - [top]