Lectures and Colloquia during the semester

13. November 2000

Freie Universität Berlin - Institut für Informatik
Takustraße 9, 14195 Berlin
Seminarraum 005

Lecture - 14.00 Uhr c.t.

Yinfeng Xu - Xi'an Jiaotong University, China

Several Geometric MinMax Problems

Abstract: In this talk, we mainly discuss three geometric minmax problems as

Geometric structures and efficient algorithms for the optimal solutions of the problems are discussed and presented. At the end of the talk, some unsolved geometric minmax problems are given.

Colloquium - 16 Uhr s.t.

Hein van der Holst - Freie Universität Berlin

High-dimensional flatness and knots in graphs

Abstract: Motivated by the Colin de Verdiere invariant \mu(G) we discuss two classes of graphs. The first class of graphs is defined as follows. If G is a graph, let C_2(G) denote the complex obtained from G by attaching to each circuit of G a disc. We say that a graph is 4-flat if C_2(G) can be embedded in 4-space. The suspension of a flat graph is a graph which is 4-flat. The graphs that are obtained from K_7 and K_{3,3,1,1} by Y\Delta- and \Delta Y-transformations are example of graphs which are not 4-flat. We conjecture that the 4-flat graphs are exactly those graphs with \mu(G) \leq 5.

The second class is formed by those graphs which can be embedded in 3-space such that no circuit is a nontrivial knot. Since this class is closed under taking minors, one problem is to find graphs for which such an embedding is not possible. Can we find a certificate which shows that such an embedding is not possible (but not necessary the other way around)? Generalizing work of Conway and Gordan, who showed how to find a certificate for certain graphs in the case when one deals with the Arf invariant, we show how to find a certificate in the case of a Vassiliev invariant. (Some parts are joint work with R. Pendavingh.)