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

Megszorított metszetű halmazrendszerekre
vonatkozó eredmények

A [25] cikkben (folyóirat-változat [21]) erős negatív választ adtunk Frankl és Wilson [18] kérdésére, valamint Babai és Frankl [4] fent említett sejtésére. Megadtuk egy olyan szuper-polinomiális méretű uniform halmazrendszer explicit konstrukcióját, amely az r>1 különböző prímosztóval rendelkező m modulusra kielégíti a Frankl-Wilson tétel feltételeit. Megjegyezzük, hogy a Frankl-Wilson tétel felső becslése konstans modulusra az alaphalmaz méretében (azaz n-ben) polinomiális korlátot ad, és Frankl [17] ellenpéldája is polinomiális méretű halmazrendszert ad meg, az általunk adott konstrukció mérete pedig szuper-polinomiális. Pontosabban mutattunk egy olyan ${\cal H}$ uniform halmazrendszert, amely az n elemű alaphalmazon kielégíti az alábbi feltételeket:

(a)
$\vert{\cal H}\vert\geq \exp\bigg(c{(\log n)^r\over
(\log \log n)^{r-1}}\bigg)$,
(b)
$\forall H\in {\cal H}: \ \vert H\vert\equiv0\pmod{m}$,
(c)
$\forall G, H\in {\cal H}, G\ne H: \ \vert G\cap H\vert\not\equiv0\pmod{m}$.
A bizonyításunk Barrington, Beigel és Rudich [8] egy polinom-konstrukciójára, és egy olyan új módszerre épül, amely többváltozós polinomokból halmazrendszereket állít elő. Megjegyezzük, hogy úgy is meg tudunk adni szuper-polinomiális méretű ${\cal H}$-t, ha a páros metszetek mérete csak három maradékosztályt foglal el modulo m.



Vince Grolmusz
1999-11-08