EKR theorem

The chromatic number of the Kneser graphs and the q-Kneser graphs

This year is László Lovász‘s 70th birthday and I went to his birthday conference, so a blog post about one of his famous results seems to be appropriate: the chromatic number of the Kneser graph.

Let \Gamma be a graph with a vertex set V and an adjacency relation \sim. A coloring of \Gamma is a map from V from V to a set of colors C such that no pair of adjacent vertices gets mapped to the same element of C. The chromatic number of \Gamma is the smallest number of colors needed to color \Gamma. One of the nicest graphs to investigate is the Kneser graph: Here V consists of all subsets of \{ 1, 2, \ldots, n \} of size k and two vertices are adjacent if the corresponding k-sets are disjoint. For k=2 and n=5, this is the famous Petersen graph:

400px-Kneser_graph_KG(5,2).svg (more…)

Advertisement

Erdős-Ko-Rado Theorems for Spherical Buildings

Today’s topic combines three of my favorite subjects: Erdős-Ko-Rado theorems (EKR theorems), finite buildings and spectral techniques. All of these topics deserve their own books (and have them, here some examples which I read: Erdos-Ko-Rado Theorems: Algebraic Approaches by Chris Godsil and Karen Meagher, Spectra of Graphs by Andries E. Brouwer and Willem H. Haemers, The Structure of Spherical Buildings by Richard M. Weiss), so I will only touch these topics slightly.

My main aim is to present a variation of the EKR theorem which is motivated by questions about spherical buildings. The variation was recently formulated by Klaus Metsch, Bernhard Mühlherr, and me. If you already know spherical buildings, then you might prefer to read the introduction of our paper instead. (more…)