Kneser-Diagramm

In der Graphentheorie ist der Kneser-Graph K ( n , k ) (alternativ KG_{_{n , k}} ) ein Graph , dessen Knoten den k -elementigen Teilmengen einer n- elementigen Menge entsprechen und in dem zwei Knoten genau dann benachbart sind, wenn die beiden zugehörigen Mengen disjunkt sind. Kneser-Graphen sind nach Martin Kneser benannt , der sie 1956 erstmals untersuchte.

Der Kneser-Graph K ( n , 1) ist der vollständige Graph mit n Knoten.

Der Knesergraph K ( n , 2) ist das Komplement des Kantengraphen des vollständigen Graphen mit n Knoten.

Der Kneser-Graph K (2 n − 1, n − 1) ist der ungerade Graph O _n ; insbesondere ist O ₃ = K (5, 2) der Petersen-Graph (siehe Abbildung oben rechts).

Der Kneser-Graph O ₄ = K (7, 3) , rechts visualisiert.

Der Kneser-Graph hat Knoten. Jeder Knoten hat genau Nachbarn. ${\displaystyle K(n,k)}$${\displaystyle {\tbinom {n}{k}}}$${\displaystyle {\tbinom {nk}{k}}}$

Der Kneser-Graph ist knoten- und kantentransitiv . Für ist der Kneser-Graph ein stark regulärer Graph mit den Parametern . Er ist jedoch nicht stark regulär für , da verschiedene Paare nicht benachbarter Knoten je nach Größe des Schnitts der entsprechenden Mengenpaare unterschiedlich viele gemeinsame Nachbarn haben. ${\displaystyle k=2}$${\displaystyle ({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{2}})}$${\displaystyle k>2}$

Da Kneser-Graphen regulär und kantentransitiv sind , entspricht ihre Knotenkonnektivität ihrem Grad , außer bei Knoten, die unzusammenhängend sind . Genauer gesagt, ist die Knotenkonnektivität gleich der Anzahl der Nachbarn pro Knoten. ^{[ 1 ]}${\displaystyle K(2k,k)}$${\displaystyle K(n,k)}$${\displaystyle {\tbinom {nk}{k}},}$

Wie Kneser ( 1956 ) vermutete , ist die chromatische Zahl des Kneser-Graphen für genau n − 2k + 2 ; beispielsweise benötigt der Petersen-Graph in jeder zulässigen Färbung drei Farben . Diese Vermutung wurde auf verschiedene Weisen bewiesen .${\displaystyle K(n,k)}$${\displaystyle n\geq 2k}$

• László Lovász bewies dies 1978 mit Hilfe topologischer Methoden ^{[ 2 ]} und begründete damit das Gebiet der topologischen Kombinatorik .
• Kurz darauf lieferte Imre Bárány einen einfachen Beweis unter Verwendung des Satzes von Borsuk-Ulam und eines Lemmas von David Gale . ^{[ 3 ]}
• Joshua E. Greene gewann 2002 den Morgan-Preis für herausragende studentische Forschungsarbeit für seinen weiter vereinfachten, aber immer noch topologischen Beweis. ^{[ 4 ]}
• Im Jahr 2004 fand Jiří Matoušek einen rein kombinatorischen Beweis . ^{[ 5 ]}

Im Gegensatz dazu ist die fraktionale chromatische Zahl dieser Graphen . ^{[ 6 ]} Wenn , hat der Graph keine Kanten und seine chromatische Zahl ist 1. Wenn , ist der Graph ein perfektes Matching und seine chromatische Zahl ist 2. ${\displaystyle n/k}$${\displaystyle n<2k}$${\displaystyle K(n,k)}$${\displaystyle n=2k}$

Es ist bekannt, dass der Petersen-Graph nicht hamiltonsch ist , aber es wurde lange vermutet, dass dies die einzige Ausnahme sei und dass jeder andere zusammenhängende Kneser-Graph K ( n , k ) hamiltonsch sei.

Im Jahr 2003 zeigte Ya-Chen Chen, dass der Kneser-Graph K ( n , k ) einen Hamiltonkreis enthält, wenn ^{[ 7 ].}

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

Seit

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

gilt für alle , diese Bedingung ist erfüllt, wenn ${\displaystyle k}$

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

Etwa zur gleichen Zeit zeigte Shields (rechnerisch), dass mit Ausnahme des Petersen-Graphen alle zusammenhängenden Kneser-Graphen K ( n , k ) mit n ≤ 27 Hamiltonsch sind. ^{[ 8 ]}

Im Jahr 2021 bewiesen Mütze, Nummenpalo und Walczak, dass der Kneser-Graph K ( n , k ) einen Hamiltonkreis enthält, wenn es eine nichtnegative ganze Zahl k gibt , sodass k = 1. ^{[ 9 ]} Insbesondere besitzt der ungerade Graph O _{_n} einen Hamiltonkreis, falls n ≥ 4. Schließlich vervollständigten Merino, Mütze und Namrata im Jahr 2023 den Beweis der Vermutung. ^{[ 10 ]}${\displaystyle a}$${\displaystyle n=2k+2^{a}}$

Für n < 3k enthält der Knesergraph K ( n , k ) keine Dreiecke. Allgemeiner gilt: Für n < ck enthält er keine Cliquen der Größe c , wohl aber für n ≥ ck . Obwohl der Knesergraph für n ≥ 2k + 2 stets Zyklen der Länge vier enthält, kann der kürzeste ungerade Zyklus für Werte von n nahe 2k eine variable Länge aufweisen. ^{[ 11 ]}

Der Durchmesser eines zusammenhängenden Kneser-Graphen K ( n , k ) ist ^{[ 12 ]}$${\displaystyle \left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.}$$

Das Spektrum des Kneser-Graphen K ( n , k ) besteht aus k + 1 verschiedenen Eigenwerten : Darüber hinaus tritt mit Vielfachheit für auf und hat Vielfachheit 1. ^{[ 13 ] [ 14 ]}$${\displaystyle \lambda _{j}=(-1)^{j}{\binom {nkj}{kj}},\qquad j=0,\ldots ,k.}$$${\displaystyle \lambda _{j}}$${\displaystyle {\tbinom {n}{j}}-{\tbinom {n}{j-1}}}$${\displaystyle j>0}$${\displaystyle \lambda _{0}}$

Der Satz von Erdős–Ko–Rado besagt, dass die Unabhängigkeitszahl des Kneser-Graphen K ( n , k ) für ist , aber wenn , dann enthält jede Knotenteilmenge der Größe größer als die Unabhängigkeitszahl einen Knoten, der zu mindestens anderen Knoten in benachbart ist . ^{[ 15 ]}${\displaystyle n\geq 2k}$$${\displaystyle \alpha (K(n,k))={\binom {n-1}{k-1}},}$$${\displaystyle n>10000k}$${\displaystyle S}$$${\displaystyle \left({\frac {1}{2}}-O\left({\sqrt {\frac {k}{n}}}\right)\right){\binom {nk-1}{k-1}}}$$${\displaystyle S}$

Der Johnson-Graph J ( n , k ) ist ein Graph, dessen Knoten k -elementige Teilmengen einer n- elementigen Menge bilden. Zwei Knoten sind benachbart, wenn sie in einer ( k  -1) -elementigen Menge zusammentreffen. Der Johnson-Graph J ( n , 2) ist das Komplement des Kneser-Graphen K ( n , 2) . Johnson-Graphen sind eng mit dem Johnson-Schema verwandt ; beide sind nach Selmer M. Johnson benannt .

Der verallgemeinerte Knesergraph K ( n , k , s ) hat dieselbe Knotenmenge wie der Knesergraph K ( n , k ) , verbindet aber jeweils zwei Knoten, wenn sie Mengen entsprechen, die sich in s oder weniger Elementen schneiden. ^{[ 11 ]} Daher gilt K ( n , k , 0) = K ( n , k ) .

Der bipartite Knesergraph H ( n , k ) besitzt als Knoten Mengen von k und n − k Elementen aus einer Menge von n Elementen. Zwei Knoten sind durch eine Kante verbunden, wenn die eine Menge eine Teilmenge der anderen ist. Wie der Knesergraph ist er knotentransitiv mit Grad n. Der bipartite Knesergraph kann als bipartite Doppelüberdeckung von K ( n , k ) konstruiert werden , indem jeder Knoten verdoppelt und jede Kante durch ein Kantenpaar ersetzt wird, das entsprechende Knotenpaare verbindet. ^{[ 16 ]} Der bipartite Knesergraph H (5, 2) ist der Desargues-Graph und der bipartite Knesergraph H ( n , 1) ist ein Kronengraph . ${\displaystyle {\tbinom {nk}{k}}.}$

• Weisstein, Eric W. „Kneser Graph“ . MathWorld .
• Weisstein, Eric W. „Odd Graph“ . MathWorld .