| [home] - [up] |
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
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).