Lectures and Colloquia during the semester

**Montag, 22. Januar 2001**

Freie Universität Berlin - Institut für
Informatik

Takustraße 9, 14195 Berlin

Seminarraum 005

**Lecture - 14.00 Uhr c.t.**

### Jørgen Bang-Jensen - University of Southern Denmark at Odense

### Paths and Cycles in Directed Graphs

*Abstract:*
We survey results on paths and cycles in directed graphs. In particular,
we discuss results on hamiltonian paths and cycles in directed
graphs. We describe various techniques for proving hamiltonicity of
different classes of digraphs such as the path-merging techinique and
the multi-insertion technique. We show how to obtain polynomial
algorithms for the hamiltonian cycle problem for quasi-transitive
digraphs by using the fact that these graphs have a nice recursive
structure. This solution also involves finding a minimum path-cover
in a quasi-transitive graph.

Bipartite tournaments are equivalent to 2-edge-coloured complete
bipartite graphs. We show briefly how to use this relationship to obtain
results on alternating hamiltonian cycles in 2-edge-coloured complete
graphs from results on hamiltonian cycles in bipartite tournaments and
vice versa.

We will also pose a number of open problems and conjectures on directed
graphs.

Much more information about directed graphs in general and paths and
cycle in particular can be found in the book "Digraphs: Theory,
Algorithms and Applications", Bang-Jensen and Gutin, Springer
Monographs in Mathematics.

**Colloquium - 16 Uhr s.t.**

### Julian Pfeifle - Technische Universität Berlin

### All of Kalai's "many" triangulated 3-spheres are polytopal

*Abstract:*
In 1988, Kalai extended a construction of Billera and Lee
to produce "many" triangulated *(d-1)*-spheres.
In fact, in view of upper bounds on the number of
simplicial d-polytopes by Goodman and Pollack, one can derive that
for every dimension *d >= 5*, most of these *(d-1)*-spheres
are not polytopal. However, for *d=4*, this reasoning fails.
We can now show that, as already conjectured by Kalai, all of
his 3-spheres are in fact polytopal.

[top]