Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Friday, May 28, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Carsten Lange (TU Berlin)
In 1978 Lovasz presented a powerful (topological) technique to prove lower bounds for the chromatic number of graphs. As a corollary, he proved Kneser's conjecture that asked for the chromatic number of Kneser graphs. A Kneser graph has the k-subsets of an n-set as vertices and two vertices form an edge if they are disjoint. A first example is the Petersen graph.
The topological lower bound can be phrased for Kneser graphs in combinatorial terms by the colourability defect introduced by Dolnikov in 1981.
In this talk, we survey known lower bounds for several r-uniform hypergraphs of Kneser type in terms of a generalised colourability defect and point to different trapdoors that are hidden on the way.
Automatic MiSe System Software Version 1.4803M | admin login