Kneser graph

{{short description|Graph whose vertices correspond to combinations of a set of n elements}}

{{For|the Kneser neighborhood graph of unimodular lattices|Niemeier lattice}}

{{infobox graph

| name = Kneser graph

| image = 230px

| image_caption = The Kneser graph {{math|K(5, 2)}},
isomorphic to the Petersen graph

| namesake = Martin Kneser

| vertices = $\binom{n}{k}$

| edges = $\frac{1}{2}\binom{n}{k} \binom{n-k}{k}$

| chromatic_number = $\begin{cases} n-2k+2 & n \ge 2 k\\ 1 & n<2k\end{cases}$

| properties = $\tbinom{n-k}{k}$ -regular
arc-transitive

|notation = {{math|K(n, k), KG_n,k}}.

}}

In graph theory, the Kneser graph {{math|K(n, k)}} (alternatively {{math|KG_n,k}}) is the graph whose vertices correspond to the combination, 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

The Kneser graph {{math|K(n, 1)}} is the complete graph on {{mvar|n}} vertices.

The Kneser graph {{math|K(n, 2)}} is the complement of the line graph of the complete graph on {{mvar|n}} vertices.

The Kneser graph {{math|K(2n − 1, n − 1)}} is the odd graph {{math|O_n}}; in particular {{math|1=O₃ = K(5, 2)}} is the Petersen graph (see top right figure).

The Kneser graph {{math|1=O₄ = K(7, 3)}}, visualized on the right.

Properties

= Basic properties =

The Kneser graph $K(n,k)$ has $\tbinom{n}{k}$ vertices. Each vertex has exactly $\tbinom{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 $( \tbinom{n}{2}, \tbinom{n-2}{2}, \tbinom{n-4}{2}, \tbinom{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 $\tbinom{n-k}{k},$ the same as the number of neighbors per vertex.{{sfnp|Watkins|1970}}

= {{Anchor|chromatic}}Chromatic number =

As {{harvs|last=Kneser|year=1956|txt}} conjectured, the chromatic number of the Kneser graph $K(n,k)$ for $n\geq 2k$ is exactly {{math|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,{{sfnp|Lovász|1978}} 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.{{sfnp|Bárány|1978}}
Joshua E. Greene won the 2002 Morgan Prize for outstanding undergraduate research for his further-simplified but still topological proof.{{sfnp|Greene|2002}}
In 2004, Jiří Matoušek found a purely combinatorial proof.{{sfnp|Matoušek|2004}}

In contrast, the fractional chromatic number of these graphs is $n/k$ .{{sfnp|Godsil|Meagher|2015}}

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 {{math|K(n, k)}} is Hamiltonian.

In 2003, Chen showed that the Kneser graph {{math|K(n, k)}} contains a Hamiltonian cycle if{{sfnp|Chen|2003}}

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

Since

: $\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

: $n \geq \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 {{math|K(n, k)}} with {{math|n ≤ 27}} are Hamiltonian.{{sfnp|Shields|2004}}

In 2021, Mütze, Nummenpalo, and Walczak proved that the Kneser graph {{math|K(n, k)}} contains a Hamiltonian cycle if there exists a non-negative integer $a$ such that $n=2k+2^a$ .{{sfnp|Mütze|Nummenpalo|Walczak|2021}} In particular, the odd graph {{mvar|O_n}} has a Hamiltonian cycle if {{math|n ≥ 4}}. Finally, in 2023, Merino, Mütze and Namrata completed the proof of the conjecture.{{sfnp|Merino|Mütze|Namrata|2023}}

= Cliques =

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

= Diameter =

The diameter of a connected Kneser graph {{math|K(n, k)}} is{{sfnp|Valencia-Pabon|Vera|2005}}

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

=Spectrum=

The spectrum of the Kneser graph {{math|K(n, k)}} consists of k + 1 distinct eigenvalues:

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

Moreover $\lambda_j$ occurs with multiplicity $\tbinom{n}{j}-\tbinom{n}{j-1}$ for $j >0$ and $\lambda_0$ has multiplicity 1.{{cite web |url=http://www.math.caltech.edu/~2011-12/2term/ma192b/kneser-evals.pdf |title=Archived copy |website=www.math.caltech.edu |access-date=9 August 2022 |archive-url=https://web.archive.org/web/20120323231232/http://www.math.caltech.edu/~2011-12/2term/ma192b/kneser-evals.pdf |archive-date=23 March 2012 |url-status=dead}}{{cite book |last1=Chowdhury |first1=Ameerah Naz |title=Shadows and Intersections (PhD Thesis) |date=2012 |publisher=ProQuest Dissertations & Theses |location=University of California, San Diego |page=47 |url=https://escholarship.org/uc/item/03k1h0m5 |access-date=21 May 2025}}

= Independence number =

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

$\alpha(K(n,k))=\binom{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

$\left(\frac{1}{2}-O\left(\sqrt{\frac{k}{n}}\right)\right) \binom{n-k-1}{k-1}$

other vertices in $S$ .{{sfnp|Chau|Ellis|Friedgut|Lifshitz|2025}}

Related graphs

The Johnson graph {{math|J(n, k)}} is the graph whose vertices are the {{mvar|k}}-element subsets of an {{mvar|n}}-element set, two vertices being adjacent when they meet in a {{math|(k − 1)}}-element set. The Johnson graph {{math|J(n, 2)}} is the complement of the Kneser graph {{math|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 {{math|K(n, k, s)}} has the same vertex set as the Kneser graph {{math|K(n, k)}}, but connects two vertices whenever they correspond to sets that intersect in {{mvar|s}} or fewer items.{{sfnp|Denley|1997}} Thus {{math|1=K(n, k, 0) = K(n, k)}}.

The bipartite Kneser graph {{math|H(n, k)}} has as vertices the sets of {{mvar|k}} and {{math|n − k}} items drawn from a collection of {{mvar|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 $\tbinom{n-k}{k}.$ The bipartite Kneser graph can be formed as a bipartite double cover of {{math|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.{{sfnp|Simpson|1991}} The bipartite Kneser graph {{math|H(5, 2)}} is the Desargues graph and the bipartite Kneser graph {{math|H(n, 1)}} is a crown graph.

References

=Notes=

=Works cited=

{{citation

| doi = 10.1016/0097-3165(78)90023-7

| mr = 0514626

| last = Bárány | first = Imre

| authorlink = Imre Bárány

| journal = Journal of Combinatorial Theory | series=Series A

| title = A short proof of Kneser's conjecture

| volume = 25

| issue = 3

| year = 1978

| pages = 325–326| doi-access =

}}

{{citation

| doi =10.5070/C65165027

| mr = 4882080

| last1 = Chau| first1 = Hou Tin

| last2 = Ellis| first2 = David

| last3 = Friedgut| first3 = Ehud

| last4 = Lifshitz| first4 = Noam

| journal = Combinatorial Theory

| title = On the maximum degree of induced subgraphs of the Kneser graph

| volume = 5

| issue = 1

| year = 2025

| at = Paper#16| doi-access = free

| arxiv = 2312.06370

}}

{{citation

| last = Chen | first = Ya-Chen

| journal = Journal of Combinatorial Theory | series=Series B

| title = Triangle-free Hamiltonian Kneser graphs

| volume = 89

| issue = 1

| year = 2003

| pages = 1–16

| doi = 10.1016/S0095-8956(03)00040-6

| mr = 1999733| doi-access =

}}

{{citation

| title = The odd girth of the generalised Kneser graph

| last = Denley | first = Tristan

| journal = European Journal of Combinatorics

| volume = 18

| issue = 6

| year = 1997

| pages = 607–611

| doi = 10.1006/eujc.1996.0122

| mr = 1468332| doi-access = free

}}

{{citation

| last1 = Godsil | first1 = Christopher | author1-link = Chris Godsil

| last2 = Meagher | first2 = Karen

| isbn = 9781107128446

| page = 43

| publisher = Cambridge University Press

| series = Cambridge Studies in Advanced Mathematics

| title = Erdős–Ko–Rado Theorems: Algebraic Approaches

| url = https://www.cambridge.org/ht/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/erdoskorado-theorems-algebraic-approaches

| year = 2015}}

{{citation

| last = Greene |first=Joshua E.

| title = A new short proof of Kneser's conjecture

| journal = American Mathematical Monthly

| year = 2002

| volume = 109

| issue = 10

| pages = 918–920

| doi = 10.2307/3072460

| mr = 1941810|jstor=3072460

}}

{{citation

| last = Kneser | first = Martin | authorlink = Martin Kneser

| title = Aufgabe 360

| journal = Jahresbericht der Deutschen Mathematiker-Vereinigung | issue=2

| volume = 58

| year = 1956

| pages = 27}}

{{citation

| last = Lovász | first = László

| authorlink = László Lovász

| title = Kneser's conjecture, chromatic number, and homotopy

| year = 1978

| volume = 25

| journal = Journal of Combinatorial Theory | series = Series A

| issue = 3

| pages = 319–324

| doi = 10.1016/0097-3165(78)90022-5 | doi-access = free

| mr = 0514625| hdl = 10338.dmlcz/126050

| hdl-access = free

}}

{{citation

| last = Matoušek | first = Jiří | authorlink = Jiří Matoušek (mathematician)

| title = A combinatorial proof of Kneser's conjecture

| journal = Combinatorica

| volume = 24

| issue = 1

| year = 2004

| pages = 163–170

| doi = 10.1007/s00493-004-0011-1

| mr = 2057690| hdl = 20.500.11850/50671

| s2cid = 42583803 | hdl-access = free

}}

{{citation

| last1 = Mütze | first1 = Torsten

| last2 = Nummenpalo | first2 = Jerri

| last3 = Walczak | first3 = Bartosz

| arxiv = 1711.01636

| mr = 3826304

| pages = 912–919

|location=New York

| title = Sparse Kneser graphs are Hamiltonian

| journal = Journal of the London Mathematical Society

| year = 2021| volume = 103

| orig-year = STOC 2018

| issue = 4

| doi = 10.1112/jlms.12406

}}

{{citation

| last1=Merino | first1=Arturo

| last2=Mütze | first2=Torsten

| author3=Namrata

| contribution=Kneser graphs are Hamiltonian

| title=Proceedings of the 55th Annual ACM Symposium on Theory of Computing

| pages=963–970

| date=2023

| doi=10.1145/3564246.3585137 | doi-access=free| arxiv=2212.03918

| isbn=978-1-4503-9913-5

}}

{{citation

|last = Shields

|first = Ian Beaumont

|title = Hamilton Cycle Heuristics in Hard Graphs

|series = Ph.D. thesis

|publisher = North Carolina State University

|url = http://www.lib.ncsu.edu/theses/available/etd-03142004-013420/

|archive-url = https://wayback.archive-it.org/all/20060917132442/http://www.lib.ncsu.edu/theses/available/etd-03142004-013420/

|url-status = dead

|archive-date = 2006-09-17

|year = 2004

|access-date = 2006-10-01

}}

{{citation

| last = Simpson | first = J. E.

| contribution = Hamiltonian bipartite graphs

| title = Proceedings of the Twenty-Second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991)

| pages = 97–110

| series = Congressus Numerantium

| volume = 85

| year = 1991

| mr = 1152123}}

{{citation

| title = On the diameter of Kneser graphs

| last1 = Valencia-Pabon | first1 = Mario | last2 = Vera | first2 = Juan-Carlos

| journal = Discrete Mathematics

| volume = 305

| issue = 1–3

| pages = 383–385

| year = 2005

| doi = 10.1016/j.disc.2005.10.001

| mr = 2186709| doi-access = free

}}

{{citation

| last = Watkins | first = Mark E.

| doi = 10.1016/S0021-9800(70)80005-9

| journal = Journal of Combinatorial Theory

| mr = 266804

| pages = 23–29

| title = Connectivity of transitive graphs

| volume = 8

| year = 1970| doi-access =

}}

External links

{{MathWorld|urlname=KneserGraph|title=Kneser Graph}}
{{MathWorld|urlname=OddGraph|title=Odd Graph}}

Category:Parametric families of graphs

Category:Regular graphs