next up previous contents
Next: Eredményeink Up: Motiváció és irodalmi áttekintés Previous: Explicit Ramsey-gráf konstrukciók

Megszorított metszetű halmazrendszerek

Nem vállalkozunk itt az extremális halmazrendszerek idevágó számos igen fontos tételének még vázlatos áttekintésére sem, sok fontos eredmény megtalálható a [4] monográfiában, illetve a [20] kézikönyvben. Itt csak munkánkhoz legszorosabban kapcsolódó eredményeket említjük meg.

A Ray-Chaudhuri--Wilson tétel [46] következő általánosítását bizonyította be Frankl és Wilson a már említett [18] cikkben: Ha ${\cal F}$ egy n elemű alaphalmaz feletti olyan uniform halmazrendszer, amelyre teljesül, hogy minden $F\in{\cal F}$-re $\vert F\vert=k\equiv\mu_0\pmod{p}$, és bármely két különböző $F,G\in{\cal F}$-re teljesül, hogy $\vert F\cap G\vert\equiv\mu_i\pmod{p}$, valamely $i=1,2,\ldots,s$-re, ahol p prím, $k+s\leq n$, és $\mu_0, \mu_1,\ldots,\mu_s$ különböző mod p maradékosztályok, akkor

\begin{displaymath}\vert{\cal F}\vert\leq{n\choose s}.\end{displaymath}

Ez a tétel került felhasználásra Frankl és Wilson előző részben említett explicit Ramsey-gráf konstrukciójában is.

Frankl és Wilson kérdezte [18]-ben, hogy a fenti felső becslés érvényben marad-e akkor, ha a p prím-modulust egy m nem-prím modulusra cseréljük ki. Ha s=m-1, és m prímhatvány, akkor maga Frankl és Wilson [18] mutatta meg, hogy a válasz igen. Az m=6 esetben Frankl [17] nemleges választ adott, megmutatta, hogy s=3-ra van $\vert{\cal F}\vert\approx cn^4$-t kielégítő halmazrendszer. Az s=m-1 eset továbbra is teljesen nyitott maradt m=6-ra, valamint nem-prímhatvány összetett számokra. Babai és Frankl sejtették ([4], Section 7.3, Conjecture C(r)), hogy a Frankl-Wilson tétel felső becslése érvényben marad s=m-1 esetén.


next up previous contents
Next: Eredményeink Up: Motiváció és irodalmi áttekintés Previous: Explicit Ramsey-gráf konstrukciók
Vince Grolmusz
1999-11-08