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

3. Az Alapfeladat három esete

3. Az Alapfeladat három esete

Az 1., 3., 4. feladatokhoz hasonlóan a továbbiakban is az alábbi problémára keressük a választ:

Alapfeladat Adott r és g esetén egy r -reguláris g -bőségű gráfnak legalább hány csúcsa van?

A szélső esetnek megfelelő gráf (esetleg gráfok) gyakran rendkívül szimmetrikus(ak), mint a szabályos poliéder(ek) vagy mint a véges síkok.

9. feladat Válaszoljunk az Alapfeladat kérdésére az r = 4 , g = 6 esetben!

Most az 1. és 3. feladatok megoldásához hasonlóan kezdjük a megoldást, az egymással szomszédos A , B csúcsokból indulunk ki. A további szomszédait jelölje B 0 , B 1 és B 2 , a B szomszédait pedig A 0 , A 1 és A 2 .

6. ábra.

Az A i további szomszédainak (lásd az ábrát) és a B j -k még nem említett szomszédainak egymástól és az eddig említett összes csúcstól is különbözniük kell, hogy ne jöjjön létre öt hosszúságú, vagy ötnél rövidebb kör. Így máris 26 csúcsa van a gráfnak.

Vajon lehetséges-e, hogy összesen csak ennyi csúcsa van? Össze tudjuk-e kötni a „végeken” található csúcsokat úgy, hogy teljesüljenek a feladat feltételei? Fogalmazzuk meg, hogy mit kell teljesíteniük az új éleknek!

Képzeljük úgy, hogy az éleket az A i j szigetek felől rajzoljuk meg!

(1) Mindegyik csúcsból ( A i j -ből) pontosan három él indul, egy-egy megy a B 0 x , a B 1 y és a B 2 z csúcsok felé (hogy ne legyen 4-es kör, például A i j B 0 x B 0 B 0 y A i j ).

(2) Az A i x és az A i y csúcsoknak nem lehet közös szomszédja (hogy ne legyen 4-es kör, például A i A i x B u v A i y B i ).

(3) Két különböző csúcsnak nem lehet két közös szomszédja (hogy ne legyen 4-es kör, például A i j B u v A k l B x y A i j ).

Az (1) feltétel szerint A i j szomszédai kódolhatók három számmal ( x -szel, y -nal és z -vel). A (2) feltétel azt jelenti, hogy az A i 0 -hoz, A i 1 -hez és A i 2 -höz tartozó számhármasok olyan 3 × 3 -as táblázatot alkotnak, amelynek minden oszlopában mindegyik szám legfeljebb egyszer (így pontosan egyszer) fordul elő. A (3) feltétel azt jelenti, hogy a 9 számhármas közül bármelyik kettő legalább két helyen eltér egymástól. Nem nehéz megadni 3 ilyen 3 × 3 -as táblázatot. Egy példa:

0 0 0 1 1 1 2 2 2 , 0 1 2 1 2 0 2 0 1 , 0 2 1 1 0 2 2 1 0 .

Tehát a szigetek száma legalább 26.

A következő feladat megoldásához arra van szükség, hogy jobban megértsük az előző megoldás végén adott konstrukciót. A salakmotorversenyek szervezőjének (lásd Montágh Balázs cikkét ugyanebben a kötetben) segítsége is jól jöhet.

10. feladat Válaszoljunk az Alapfeladat kérdésére az r = 5 , g = 6 esetben!

E feladat megoldására a következő fejezetben térünk ki. Az alábbi probléma váratlanul nehéz, pedig a paraméterek értékét az előző két esethez képest nem növeltük.

11. feladat Válaszoljunk az Alapfeladat kérdésére az r = 4 , g = 5 esetben!

Ha a 4. feladat megoldásának mintájára indulunk el, akkor rájöhetünk, hogy legalább 1 + 4 + 4 · 3 = 17 csúcsa van a gráfnak. Most azonban hiába próbálkozunk a „végeken” található 12 csúcs között megfelelően behúzni az éleket, nem sikerül. Sőt, 18 csúcsra sincs konstrukció, de 19-re már van. Mindezek bizonyítása a cikk végén található.