[home] - [up]


Lectures and Colloquia during the semester



Monday, June 14, 2004

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 042           - map -
Lecture - 14:15

Frank Lutz -Technische Universität Berlin

The Geometry of Graph Colorings

Abstract: Graph coloring is a central but hard to tackle topic in discrete mathematics and combinatorial optimization. In particular, it is still unresolved how to obtain good lower bounds on the chromatic number of a graph. (To be more precise, all the known lower bounds are either rather weak, not computable, or work only in specific cases.)

In the topological approach to graph coloring problems, initiated 1978 by Lovasz' proof of the Kneser conjecture, lower bounds on the chromatic number are obtained by associating certain simplicial or cell complexes to a graph and then exploiting topological invariants of the resulting spaces (whenever this is possible).

An exposition of Lovasz' approach will be given in the talk. Also we will discuss the geometric, topological, and combinatorial properties of some interesting classes of coloring complexes.


Colloquium - 16:00

Taral Guldahl Seierstad -Humboldt-Universität zu Berlin

Restricted random graph processes

Abstract: We consider a random graph process where edges are added randomly, subject to the condition that the graph remains triangle-free. We study various properties that the resulting maximal triangle-free graph will have with high probability. One of the questions we would like to answer is which (triangle-free) graphs will almost surely appear as subgraphs - and when this happens.


[home] - [up] - [top]