Kneser graph

In graph theory, the Kneser graph Template:Math (alternatively Template:Math) is the graph whose vertices correspond to the [[combination|Template:Mvar-element subsets of a set of Template:Mvar elements]], and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956.

Examples

File:Kneser graph KG(7,3).jpg

Kneser graph Template:Math

The Kneser graph Template:Math is the complete graph on Template:Mvar vertices.

The Kneser graph Template:Math is the complement of the line graph of the complete graph on Template:Mvar vertices.

The Kneser graph Template:Math is the odd graph Template:Math; in particular Template:Math is the Petersen graph (see top right figure).

The Kneser graph Template:Math, visualized on the right.

Properties

Basic properties

The Kneser graph $K(n,k)$ has $(\genfrac{}{}{0ex}{}{n}{k})$ vertices. Each vertex has exactly $(\genfrac{}{}{0ex}{}{n-k}{k})$ neighbors.

The Kneser graph is vertex transitive and arc transitive. When $k=2$, the Kneser graph is a strongly regular graph, with parameters $((\genfrac{}{}{0ex}{}{n}{2}),(\genfrac{}{}{0ex}{}{n-2}{2}),(\genfrac{}{}{0ex}{}{n-4}{2}),(\genfrac{}{}{0ex}{}{n-3}{2}))$. However, it is not strongly regular when $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 $K(2k,k)$ which is disconnected. More precisely, the connectivity of $K(n,k)$ is $(\genfrac{}{}{0ex}{}{n-k}{k}),$ the same as the number of neighbors per vertex.Template:Sfnp

Chromatic number

As Template:Harvs conjectured, the chromatic number of the Kneser graph $K(n,k)$ for $n\ge 2k$ is exactly Template:Math; 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,Template:Sfnp 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.Template:Sfnp
• Joshua E. Greene won the 2002 Morgan Prize for outstanding undergraduate research for his further-simplified but still topological proof.Template:Sfnp
• In 2004, Jiří Matoušek found a purely combinatorial proof.Template:Sfnp

In contrast, the fractional chromatic number of these graphs is $n/k$.Template:Sfnp When $n<2k$, $K(n,k)$ has no edges and its chromatic number is 1. When $n=2k$, the graph is a perfect matching and its chromatic number is 2.

Hamiltonian cycles

It is well-known that the Petersen graph is not Hamiltonian, but it was long conjectured that this was the sole exception and that every other connected Kneser graph Template:Math is Hamiltonian.

In 2003, Chen showed that the Kneser graph Template:Math contains a Hamiltonian cycle ifTemplate:Sfnp

$n\ge \frac{1}{2}(3k+1+\sqrt{5k^2-2k+1}).$

Since

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

holds for all $k$, this condition is satisfied if

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

Around the same time, Shields showed (computationally) that, except the Petersen graph, all connected Kneser graphs Template:Math with Template:Math are Hamiltonian.Template:Sfnp

In 2021, Mütze, Nummenpalo, and Walczak proved that the Kneser graph Template:Math contains a Hamiltonian cycle if there exists a non-negative integer $a$ such that $n=2k+2^a$.Template:Sfnp In particular, the odd graph Template:Mvar has a Hamiltonian cycle if Template:Math. Finally, in 2023, Merino, Mütze and Namrata completed the proof of the conjecture.Template:Sfnp

Cliques

When Template:Math, the Kneser graph Template:Math contains no triangles. More generally, when Template:Math it does not contain cliques of size Template:Math, whereas it does contain such cliques when Template:Math. Moreover, although the Kneser graph always contains cycles of length four whenever Template:Math, for values of Template:Mvar close to Template:Math the shortest odd cycle may have variable length.Template:Sfnp

Diameter

The diameter of a connected Kneser graph Template:Math isTemplate:Sfnp $$\lceil \frac{k-1}{n-2k}\rceil +1.$$

Spectrum

The spectrum of the Kneser graph Template:Math consists of k + 1 distinct eigenvalues: $${\lambda }_j=(-1{)}^j(\genfrac{}{}{0ex}{}{n-k-j}{k-j}),j=0,\dots ,k.$$ Moreover ${\lambda }_j$ occurs with multiplicity $(\genfrac{}{}{0ex}{}{n}{j})-(\genfrac{}{}{0ex}{}{n}{j-1})$ for $j>0$ and ${\lambda }_0$ has multiplicity 1.

Independence number

The Erdős–Ko–Rado theorem states that the independence number of the Kneser graph Template:Math for $n\ge 2k$ is $$\alpha (K(n,k))=(\genfrac{}{}{0ex}{}{n-1}{k-1}),$$ but if $n>10000k$, then every vertex subset $S$ of size beyond the independence number will contain a vertex adjacent to at least $$(\frac{1}{2}-O\left(\sqrt{\frac{k}{n}}\right))(\genfrac{}{}{0ex}{}{n-k-1}{k-1})$$ other vertices in $S$.Template:Sfnp

Related graphs

The Johnson graph Template:Math is the graph whose vertices are the Template:Mvar-element subsets of an Template:Mvar-element set, two vertices being adjacent when they meet in a Template:Math-element set. The Johnson graph Template:Math is the complement of the Kneser graph Template:Math. Johnson graphs are closely related to the Johnson scheme, both of which are named after Selmer M. Johnson.

The generalized Kneser graph Template:Math has the same vertex set as the Kneser graph Template:Math, but connects two vertices whenever they correspond to sets that intersect in Template:Mvar or fewer items.Template:Sfnp Thus Template:Math.

The bipartite Kneser graph Template:Math has as vertices the sets of Template:Mvar and Template:Math items drawn from a collection of Template:Mvar elements. Two vertices are connected by an edge whenever one set is a subset of the other. Like the Kneser graph it is vertex transitive with degree $(\genfrac{}{}{0ex}{}{n-k}{k}).$ The bipartite Kneser graph can be formed as a bipartite double cover of Template:Math in which one makes two copies of each vertex and replaces each edge by a pair of edges connecting corresponding pairs of vertices.Template:Sfnp The bipartite Kneser graph Template:Math is the Desargues graph and the bipartite Kneser graph Template:Math is a crown graph.