Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

5. A Hoffmann–Singleton-gráf

5. A Hoffmann–Singleton-gráf

Ebben és a következő fejezetben megismerkedünk egy olyan 50 csúcsú 5 bőségű 7-reguláris gráffal, amelyet korábban ígértünk. Vizsgálatunk úgy kezdődik, ahogy az 1., 3., 10., 11. feladatokban a páros bőségű gráfok elemzésének álltunk neki.

Legyen a gráf két szomszédos csúcsa A és B , A további szomszédai B 1 , , B 6 , míg B további szomszédai A 1 , , A 6 . Az eddig felsorolt 14 csúcs között nincs más él, mert a gráf bősége 5. Nem említettünk még 36 csúcsot, ezek között van a B 1 , , B 6 pontok 6-6 szomszédja, és egyben az A 1 , , A 6 pontok 6-6 szomszédja is. Az A i és A j pontoknak ( i ? j ) nem lehet közös szomszédja e 36 pont között, mert B már egy közös szomszédjuk, és nem hozhatunk létre négyszöget. Tehát a 36 csúcs hat darab 6 pontból álló csoportra osztható fel a B 1 , , B 6 pontokkal való szomszédságuk szerint, és szintén hat darab 6-os csoportba osztható az A 1 , , A 6 pontokkal való szomszédság alapján. Egy A i szerinti csoportnak és egy B j szerinti csoportnak legfeljebb egy közös eleme lehet, mert ha kettő lenne, mondjuk x és y , akkor lenne négyszög a gráfban: A i x B j y A i .

8. ábra.

Tehát minden ( A i , B j ) párhoz legfeljebb egy olyan pont van az új pontok között, amely mindkettővel szomszédos. Ez 36 pont esetén csak úgy lehetséges, ha pontosan egy pont tartozik minden párhoz. Ezek után a 36 pontot a párokkal fogjuk jelölni, ( A i , B j ) azt az egyetlen pontot jelöli, amely A i -nek és B j -nek is szomszédja. A i -t és B j -t az ( A i , B j ) pont „koordinátáinak” is nevezhetjük.

Eddig a gráfban nincs 5-nél rövidebb kör és már csak a 36 darab ( A i , B j ) típusú csúcs közötti éleket kell megfelelően behúzni. Fogalmazzuk meg ennek szabályait!

(1) Mindegyik csúcsból 5 él indul ki.

(2) Ha két csúcs valamelyik koordinátája megegyezik, akkor a gráfban nem szomszédosak (hogy ne kapjunk háromszöget, például A 1 ( A 1 , B 2 ) ( A 1 , B 3 ) A 1 ).

(3) Egyik csúcsból sem megy két olyan csúcshoz is él, melyek valamelyik koordinátája megegyezik. (ha például az ( A 1 , B 1 ) csúcs ( A 2 , B 2 ) -vel és ( A 5 , B 2 ) -vel is szomszédos lenne, akkor B 2 ( A 2 , B 2 ) ( A 1 , B 1 ) ( A 5 , B 2 ) B 2 négyszög lenne a gráfban).

Nem nehéz végiggondolni, hogy a (2), (3) tulajdonságok nem csak szükségesek, de garantálják is, hogy minden olyan kör, amely nem csak az ( A i , B j ) típusú pontokat tartalmazza legalább 5 hosszúságú. A gráfban máris van 5 hosszúságú kör, például A B A 1 ( A 1 , B 1 ) B 1 A . Ezért már csak egy feltétel marad, amelyben már csak a 36 ( A i , B j ) típusú pont és a közöttük húzott élek alkotta G gráfra vonatkozik:

(4) G bősége legalább 5.

9. ábra.

Rendkívül nehéz eligazodni e sok szabály és sok csúcs között. Ezért egy önkorlátozást vezetünk be abban a reményben, hogy ezzel nem zárjuk ki a megoldást, de könnyebben áttekinthető struktúrát kapunk:

(5) Az élek szimmetrikus párokat alkotnak, azaz ha ( A i , B j ) és ( A k , B l ) között van él, akkor ( A i , B l ) és ( A k , B j ) között is van.

Vizsgáljuk meg, mit jelentenek a szabályok két „sor”, mondjuk az ( A 1 , B 1 ) , ( A 1 , B 2 ) , , ( A 1 , B 6 ) és az ( A 2 , B 1 ) , ( A 2 , B 2 ) , , ( A 2 , B 6 ) csúcsok közti élekre vonatkozóan!

10. ábra.

A (2) szabály szerint soron belül nincs él, csak a sorok között. Ugyanezen szabály szerint „függőleges” élek sincsenek, tehát bármelyik ( A 1 , B i ) -t egy olyan ( A 2 , B j ) -vel köti össze él, amelyre i ? j . A (3) szabály szerint legfeljebb egy él indul ki mindegyik csúcsból. Mivel mindegyik soron kívül még 5 másik sor van, így az (1) szabály következtében pontosan egy él indul ki mindegyik csúcsból. Ha az (5) szabályt is figyelembe vesszük, akkor azt látjuk, hogy a részgráf élei párbaállítják a B i koordinátákat, például:

B 1 - B 3 , B 2 - B 5 , B 4 - B 6 .

Ha A 1 és A 3 sorát, , majd A 1 és A 6 sorát vizsgáljuk, akkor a B i -k négy további párosítását kapjuk. A (3) szabály szerint az így kapott 5 · 3 = 15 pár között nincsenek azonosak.

Tekintsük a B 1 , , B 6 szimbólumokat focicsapatoknak és fogalmazzuk meg eddigi eredményeinket a foci nyelvén!

I. Ha kiválasztunk egy A i és egy A j csúcsot ( i ? j ), akkor a nekik megfelelő ( A i , B 1 ) , , ( A i , B 6 ) és ( A j , B 1 ) , , ( A j , B 6 ) csúcsok közötti élek a B 1 , , B 6 csapatok egy párosítását, egy körmérkőzés egy lehetséges fordulóját jelölik ki.

II. Ha az A i csúcsot rögzítjük és egyenként mellévesszük az összes többi A j csúcsot, akkor az I.-ben adott értelmezéssel a B 1 , , B 6 csapatok egy teljes bajnokságát kapjuk, amely során minden csapat mindegyikkel pontosan egyszer találkozik.

Bajnokságon most fordulók egy olyan rendszerét értjük, amelynek során mindenki mindenkivel pontosan egyszer játszik, a fordulók sorrendje nem számít. A gráfelmélet nyelvén (lásd Gyárfás András írását) a forduló a B 1 , , B 6 csúcsú B teljes gráf egy faktora, a bajnokság pedig B egy faktorizációja.

Ha tudunk bajnokságokat szervezni, akkor biztosan meg is találjuk a keresett gráfot? Tegyük fel, hogy sikerült a 15 A i A j párnak megfelelő 15 olyan fordulót összeállítani 6 csapat ( B 1 , , B 6 ) között, hogy II. is teljesül: bármelyik A i -t tartalmazó 5 A i A k pár 5 olyan fordulót határoz meg, amely együtt egy bajnokság. Gráfunkban ennek megfelelően pontosan akkor húzunk be ( A i , B j ) és ( A k , B l ) között élt, ha i ? k és j ? l továbbá az A i A k párnak megfelelő fordulóban B j és B l egymással játszik. Könnyű ellenőrizni, hogy ekkor a gráfunkra kirótt (1), (2), (3), (5) feltételek mind teljesülni fognak, (4)-gyel kapcsolatban azonban egyelőre nem sokat mondhatunk. Nem is csoda: eddigi gondolatmenetünk kis módosítással 7-reguláris gráf helyett tetszőleges r -reguláris gráffal is elmondható lett volna, az általános eset végén egy ( r - 1 ) csapatból álló bajnokságot vizsgálnánk. Szükséges lesz előbb megismerkednünk a bajnokságszervezés egy-két fortélyával és meg kell értenünk, mitől különleges a 6-os szám.