"On the stable Kneser graphs"

Ben Braun
University of Kentucky

Monday, April 6, 2009
4:00 pm, 845 Patterson Office Tower

Abstract:

Given integers n and k such that n > 2k-1, the Kneser graph KG(n, k) is the graph with vertex set the k-subsets of {1, 2, ..., n} and edges between disjoint subsets. In a remarkable application of the Borsuk-Ulam theorem, in 1978 L. Lovász determined that the chromatic number of KG(n, k) is n-2k+2 for all such n and k. Shortly afterward, A. Schrijver proved that KG(n, k) contains a vertex critical subgraph, denoted SG(n, k), whose chromatic number is also n-2k+2. The graphs SG(n, k) are called stable Kneser graphs and can be viewed as a fundamental obstruction to coloring the Kneser graphs. In this talk, we will discuss symmetry and independence properties of the stable Kneser graphs and some of their relatives.