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

4. Általános ismeretek

4. Általános ismeretek

Jelölje I ( r , g ) azt a legkisebb pozitív egész számot, amelyre van I ( r , g ) csúcsú r -reguláris g bőségű gráf. Az Alapfeladat az I ( r , g ) függvény pontos leírását követeli meg. Lássuk mi ismert eddig vele kapcsolatban!

Már az sem magától értetődő, hogy I ( r , g ) minden értékpárra értelmezett. Ennek igazolása egyenértékű a majd később vizsgálandó 17. feladat megoldásával.

12. feladat Bizonyítsuk be, hogy

I ( r , g ) ? 2 · 1 + ( r - 1 ) + ( r - 1 ) 2 + ( r - 1 ) g 2 - 1 , ha g páros; 1 + r + r · ( r - 1 ) + r · ( r - 1 ) 2 + r · ( r - 1 ) g - 3 2 , ha g páratlan.

A képlet jobb oldalán szereplő kifejezést a továbbiakban I * ( r , g ) -vel jelöljük. Röviden:

I * ( r , g ) = 2 · ( r - 1 ) g 2 - 1 r - 2 , ha g páros; 1 + r · ( r - 1 ) g - 1 2 - 1 r - 2 , ha g páratlan.

Azokat az r -reguláris g bőségű gráfokat, amelyeknek csak I * ( r , g ) csúcsa van Moore gráfoknak nevezzük. A Moore gráfok különlegesen tömör, szimmetrikus struktúrák. Az I ( r , g ) függvényről már sok tapasztalatot szereztünk. Haladjunk sorba g szerint növekedve a lehetőségeken!

Az első tartalmas esetet g = 3 jelenti. A bőségre vonatkozó feltétel így fogalmazható át: nincs hurokél, és bármely két csúcs között legfeljebb egy él található, tehát a gráf egyszerű. A legkisebb r -reguláris példát az az ( r + 1 ) csúcsból álló gráf adja, amelynek bármely két csúcsát él köti össze. Ez az ( r + 1 ) csúcsú teljes gráf. Tehát I ( r , 3 ) = r + 1 .

A g = 4 esetet a 3. feladatban általában tisztáztuk. Láttuk, hogy I ( r , 4 ) = 2 r , és a minimális esetnek az a gráf felel meg, amelynek csúcsai két r elemű csoportba oszthatók, és két csúcs között pontosan akkor van él, ha a két csúcs különböző csoportban van. Az ilyen gráfot teljes páros gráfnak nevezik, jele K r , r .

A g = 5 esetről azt láttuk, hogy az I * ( r , g ) = r 2 + 1 alsó korlát az r = 3 esetben teljesíthető (Petersen-gráf), r = 4 esetén viszont nem. Az r = 2 esetet még nem is néztük, erre nyilvánvalóan az ötszög (5 hosszú kör) adja a legkisebb példát.

Az r = 2 és 3 esetben látott egyszerű konstrukció után talán meglepő, hogy ezeken kívül még legfeljebb két r érték esetén lehet Moore gráfot szerkeszteni.

Hoffman-Singleton tétel (1960): Ha létezik r 2 + 1 csúcsú, r -reguláris, 5 bőségű gráf, akkor r = 2 , 3 , 7 vagy 57.

A tétel bizonyítása különösen szép, de nehéz lineáris algebrai segédeszközöket használ. Ezért itt nem közöljük a levezetést, az érdeklődőknek az [1] és [5] könyveket ajánljuk. A tétel nem állítja, hogy a felsorolt négy esetben van is Moore gráf. Amint láttuk, az első két esetben van egy-egy ilyen gráf, r = 7 -re Hoffman és Singleton a tétellel egy időben adtak példát (mely szintén egyértelmű), különleges gráfukkal az 5-6. részben ismerkedünk meg. Az r = 57 eset viszont a mai napig nyitott, senki sem tudott még szerkeszteni 57-reguláris 5 bőségű gráfot 3250 csúccsal, de megcáfolni sem sikerült ennek létezését. Játsszunk el a gondolattal, hogy van ilyen gráf!

13. feladat Hány öt-, illetve hány hatszög található egy 3250 csúcsú 57-reguláris 5 bőségű gráfban (ha van ilyen)?

Nézzük a g = 6 esetet! Láttuk, hogy a természetesen adódó 2 · 1 + ( r - 1 ) + ( r - 1 ) 2 alsó korlát r = 4 és r = 5 esetén megvalósítható. Ha az olvasót a 9. feladatban adott táblázatok az ortogonális latin négyzetek témájára és a véges geometriára emlékeztették, akkor jóra gondolt. A konstrukció legegyszerűbben a projektív geometriával hozható kapcsolatba. Az általános esetben 1 + ( r - 1 ) + ( r - 1 ) 2 darab A -jelű és ugyanennyi B -jelű pont van (lásd a 6. ábrát). Feleltessük meg a B jelű pontokat egy ( r - 1 ) -edrendű projektív sík pontjainak, az A jelűeket pedig ugyanezen sík egyeneseinek. A gráf két pontját akkor kössük össze éllel, ha a nekik megfelelő objektumok egyike egyenes, a másik pedig olyan pont, amely illeszkedik az egyenesre.

Azt állítjuk, hogy ez a gráf megfelelő. Valóban, a projektív síkok alaptulajdonságai miatt a csúcsok száma 2 ( 1 + ( r - 1 ) + ( r - 1 ) 2 ) , minden egyenesre r - 1 + 1 = r pont, és minden pontra ugyanennyi egyenes illeszkedik, tehát a gráf r -reguláris. Másrészt, mivel páros a gráf, ezért csak páros hosszúságú körök lehetnek benne, azaz ahhoz, hogy a bőség legalább 6 legyen, csak a négy hosszúságú köröket kell kizárni. Ilyen pedig azért nincs, mert nincs két különböző egyenes 2 közös ponttal. Tehát a legkisebb kör hossza legalább 6. Hat hosszúságú kör viszont van: a sík bármely háromszögének három csúcsa és három oldalegyenese ilyet alkot. Ezzel minden q -adrendű projektív síkból kapunk ( q + 1 ) -reguláris, 6 bőségű gráfot minimális csúcsszámmal.

Azt is könnyen végiggondolhatjuk, hogy ez a konstrukció fordítva is működik: minden r -reguláris, 2 ( r 2 + r + 1 ) csúcsú, 6 bőségű gráf segítségével lehet r -rendű projektív síkot szerkeszteni. Ezekhez a 9. feladat megoldásában megfogalmazott (1), (2), (3) követelményeket kell az általános esetben is számba venni.

g //>// 6 esetén Moore gráfokról további ismereteink csak a g = 2 n páros esetről vannak. Ezeket általánosított n -szögek nek is nevezik,egy Feit és Higman nevéhez fűződő eredmény szerint ilyenek csak n = 3 , 4 , 6 , 8 esetén létezhetnek. Általánosított négy-, hat- és nyolcszögeket véges projektív terek bilineáris formái segítségével lehet konstruálni, ez meghaladja ennek a könyvnek a kereteit (lásd például [3] és [6]).

14. feladat Határozzuk meg I ( 3 , 7 ) értékét!

Azt a keveset, amit I ( r , g ) nagyságrendjéről tudni lehet, a Lovász László feladatgyűjteményéből ([7]) származó 17., 18. feladatok kapcsán ismertetjük. Ehhez a 15., 16. – az Alapfeladathoz képest fordított jellegű kérdések – előkészítésül szolgálnak. Használni fogjuk a gráf átmérőjének fogalmát, amin a legkisebb olyan d pozitív egész számot értjük, amelyre teljesül, hogy bármely két csúcs között van olyan út, amely legfeljebb d hosszúságú.

15. feladat Mutassuk meg, hogy bármely d átmérőjű, r maximális fokú gráfnak legfeljebb 1 + r + r ( r - 1 ) + + r ( r - 1 ) d - 1 csúcsa van és egyenlőség esetén a gráf reguláris.

16. feladat Mutassuk meg, hogy a 15. feladatban az egyenlőséget teljesítő gráf a g = 2 d + 1 bőséghez tartozó Moore gráf. Mondható-e hasonló állítás a Moore gráfok átmérőjéről?

17. feladat (Erdős–Sachs) Bizonyítsuk be, hogy ha r ? 2 és g ? 2 , akkor létezik r -reguláris, g bőségű gráf véges sok csúccsal.

Láttuk már, hogy 3 és 4 bőségű gráfok minden r ? 2 regularitási fok esetén léteznek. Azt fogjuk indukcióval bizonyítani, hogy ha g bőségű gráfok léteznek bármely r regularitási fokkal, akkor ( g + 1 ) bőségű gráfok is léteznek tetszőleges regularitással.

Van 2-reguláris ( g + 1 ) bőségű gráf: egy ( g + 1 ) hosszú kör. Az ( r + 1 ) -reguláris ( g + 1 ) bőségű gráf szerkesztésekor egy r -reguláris ( g + 1 ) bőségű G gráf több példányát varrjuk össze. Legyen G csúcsainak száma n . Szabásminta céljából tekintsünk egy n -reguláris, g bőségű N gráfot.

7. ábra. 5 bőségű 3-reguláris gráfhoz ötszögek K 5 , 5 szabásmintával

N minden csúcsát helyettesítsük egy G gráffal, a N egy csúcsából induló n élt indítsuk az aktuális G különböző csúcsaiból.

Az így kapott gráf ( r + 1 ) -reguláris lesz, hiszen G bármelyik példányában bármelyik csúcs foka eggyel nőtt. Azért kapunk ( g + 1 ) bőségű gráfot, mert egy G gráfon belül lesz ( g + 1 ) hosszú kör, de rövidebb nem és bármely olyan kör, amely több G között megy az N tulajdonsága révén eleve legalább g hosszú, de kell még tartalmaznia mindegyik általa érintett G gráfon belül még legalább egy-egy élt.

Ez a konstrukció nagyon általános, de ennek fejében messze nem optimális. Ha az 5 bőségű gráfokat a 2-reguláris ötszögből kezdenénk el szerkeszteni a 4 bőségű teljes páros gráfok szerinti szabásmintákkal, akkor 3-reguláris gráfra 5 · 10 = 50 csúcsú gráfot kapnánk, ezt továbbszerkesztve 4-regulárisra 50 · 100 = 5000 csúcs adódna, általában a g bőségű 5-reguláris gráfunknak 1 2 · 100 2 r - 3 csúcsa lenne. Láttuk, hogy a kis esetekre talált I ( 3 , 5 ) = 10 , I ( 4 , 5 ) = 19 optimális értékek ennél sokkal kisebbek, csakúgy mint az eddig talált egyetlen általános érvényű alsó korlát I * ( r , 5 ) = r 2 + 1 .

A következő feladatban viszont anélkül adunk ennél sokkal jobb felső becslést, hogy bármit konstruálnánk. A (iii)-ban adott képlet a 15. feladatban adott formula megfelelő változatának rövidített alakja.

18. feladat Legyen a G gráf csúcsainak száma minimális az r -reguláris legalább g bőségű gráfok között. Bizonyítsuk be, hogy ekkor:

(i) G átmérője legfeljebb g ;

(ii) G bősége pontosan g ;

(iii) G csúcsainak száma legfeljebb r r - 2 ( r - 1 ) g .

A Sauertől származó c · ( r - 1 ) g - 2 felső korlát ( c konstans) kicsit jobb az előző feladatból adódónál, de még mindig inkább I * ( r , g ) négyzetéhez van közel, mint magához I * ( r , g ) -hez. Hihetetlenül nagy a sok konkrét esetben megtalált „legkisebb” gráf csúcsainak száma és az általános elméletben talált legkisebb felső korlát közti különbség. A téma egyik szakértője, Bollobás Béla szerint elképzelhető, hogy van olyan konstans, amelynél I * ( r , g ) és I ( r , g ) különbsége minden esetben kisebb, de már az is komoly eredménynek számítana, ha sikerülne igazolni, hogy a 2-es kitevő akármilyen kicsit is csökkenthető, azaz ha volna olyan ? //>// 0 , amelyre bármely r ? 3 és minden elég nagy g esetén I ( r , g ) //<// I * ( r , g ) 2 - ? .