Up
# 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.