Kneser-gráf

Kneser-gráf
A KG(5,2) Kneser-gráf izomorf a Petersen-gráffal
Névadó	Martin Kneser
Csúcsok száma	$\textstyle {\binom {n}{k}}$
Élek száma	$\textstyle {\binom {n}{k}}{\binom {n-k}{k}}/2$
Átmérő	$\left\lceil {\frac {k-1}{n-2k}}\right\rceil +1$
Kromatikus szám	$\left\{{\begin{array}{ll}n-2k+2&n\geq 2k\\1&{\text{különben}}\end{array}}\right.$
Egyéb	${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 $1\leq k<n$ természetes számok, akkor a $KG(n,k)$ Kneser-gráf csúcspontjait egy $n$-elemű halmaz $k$-elemű részhalmazai alkotják, két csúcsot összekötünk, ha a megfelelő részhalmazok diszjunktak.

Tulajdonságai

A $KG(n,k)$ gráfnak $n \choose k$ csúcsa van, és minden csúcsnak ${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 $KG(5,2)$.

Kapcsolódó tételek

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

Tétel: A $KG(n,k)$ kromatikus száma egyenlő $(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: $\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 $(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 $(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 $(n-2k+2)$-edik, akkor a részhalmazok elemei $n-(n-2k+1)=2k-1$ különböző elem közül kerülhetnek ki, az ilyen $k$-elemű részhalmazok között azonban nincs két diszjunkt, tehát ezek a csúcsok sem lehetnek összekötve.

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

Címkézzük meg a csúcsokat 1-től $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 $KG(n,2)$-es Kneser-gráf definíciójával.