May 5 , 2008
Freie Universität Berlin
Institut für Informatik
Takustr. 9,
room 005
Lecture - 14:15
Abstract:
Triangulations of topological manifolds may be used to construct
spaces in algebraic geometry via Stanley-Reisner schemes. In this talk I
will start with Möbius' vertex-minimal triangulation of the torus with
seven vertices which corresponds to a highly singular abelian surface in
projective 6-space. Deforming this surface leads to interesting
combinatorics, including a special 6 dimensional reflexive polytope.
Colloquium - 16:00
Abstract:
In his celebrated 1978 proof of the Kneser Conjecture, Lovász showed that the chromatic number of a graph G is bounded below by the topological connectivity of the 'space of directed edges' of G. This is a special case of a general Hom(T,G) complex which assigns a topology to the set of graph homomorphisms from T to G, and one can ask which T are 'test graphs' in the sense that the topology of Hom(T,G) give the expected lower bound on chromatic number. In 2005, Babson and Kozlov showed that all odd cycles are test graphs, and in the process initiated a study of certain distinguished cohomology classes of the Hom complexes.
In this talk we prove a structural theorem which shows how one can encode the topology of spaces related to Hom complexes in graph theoretical terms. We then apply this result to produce a family of test graphs (with arbitrarily large chromatic number) which also give a reinterpretation of the connectivity of the original Lovász complexes. This generalizes a result of Schultz, who used a similar construction to prove a strengthening of the Babson-Kozlov theorem.
This is joint work with Carsten Schultz, TU Berlin.