Kneser graph

The Kneser graph ${\displaystyle 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. When ${\displaystyle k=2}$, the Kneser graph is a strongly regular graph, with parameters ${\displaystyle ({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{2}})}$. However, it is not strongly regular when ${\displaystyle k>2}$, as different pairs of nonadjacent vertices have different numbers of common neighbors depending on the size of the intersection of the corresponding pairs of sets.

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

As Kneser (1956) conjectured, the chromatic number of the Kneser graph ${\displaystyle 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 proved this in 1978 using topological methods,[2] giving rise to the field of topological combinatorics.
• Soon thereafter Imre Bárány gave a simple proof, using the Borsuk–Ulam theorem and a lemma of David Gale.[3]
• Joshua E. Greene won the 2002 the Morgan Prize for outstanding undergraduate research for his further simplified but still topological proof.[4]
• In 2004, Jiří Matoušek found a purely combinatorial proof.[5]

In contrast, the fractional chromatic number of these graphs is ${\displaystyle n/k}$.[6] When ${\displaystyle n<2k}$, ${\displaystyle K(n,k)}$ has no edges and its chromatic number is 1.

The Kneser graph K(n, k) contains a Hamiltonian cycle if[7]

$${\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 ${\displaystyle 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}}$. [8] 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.[9]

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 variable length.[10]

The diameter of a connected Kneser graph K(n, k) is[11]

$${\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.[12]

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}}.}$$