|
|
|
|||||||
| See by year | See by month | Jump to month | |||||||
Csaba Béla: A Ramsey-Turán-probléma K_4-ekre |
|
|||
|
|
||||
|
||||
| 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. |
||||
Export Event JEvents v3.1.8 Stable Copyright © 2006-2013