Négy hosszú kört nem tartalmazó gráfok

Alapkérdés: Legyen G egy n pontú egyszerű gráf, amely nem tartalmaz négy hosszú kört. Milyen sok éle lehet G-nek?

Nevezzük cseresznyének a G gráf két élet, ha közös végpontban futnak össze (a két él legyen e=xy és f=xz). Az x csúcsot a cseresznye közepének, y-t és z-t a cseresznye két szemének nevezzük. Egy látszólag új, az előzőektől független kérdést teszünk fel. Az erre adott válaszok azonben elvezetnek eredeti kérdésünk megválaszolásához.

Hány cseresznye van G-ben?

A G-beli cseresznyéket először közepüknél számoljuk össze. Egy x csúcshoz (d(x)2) darab cseresznye van, amleyek közepe x. Valóban az x közepű cseresznyék két élét az x-re illeszkedő d(x) darab él közül tetszőleges kettő alkothatja. Azaz ahhoz, hogy a cseresznyék számát megkapjuk a (d(x)2) számokat kell összegezni az összes x csúcsra.

Egy másik elindulás lehet a szemek csúcspárjai serint csoportosítani a cseresznyéket és ezen csoportosítás segítségével számolni meg azokat. (n2) darab lehetőség van a szempárokra. Ezen lehetőségek mindegyike mögött nulla vagy egy cseresznye van. Valóban, ha egy szempárhoz két (vagy több) cseresznye tartozna, akkor G-ben kialakulna egy négy hosszú kör, ami nem lehetséges. Így kapjuk, hogy a cseresznyék száma legfeljebb (n2).

A két gondolat összevetéséból kapjuk, hogy ha G csúcshalmaza {v1,v2,...,vn}, akkor (n2)>= (d(v1)2)+(d(v2)2)+ (d(v3)2)+...+(d(vn)2).

A jobb oldal alúlról becsülhető a Jensen-egyenlőtlenséget a (x2)=x(x-1)/2 konkáv függvényre alkalmazva:

(n2) >= (d(v1)2)+(d(v2)2)+ (d(v3)2)+...+(d(vn)2). >= n· ((d(v1)+d(v2)+...+d(vn))/n2).
A fokszámok átlaga 2|E(G)|/|V(G)|. Így a fenti egyenlőtlenség sorozat eredménye:
n(n-1)/2>=n·2|E(G)|/|V(G)|(2|E(G)|/|V(G)|-1)/2.
Rendezés után kapjuk a következőt:

Tétel: (Kővári Tamás, T. Sós Vera, Turán Pál)
Ha egy n pontú egyszerű gráf nem tartalmaz négy hosszú kört, akkor |E|<=1/2·n3/2+1/4·n.

A fenti tétel felső becslést ad ext(n;C4)-re. Alsó becslést egy n pontú egyszerű gráf konstruálásával adhatunk, amely gráf nem tartalmaz négy hosszú kört, de ``sok'' éle van. A konstrukcióban szereplő élszám alúlról becsüli ext(n;C4)-t. A következő `feladat' ahhoz ad segítséget, hogy nyerhetünk a fenti felső becsléssel aszimptotikusan azonos alsó becslést:

Legyen padott prím és tekintsük az (x,y) egész számpárokat mod p. Készítsül el azt a gráfot, amelynek csúcsai ezek a párok, és két csúcs, (x,y) és (x',y') között pontosan akkor halad él, ha x·x'+y·y'=1 mod p. Az ily módon esetleg létrejövő hurokéleket hagyjuk el a gráfból. Az így kapott gráf nem tartalmaz négy hosszú kört.