Let be a graph with a vertex set and an adjacency relation . A coloring of is a map from from to a set of colors such that no pair of adjacent vertices gets mapped to the same element of . The chromatic number of is the smallest number of colors needed to color . One of the nicest graphs to investigate is the Kneser graph: Here consists of all subsets of of size and two vertices are adjacent if the corresponding -sets are disjoint. For and , this is the famous Petersen graph:
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…)