In graph theory, the Kneser graph (alternatively ) is the graph whose vertices correspond to the k-element subsets of a set of n 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

The Kneser graph is the complete graph on vertices.

The Kneser graph is the complement of the line graph of the complete graph on vertices.

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

The Kneser graph , visualized on the right.

Properties

Basic properties

neighbors.

The Kneser graph is vertex transitive and arc transitive, the Kneser graph is 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 pairs of sets.

Because Kneser graphs are regular and edge-transitive, their vertex connectivity equals their degree which is disconnected the same as the number of neighbors per vertex.

Chromatic number

As conjectured, the chromatic number is exactly ; 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, 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.

• Joshua E. Greene won the 2002 Morgan Prize for outstanding undergraduate research for his further-simplified but still topological proof.

• In 2004, Jiří Matoušek found a purely combinatorial proof.

In contrast, the fractional chromatic number., 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 is Hamiltonian.

In 2003, Ya-Chen Chen showed that the Kneser graph contains a Hamiltonian cycle if

Since

, this condition is satisfied if

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

In 2021, Mütze, Nummenpalo, and Walczak proved that the Kneser graph contains a Hamiltonian cycle if there exists a non-negative integer. In particular, the odd graph has a Hamiltonian cycle if . Finally, in 2023, Merino, Mütze and Namrata completed the proof of the conjecture.

Cliques

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

Diameter

The diameter of a connected Kneser graph is

Spectrum

The spectrum of the Kneser graph consists of k + 1 distinct eigenvalues occurs with multiplicity has multiplicity 1.

Independence number

The Erdős–Ko–Rado theorem states that the independence number of the Kneser graph .

Related graphs

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

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

The bipartite Kneser graph has as vertices the sets of and items drawn from a collection of The bipartite Kneser graph can be formed as a bipartite double cover of in which one makes two copies of each vertex and replaces each edge by a pair of edges connecting corresponding pairs of vertices. The bipartite Kneser graph is the Desargues graph and the bipartite Kneser graph is a crown graph.

References

Notes

Works cited

External links