Kneser gráfok

• A Kneser-gráfok gráfok egy két paraméteres serege. K(n,k) csúcshalmzát egy n elemû alaphalmaz k elemû részhalmazai alkotják. Két csúcs akkor és csak akkor van összekötve, ha a megfelelõ halmazok diszjunktak. K(n,k) az üres gráf, ha n < 2k.

  A továbbiakban feltesszük, hogy n legalább 2k. Bevezetjük a p=n-2k (n=2k+p) nemnegatív paramétert.

  K(2k,k) független élekbõl áll. K(5,2) A Petersen-gráf.

• K(n,k) csúcs színezéseit vizsgáljuk. Kromatikus számára könnyû egy n-k+1-es felsõ becslést adni: Az aalphalmaz legyen a {1,2,3,...,n} alaphalmaz. A színhalmaz legyen {1,2,3,...,n-k+1}. Egy csúcs (az alaphalmaz egy k elemû részhalmaza) színként kapja a minimális elemét.

  Ez a színezés javítható, ha a színhalmazt {1,2,...,n-2k}-nak vesszük. Ekkor néhány halmaz színezetlen marad, de erre megszorítva a gráfot egy párosítást kapunk. Így 2 plusz szín felhasználásával K(n,k) kiszínezhetõ n-2k+2 színnel.

• A kromatikus szám alsó becslése jóval nehezebb. ELõször Lovász László nehéz topológiai meggondolásaokkal bizonyította be, hogy az n-2k+2 szín szükséges is. Bizonyításának ismeretében Bárány Imre egy (Borsuk-tétel ismeretében) egyszerû bizonyítást publikált. mi A. Schrijver élesítését mondjuk el, ami Bárány Imre módszereivel igazolja, hogy K(n,k) egy részgráfja is kívánja az n-2k+2 színt. Ez a részgráf csúcskritikus lesz a kromatikus számra (azaz bármely csúcsát elhagyva kormatikus száma csökken eggyel).

• K*(n,k) definíciójában az alaphalmazunk újból {1,2,3,...,n} lesz. Ezen számok között a ``modulo szomszédságot'' definiáljuk, azaz a szokásos szomszédság mellett 1 és n is szomszédos lesz. K*(n,k) csúcsit az alaphalmaz azzon k elemû részhalmazai alkotják, amelyek nem tartalmaznak két szomszédos elemet.

  K(5,2) egy 5 hosszú kör lesz.

• Tétel: (i) K*(n,k) kromatikus száma n-2k+2.

  (ii) K*(n,k) bármelyik csúcsát elhagyva egy n-2k+1 kromatikus gráfot kapunk.

(i) bizonyítása: belátjuk, hogy S^p-n (a p dimenziós gömbfelületen, azaz a p+1 dimenziós tér egységvektoai által alkotott halmazban) kijelölhetõk v₁,v₂,v₃,...,v_n pontok a következõknek megfelelõen. A fenti pontok indexeiken keresztül azonosíthatók a redukált Kneser-gráf alaphalmazával. Így a redukált Kneser-gráf csúcshalmaza azonosítható a v-vektorok k-asaiból álló rendszerekkel. A szúkséges tulajdonság a következõ lesz: Minden nyilt félgömbhóz lesz olyan csúcsa a redukált Kneser-gráfnak, hogy a hozzá tartozó vektor k-as minden eleme a nyilt félgömbbe essen.

Ha ezt tudjuk akkor a bizonyítás hátralévõ része egyszerû. Tegyük fel, hogya redukált gráf kiszínezhetõ n-2k+1=p+1 színnel. Minden színhez feleltessünk meg a gömbfelületünkön egy nyilt halmazt: azon pontok halmazát, amelyekkel mint középponttal rajzolt nyilt félgömbök tartalmaznak egy adott adott színû csúcsnak megfeleleõ vektor k-as minden elemét. A megkövetelt tulajdonság miatt a fenti módon definiált p+1 nyilt halmaz lefedi a gömbfelületet. Borsuk tétele alapján lesz olyan halmaz (mondjuk a kék színhez tartozó halmaz), amely tartalmaz átellenes pontpárt. Az átellenes két pont azért tartozott ehhez a nyilt halmazhoz, mert mindegyik köré rajzolt félgömbfelület tartalmazzott kék vektor k-ast. Az átellenesség miatt azzonban ezek diszjunktak. Így a közös színük ellentmondást ad.

A szükséges vektorrendszer létezésének bizonyításához felírunk egy vektorrendszert. legyen u_i=(-1)_i(1,i,i²,i³,i⁴,..., i^p). Természetesen ez a vektor nem lesz egységvektor. Legyen v_i a u_i vektor egységvektorrá normálva (v_i=u_i/||u_i||). A továbbiakban csak az elvárt tulajdonságot kell igazolni erre a vektorrendszerre.

Ehhez vegyünk egy tetszõleges a vektort és belátjuk, hogy van k darab u_i vektorunk, hogy a.u_i>0 mindegyikre teljesül és a vektor k-as a redukált gráf egy csúcsának felel meg. Ez átfogalmazva azt jelenti, hogy tetszõleges legfeljebb p-ed fokú, nem 0 poliom esetén (-1)¹p(1),(-1)²p(2),(-1)³p(3), (-1)⁴p(4),...,(-1)ⁿp(n) lesz k darab pozitív elem úgy, hogy ne legyen közöttük két szomszédos (az elsõ e's utolsó elemet is szomszédosnak gondolva a teljes sorozatban).

Ennek igazolása a mohó algoritmussal történhet. Sorban definiáljuk az a₁,a₂,a₃,... indexeket. a₁ az elsõ index amelyre (-1)¹p(1),(-1)²p(2),(-1)³p(3), (-1)⁴p(4),... sorozat megfelelõ eleme pozitív. a₂ az elsõ a₁-et követõ, de nem rákövetkezõ pozitív elem a (-1)¹p(1),(-1)²p(2),(-1)³p(3), (-1)⁴p(4),... sorozatban. a₃ az elsõ a₂-et követõ, de nem rákövetkezõ pozitív elem a (-1)¹p(1),(-1)²p(2),(-1)³p(3), (-1)⁴p(4),... sorozatban...

Belátjuk, hogy a mohó algoritmus mûködik, azaz a_k nem haladja meg n-et és a₁=1 és a_k=n egyszerre nem lehetséges. Ennek igazolása a p polinom gyökeinek vizsgálatával történik.