Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

May 5 , 2008

Freie Universität Berlin
Institut für Informatik
Takustr. 9,
room 005

Lecture - 14:15

Jan Christophersen - Universitetet i Oslo

The minimal triangulation of the torus and abelian surfaces

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

Anton Dochtermann - University of Washington / TU Berlin

Test graphs for topological lower bounds on chromatic number

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.

Letzte Aktualisierung: 28.04.2008