Kneser graph

• The Kneser graph K(n, k) has ${\displaystyle {\tbinom {n}{k}}}$ vertices. Each vertex has exactly ${\displaystyle {\tbinom {n-k}{k}}}$ neighbors.

• The Kneser graph is vertex transitive and arc transitive. However, it is not, in general, a strongly regular graph, as different pairs of nonadjacent vertices have different numbers of common neighbors depending on the size of the intersection of the corresponding pair of sets.

• Because Kneser graphs are regular and edge-transitive, their vertex connectivity equals their degree, except for K(2k, k) which is disconnected. More precisely, the connectivity of K(n, k) is ${\displaystyle {\tbinom {n-k}{k}},}$ the same as the number of neighbors per vertex (Watkins 1970).

As Kneser (1956) conjectured, the chromatic number of the Kneser graph K(n, k) for ${\displaystyle n\geq 2k}$ is exactly n − 2k + 2; for instance, the Petersen graph requires three colors in any proper coloring. This conjecture was proved in several ways.

• László Lovász (1978) proved this using topological methods, giving rise to the field of topological combinatorics.
• Soon thereafter Imre Bárány (1978) gave a simple proof, using the Borsuk–Ulam theorem and a lemma of David Gale.
• Joshua E. Greene (2002) won the Morgan Prize for a further simplified but still topological proof.
• Jiří Matoušek (2004) found a purely combinatorial proof.

When ${\displaystyle n<2k}$, the chromatic number of K(n, k) is 1.

• The Kneser graph K(n, k) contains a Hamiltonian cycle if (Chen 2003):

${\displaystyle n\geq {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right).}$

Since

${\displaystyle {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right)<\left({\frac {3+{\sqrt {5}}}{2}}\right)k+1,}$

holds for all k this condition is satisfied if

${\displaystyle n\geq \left({\frac {3+{\sqrt {5}}}{2}}\right)k+1\approx 2.62k+1.}$

• The Kneser graph K(n, k) contains a Hamiltonian cycle if there exists a non-negative integer a such that ${\displaystyle n=2k+2^{a}}$ (Mütze, Nummenpalo & Walczak 2018). In particular, the odd graph O_n has a Hamiltonian cycle if n ≥ 4.

• With the exception of the Petersen graph, all connected Kneser graphs K(n, k) with n ≤ 27 are Hamiltonian (Shields 2004).

• When n < 3k, the Kneser graph K(n, k) contains no triangles. More generally, when n < ck it does not contain cliques of size c, whereas it does contain such cliques when n ≥ ck. Moreover, although the Kneser graph always contains cycles of length four whenever n ≥ 2k + 2, for values of n close to 2k the shortest odd cycle may have nonconstant length (Denley 1997).

• The diameter of a connected Kneser graph K(n, k) is (Valencia-Pabon & Vera 2005):

${\displaystyle \left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.}$

• The spectrum of the Kneser graph K(n, k) consists of k + 1 distinct eigenvalues:

${\displaystyle \lambda _{j}=(-1)^{j}{\binom {n-k-j}{k-j}},\qquad j=0,\ldots ,k.}$

Moreover ${\displaystyle \lambda _{j}}$ occurs with multiplicity ${\displaystyle {\tbinom {n}{j}}-{\tbinom {n}{j-1}}}$ for ${\displaystyle j>0}$ and ${\displaystyle \lambda _{0}}$ has multiplicity 1. See this paper for a proof.

• The Erdős–Ko–Rado theorem states that the independence number of the Kneser graph K(n, k) for ${\displaystyle n\geq 2k}$ is

${\displaystyle \alpha (K(n,k))={\binom {n-1}{k-1}}.}$