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.
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.