Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, December 07, 2017, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Torsten Mütze
The flip graph of triangulations has as vertices all triangulations of a set of points in convex position, and an edge between any two triangulations that differ in exactly one inner edge. A rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears and disappears exactly once. This notion of a rainbow cycle extends straightforwardly also to other flip graphs of interest for computer scientists, such as the flip graphs of spanning trees or matchings on a point set, or the flip graphs of permutations or subsets on a ground set. For each of these five settings we prove the existence and non-existence of rainbow cycles for different values of the parameters.
This is joint work with Stefan Felsner, Linda Kleist and Leon Sering.
Automatic MiSe System Software Version 1.4803M | admin login