next up previous contents
Next: Bibliography Up: Eredményeink Previous: Megszorított metszetű halmazrendszerekre vonatkozó

Explicit Ramsey-gráf konstrukciók

A [25] cikkben (folyóirat-változat [21]) leírt fenti halmazrendszer explicit konstrukciójából rögtön adódik egy explicit Ramsey-gráf konstrukció is: legyen m=6, és legyen a gráfunk csúcshalmaza ${\cal H}$. Pontosan akkor szinezzük a G,H csúcspárt pirosra, ha $\vert G\cap H\vert$ páratlan, és kékre, ha páros. Ekkor nyilván a legnagyobb piros teljes részgráf mérete n (a Frankl-Wilson tételből, hiszen mind |H|, mind pedig |G| páros), vagy a sokkal egyszerűbb Párosfalva-Páratlanfalva tételből [4]). Ha $\vert G\cap H\vert$ páros, akkor persze nem lehet hárommal is osztható, ezért ismét a Frankl-Wilson tételből a legnagyobb kék teljes részgráf mérete $n\choose2$. Így egy új explicit Ramsey-gráf konstrukciót adtunk, amely logaritmikus nagyságrendje megegyezik a Frankl és Wilson által adott konstrukcióéval (a mi konstansunk a gyengébb).

Azonban a mi konstrukciónk könnyen általánosítható -- r különböző prímosztójú modulus segítségével -- r színre, a Frankl-Wilson konstrukcióról azonban nem látszik, hogy általánosítható lenne kettőnél több színre.


A Babai Lászlóval közös [5] cikkben úgy sikerült javítani és számottevően egyszerűsíteni a fenti Ramsey-gráf konstrukciót, hogy immár azonos nagyságrendet ad, mint a Frankl-Wilson eredmény [18], és továbbra is müködik a konstrukció több színre. A konstrukció alapötlete a következő: legyen p1 és p2 két prím, úgy hogy $\sqrt{n}<p_i<(1+\varepsilon)\sqrt{n}$. Legyen a gráfunk csúcshalmaza a 2n elemű halmaz összes n elemű részhalmaza. Szinezzük ki a GH csúcspárt kékre, ha $p_1 {\not\vert}\ \vert G\cap H\vert$, és pirosra akkor, ha nem kék, és $p_2{\not\vert}\ \vert G\cap H\vert$. A prímek választásából minden csúcspárt kiszinezünk, és a gráf nem tartalmaz $2n\choose p_i$-nél nagyobb monokromatikus kék (i=1), illetve piros (i=2) teljes gráfot. Ez az egyszerű bizonyítás némileg rosszabb eredményt ad, mint a Frankl-Wilson eredmény [18], azonban Babai, Snevily és Wilson [7] egy tételét felhasználva sikerült úgy módosítanunk, hogy ugyanazt a nagyságrendet adja, mint a legjobb ismert alsó korlát.


next up previous contents
Next: Bibliography Up: Eredményeink Previous: Megszorított metszetű halmazrendszerekre vonatkozó
Vince Grolmusz
1999-11-08