Topological bounds on the chromatic number

Speaker: Matěj Stehlík, Université Grenoble Alpes.

Date: 24 apr 2017, 13h.

Place: Room 409, Bloco H, IME, Campus Gragoatá, UFF.

Abstract: Topological bounds on the chromatic number of graphs originate from Lovasz’s celebrated proof of Kneser’s conjecture in 1977. The general idea is to associate a simplicial complex to a graph, and then to bound the chromatic number of the graph in terms of certain topological invariants of the associated complex. In this talk, we will explore an alternative approach using what we call higher-dimensional projective quadrangulations. We will illustrate this on some classes of graphs such as Kneser graphs, and also show how one of the “classical" topological bounds can be expressed purely in terms of projective quadrangulations.

Note: Joint work with Tomas Kaiser.