next up previous contents
Next: Megszorított metszetű halmazrendszerek Up: Motiváció és irodalmi áttekintés Previous: Motiváció és irodalmi áttekintés

Explicit Ramsey-gráf konstrukciók

Ramsey 1930-ban megjelent nagyhatású eredménye [45] után Erdős és Szekeres [15] voltak az elsők, akik 1935-ben explicit felső korlátot bizonyítottak az R(t,t) Ramsey-számokra:

\begin{displaymath}R(t,t)\leq{2t-2\choose t-1}<4^t.\end{displaymath}

Erdős híres egzisztencia-tétele mutatta meg, hogy létezik az $N=\lfloor 2^{t/2}\rfloor$ csúcsú teljes gráfnak olyan kétszinezése, amely nem tartalmaz monokromatikus teljes részgráfot t csúcson, azaz:

\begin{displaymath}2^{t/2}\leq R(t,t).\end{displaymath}

Erdős fenti eredménye után persze hamar felmerült, hogy ha van ilyen szinezés, akkor jó lenne expliciten is konstruálni ilyet. Hosszú ideig csak egy monokromatikus, teljes t-es nélküli (t-1)2 csúcsú gráf konstrukciója volt ismert. 1972-ben Abbot [1] adott egy nem-konstruktív bizonyítást arra, hogy minden rögzitett k-ra létezik egy explicit konstrukció, amely elegendően nagy t-re monokromatikus, teljes t-es nélküli szinezését adja a tk csúcsú teljes gráfnak.

Nagy mutatott 1972-ben [42] ct3 csúcsú gráfot, majd Frankl [16] adott először t-ben szuper-polinomiális méretű explicit konstrukciót.

Egyszerűbb konstrukciót talált, lényegileg ugyanolyan renben növekedő csúcsszámra híres cikkében Frankl és Wilson [18]. Teljes, monokromatikus t-es nélküli gráfjuk csúcsszáma:

\begin{displaymath}\exp\left(({1\over4}-\varepsilon){(\log t)^2\over\log\log t}\right).\end{displaymath}



Vince Grolmusz
1999-11-08