Kneser graphs

The Kneser graph K(n,m) is the graph on the m-subsets of an n-set, adjacent when disjoint.

The graph K(n,m) is regular of valency (n–m choose m) (which is zero if n < 2m).

The graph K(n,m) has chromatic number n–2m+2 if n > 2m–1 (and 1 otherwise).

The Odd graphs O_m are Kneser graphs K(2m+1,m).

Kneser graphs are the distance-m graphs of the Johnson graphs, see there for some more details.

Far

Much more generally, in contexts where there is a natural concept of being as far apart as possible (like being disjoint for sets), one can define the Kneser graph in that setting to have as vertices the objects under consideration, where two objects are adjacent when they are as far apart as possible.

For example, when the objects are m-subspaces of a vector space of dimension n, then these are as far apart as possible when they meet in only the zero vector.

When the objects are elements of a conjugacy class of parabolic subgroups of a finite Chevalley group, then relations between them are labeled by double cosets of parabolic subgroups of the corresponding Weyl group, and two objects are as far apart as possible when the label of their relation contains the longest element of the Weyl group.

Many results that were first proved for sets can be generalized to vector spaces and spherical buildings. Some more detail for the situation where the objects are flags is given here.