Kneser graph

From HandWiki
Short description: Graph whose vertices correspond to combinations of a set of n elements
Kneser graph
Kneser graph KG(5,2).svg
The Kneser graph K(5, 2),
isomorphic to the Petersen graph
Named afterMartin Kneser
Vertices[math]\displaystyle{ \binom{n}{k} }[/math]
Edges[math]\displaystyle{ \frac{1}{2}\binom{n}{k} \binom{n-k}{k} }[/math]
Chromatic number[math]\displaystyle{ \begin{cases} n-2k+2 & n \ge 2 k\\ 1 & n\lt 2k\end{cases} }[/math]
Properties[math]\displaystyle{ \tbinom{n-k}{k} }[/math]-regular
arc-transitive
NotationK(n, k), KGn,k.
Table of graphs and parameters

In graph theory, the Kneser graph K(n, k) (alternatively KGn,k) 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

Kneser graph O4 = K(7, 3)

The Kneser graph K(n, 1) is the complete graph on n vertices.

The Kneser graph K(n, 2) is the complement of the line graph of the complete graph on n vertices.

The Kneser graph K(2n − 1, n − 1) is the odd graph On; in particular O3 = K(5, 2) is the Petersen graph (see top right figure).

The Kneser graph O4 = K(7, 3), visualized on the right.

Properties

Basic properties

The Kneser graph [math]\displaystyle{ K(n,k) }[/math] has [math]\displaystyle{ \tbinom{n}{k} }[/math] vertices. Each vertex has exactly [math]\displaystyle{ \tbinom{n-k}{k} }[/math] neighbors.

The Kneser graph is vertex transitive and arc transitive. When [math]\displaystyle{ k=2 }[/math], the Kneser graph is a strongly regular graph, with parameters [math]\displaystyle{ ( \tbinom{n}{2}, \tbinom{n-2}{2}, \tbinom{n-4}{2}, \tbinom{n-3}{2} ) }[/math]. However, it is not strongly regular when [math]\displaystyle{ k\gt 2 }[/math], 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 [math]\displaystyle{ K(2k,k) }[/math] which is disconnected. More precisely, the connectivity of [math]\displaystyle{ K(n,k) }[/math] is [math]\displaystyle{ \tbinom{n-k}{k}, }[/math] the same as the number of neighbors per vertex.[1]

Chromatic number

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

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

Hamiltonian cycle

It was proven in 2023 that all Kneser graphs are Hamiltonian with the sole exception of the Petersen graph.[7]

Before that, proofs were known for special cases:

  • The Kneser graph K(n, k) contains a Hamiltonian cycle if[8]
[math]\displaystyle{ n\geq \frac{1}{2} \left (3k+1+\sqrt{5k^2-2k+1} \right ). }[/math] Since
[math]\displaystyle{ \frac{1}{2} \left (3k+1+\sqrt{5k^2-2k+1} \right )\lt \left (\frac{3 + \sqrt{5}}{2} \right) k+1 }[/math] holds for all [math]\displaystyle{ k }[/math] this condition is satisfied if
[math]\displaystyle{ n\geq \left (\frac{3 + \sqrt{5}}{2} \right) k+1 \approx 2.62k+1. }[/math]
  • The Kneser graph K(n, k) contains a Hamiltonian cycle if there exists a non-negative integer [math]\displaystyle{ a }[/math] such that [math]\displaystyle{ n=2k+2^a }[/math].[9] In particular, the odd graph On 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.[10]

Cliques

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.[11]

Diameter

The diameter of a connected Kneser graph K(n, k) is[12] [math]\displaystyle{ \left\lceil \frac{k-1}{n-2k} \right\rceil + 1. }[/math]

Spectrum

The spectrum of the Kneser graph K(n, k) consists of k + 1 distinct eigenvalues: [math]\displaystyle{ \lambda_j=(-1)^j\binom{n-k-j}{k-j}, \qquad j=0, \ldots,k. }[/math] Moreover [math]\displaystyle{ \lambda_j }[/math] occurs with multiplicity [math]\displaystyle{ \tbinom{n}{j}-\tbinom{n}{j-1} }[/math] for [math]\displaystyle{ j \gt 0 }[/math] and [math]\displaystyle{ \lambda_0 }[/math] has multiplicity 1.[13]

Independence number

The Erdős–Ko–Rado theorem states that the independence number of the Kneser graph K(n, k) for [math]\displaystyle{ n\geq 2k }[/math] is [math]\displaystyle{ \alpha(K(n,k))=\binom{n-1}{k-1}. }[/math]

Related graphs

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

The generalized Kneser graph K(n, k, s) has the same vertex set as the Kneser graph K(n, k), but connects two vertices whenever they correspond to sets that intersect in s or fewer items.[11] Thus K(n, k, 0) = K(n, k).

The bipartite Kneser graph H(n, k) has as vertices the sets of k and n − k items drawn from a collection of n 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 [math]\displaystyle{ \tbinom{n-k}{k}. }[/math] The bipartite Kneser graph can be formed as a bipartite double cover of K(n, k) in which one makes two copies of each vertex and replaces each edge by a pair of edges connecting corresponding pairs of vertices.[14] The bipartite Kneser graph H(5, 2) is the Desargues graph and the bipartite Kneser graph H(n, 1) is a crown graph.

References

Notes

  1. ↑ Watkins (1970).
  2. ↑ Lovász (1978).
  3. ↑ Bárány (1978).
  4. ↑ Greene (2002).
  5. ↑ Matoušek (2004).
  6. ↑ Godsil & Meagher (2015).
  7. ↑ Merino, Mütze & Namrata (2023).
  8. ↑ Chen (2003).
  9. ↑ Mütze, Nummenpalo & Walczak (2021).
  10. ↑ Shields (2004).
  11. ↑ 11.0 11.1 Denley (1997).
  12. ↑ Valencia-Pabon & Vera (2005).
  13. ↑ "Archived copy". http://www.math.caltech.edu/~2011-12/2term/ma192b/kneser-evals.pdf. 
  14. ↑ Simpson (1991).

Works cited

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Kneser_graph&oldid=3361329"