Leírás
A Ramsey-Turán-problémákat T. Sós Vera vetette fel:
adva vannak az n, m természetes számok és az F rögzített
gráf. Hány él lehet legfeljebb egy F-et részgráfként
elkerülő n csúcsú G gráfban, melynek legnagyobb független
halmaza nem nagyobb m-nél?
A kérdéssel különösen sokat foglalkoztak abban az esetben,
amikor F a négy pontú klikk. Szemerédi Endre 1972-ben
bebizonyította, hogy G-nek nem lehet (1/8 + o(1))n^2-nél
több éle, ha m=o(n). Néhány évvel később Bollobás Béla és
Erdős Pál konstruáltak n csúcsú gráfokat, amikre m=o(n),
éleik száma (1/8 - o(1))n^2, és nincs bennük K_4.
Ezekkel az eredményekkel nem zárult le a terület, továbbra
is kérdéses maradt, mit mondhatunk akkor, ha az élek száma
elég közel van n^2/8 - hoz.
Nemrég Lüders és Reiher, nagyban támaszkodva Fox, Loh és Zhao
eredményeire, belátták, hogy elég nagy n-re a K_4-ek felbukkanása
az 1/4 + m/n - (m/n)^2 élsűrűségnél következik be. A bizonyításukban
fontos szerepet játszik a Regularitási lemma, így m nem lehet
akármilyen kicsi, és n-nek óriásinak kell lennie.
Erre a tételre adunk egy másik, Regularitási lemmát nem használó
bizonyítást.