Kneser-gráf

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

Kneser-gráf
A KG(5,2) Kneser-gráf izomorf a Petersen-gráffal
Névadó	Martin Kneser
Csúcsok száma	${\displaystyle \textstyle {\binom {n}{k}}}$
Élek száma	${\displaystyle \textstyle {\binom {n}{k}}{\binom {n-k}{k}}/2}$
Átmérő	${\displaystyle \left\lceil {\frac {k-1}{n-2k}}\right\rceil +1}$
Kromatikus szám	${\displaystyle \left\{{\begin{array}{ll}n-2k+2&n\geq 2k\\1&{\text{különben}}\end{array}}\right.}$
Egyéb	${\displaystyle {n-k} \choose k}$-reguláris
Jelölés	KGn,k, K(n,k)

A Kneser-gráf igen egyszerűen definiált gráf, mégis kromatikus számának pontos meghatározása hosszú ideig megoldatlan probléma volt.

Definíció

Ha ${\displaystyle 1\leq k<n}$ természetes számok, akkor a ${\displaystyle KG(n,k)}$ Kneser-gráf csúcspontjait egy ${\displaystyle n}$-elemű halmaz ${\displaystyle k}$-elemű részhalmazai alkotják, két csúcsot összekötünk, ha a megfelelő részhalmazok diszjunktak.

Tulajdonságai

A ${\displaystyle KG(n,k)}$ gráfnak ${\displaystyle n \choose k}$ csúcsa van, és minden csúcsnak ${\displaystyle {n-k} \choose k}$ a fokszáma.

Példák

Példa nevezetes Kneser-gráfra: A Petersen-gráf, amely nem más, mint ${\displaystyle KG(5,2)}$.

Kapcsolódó tételek

A következő tételt Martin Kneser sejtésként fogalmazta meg 1955-ben.

Tétel: A ${\displaystyle KG(n,k)}$ kromatikus száma egyenlő ${\displaystyle (n-2k+2)}$-vel.

Ezt először Lovász László igazolta, algebrai topológiai eszközök felhasználásával, 1978-ban. Röviddel ezután Bárány Imre adott egy rövid levezetést Gale tételét használva. 2002-ben Joshua Greene még egyszerűbb levezetést adott a Borsuk-tétel felhasználásával.

A tétel érdekessége, hogy a témakör szokásos tételeitől eltérően, nem a felső, hanem az alsó korlát nehéz: ${\displaystyle \chi (KG(n,k))\leq n-2k+2}$ igazolása igen könnyű:

Az állítást igazolja, hogy ha megadjuk a csúcsok egy (n-2k+2) színnel való jó színezését. Minden olyan csúcsot, melynek megfelelő részhalmaz legkisebb eleme legfeljebb (n-2k+1), színezzük ki egy olyan színnel, melyet egyértelműen megfeleltetünk a legkisebb elemmel. A többi csúcsot színezzük ki az ${\displaystyle (n-2k+2)}$-edik színnel. Az így keletkezett színezés jó, mert ha két csúcs színe azonos, és ez a szín nem az ${\displaystyle (n-2k+2)}$-edik, akkor a két csúcs nincs összekötve, mert a nekik megfelelő részhalmazok legkisebb eleme megegyezik. Ha a szín az ${\displaystyle (n-2k+2)}$-edik, akkor a részhalmazok elemei ${\displaystyle n-(n-2k+1)=2k-1}$ különböző elem közül kerülhetnek ki, az ilyen ${\displaystyle k}$-elemű részhalmazok között azonban nincs két diszjunkt, tehát ezek a csúcsok sem lehetnek összekötve.

A ${\displaystyle K_{n}}$, vagyis az ${\displaystyle n}$ csúcsú teljes gráf élgráfjának komplementere a ${\displaystyle KG(n,2)}$-es Kneser-gráffal izomorf.

Címkézzük meg a csúcsokat 1-től ${\displaystyle n}$-ig. Ekkor minden élhez hozzárendelhető egy számpár aszerint, hogy melyik két csúcsot köti össze. Az élgráfban két csúcs pontosan akkor van összekötve, ha az eredeti gráfban a nekik megfelelő éleknek volt közös végpontjuk, vagyis ha a nekik megfelelő számpárokban van egy olyan szám, mely mindkettőben előfordul. Másként megfogalmazva, két csúcs akkor és csak akkor szomszédos, ha a kételemű részhalmazaik nem diszjunktak. Az eredeti gráf teljes volta miatt az élgráf csúcsai között az összes kiválasztható kételemű részhalmaz szerepel. Így az élgráf komplementerében is szerepel az összes, amelyek akkor és csak akkor vannak összekötve, ha a nekik megfelelő számhalmazok diszjunktak. Ez pedig megegyezik a ${\displaystyle KG(n,2)}$-es Kneser-gráf definíciójával.