Többszörösen metsz halmazrendszerek

Többszörösen metsz® halmazrendszerek Katona Zsolt Eötvös Loránd Tudományegyetem E-mail:

[email protected] Kivonat

Jelölje [n] az {1, 2, ..., n} halmazt, 2[n] pedig [n] összes részhalmazát. Vegyünk egy F ⊂ 2[n] halmazrendszert. |F| maximumát keressük, ha bármely r részhalmaz metszete legalább s elem¶, és bármely ` különböz® halmaz metszete legfeljebb t elem¶, a paraméterek különféle vásztása mellett. Az r = 2, s = t = 1 esetben, tehát amikor bármely két halmaz metszete nemüres, de bármely ` különböz® halmaz metszete legfeljebb egy elem¶, megmutatjuk, hogy |F| ≤ (` − 1)n és ez aszimptotikusan a legjobb korlát. Egy masik fontos specialis eset, amikor r = `, s = t, azaz, amikor bármely ` különböz® halmaz   metszete pontosan t elem¶. Itt belátjuk, hogy |F| ≤ 2` (n − t) + 1 ha n elég nagy. Ez esetben az optimális család triviális, tehát azt is vizsgáljuk, hogy mi az optimum, ha kizárjuk a triviális konstrukciót, amikor az összes halmaz tartalmaz egy adott t-elem¶ halmazt. Az általános esetet csak azon feltétel mellett sikerült megoldani, amikor t ≥ 2s ≥ 2, r, ` ≥ 2, fennáll, természetesen
t+`−s n−snem
tartalmazza a fent tárgyalt Pt−s ez n−s eseteket. Ekkor |F| ≤ i=0 + i t+2−s t+1−s + ` − 2 és ez aszimptotikusan legjobb korlát, ha a paraméterek rögzïtettek és n → ∞. A cikk a szerz® idegen nyelven megjelen® 3 cikkének (egyik Füredi Zoltánnal közös) összefoglalása.

1

1.

Bevezetés

Jelölje [n] az {1, 2, . . . , n} halmazt, 2[n] az [n] összes részhalmazának családját, míg
[n] jelölje a k elem¶ részhalmazok családját. Erd®s, Ko és Rado [9] egyszer¶ tétele k szerint |F| maximuma 2n−1 ha az F ⊆ 2[n] család bármely két halmazának nemüres metszete van. Egy ilyen F -et

metsz®

halmazrendszernek hívunk. Valóban,

egy halmaz és komplementere közül csak az egyik szerepelhet, tehát az összesnek legfeljebb a fele, vagyis 2n /2 = 2n−1 . Ennyi halmazt tartalmazó metsz® rendszert,

M-et pedig úgy kapunk, ha veszünk egy rögzített elemet, például az 1-et tartalmazó összes halmazt. Ekkor M-et triviálisan

metsz®nek

hívjuk, hiszen az összes halmaz

metszete, ∩M 6= ∅. Azonban, ha n páratlan, akkor ugyanekkora metsz® rendszer az, -elem¶ halmazból áll, hiszen amelyik az összes, legalább n+1 2       n n n + n+3 + . . . + = 2n−1 . n+1 n 2 2 Ha n páros, akkor az összes legalább venni az 1 elemet tartalmazó összes

n + 1-elem¶ halmaz 2 n -elem¶ halmazt is. 2

családjához még hozzá kell

Tegyük a fenti konstrukciókat geometriai analógiával egy kissé szemléletesebbé. Egy F ⊂ 2[n] halmazhoz rendeljük hozzá az un.

karakterisztikus vektorát,

ami-

ben az i-edik koordináta 1 vagy 0 aszerint, hogy i eleme-e F -nek vagy sem. Akkor egy

F -nek n-hosszú 0,1 sorozatok (vektorok) felelnek meg. Az egyszer¶ség kedvéért ezt is jelölhetjük F -fel. Két ilyen sorozat távolsága a különböz® bitek száma. A halmazok nyelvén pedig a szimmetrikus dierencia mérete. Ebben a térben egy a középpontú, r sugarú B(a, ≤ r) gömb azon 0,1 sorozatokból áll, amelyek a-tól legfeljebb r távolságra vannak. Ha a gömb középpontja a = (1, 1, . . . , 1), akkor a B(a, ≤ r) gömböt jelöljük

B(n, ≥ n − r)-rel, ahol ≥ n − r arra utal, hogy legalább n − r-elem¶ halmazokról van szó. Ezek alapján a második konstrukció páratlan n esetén a B(n, ≥

n+1 ) 2

gömb. A

fenti feladatra vonatkozó els® konstrukciónak megfelel® vektorok azok, amiknek els® koordinátájuk 1, a többi pedig tetsz®leges. 0,1 vektorok egy olyan halmazát, amelyeknek néhány koordinátája rögzített, a többi pedig tetsz®leges, 2

hengernek

nevezzük,

de a megfelel® halmazrendszert ugyancsak. A fenti els® konstrukció tehát egy henger. A második konstrukció páros n esetén szintén egy gömb és egy henger kombinációja,
hiszen a B(n, ≥ n2 ) gömbhöz hozzávesszük egy hengernek és [n] n -nek a metszetét. 2

A fenti tételt Katona Gyula a következ®képpen terjesztette ki [22]. Ha egy F halmazrendszer s-metsz®, azaz bármely két halmaz metszete legalább s-elem¶, akkor páros n + s esetén |F| ≤ |B(n, ≥ 21 (n + s))|, ahol B(n, ≥x) egy gömb,

Hamming

azaz a legalább x méret¶ halmazok összesége, míg páratlan n + s mellett

|F| ≤ 2|B(n − 1, ≥ 21 (n + s − 1))|, és az optimális rendszer egy henger és egy gömb kombinációja. Ez sokszor el®fordul a metsz® halmazrendszerek elméletében, különösen uniform rendszerek esetén (amikor minden halmaz azonos méret¶), lásd Ahlswede és Khachatrian [1] megoldása az Erd®sFrankl sejtésre. Jegyezzük meg, hogy míg s = 1 esetén mind egy henger, mind egy gömb(szer¶) konstrukció optimális (s®t, sok más optimális is van), s ≥ 2 esetén csak a gömb(szer¶) (az egyetlen) optimális. Általánosan azt mondjuk, hogy F rendelkezik az I(r, ≥s) tulajdonsággal (vagy

r-szeresen

legalább

s-metsz®) ha

|F1 ∩ F2 ∩ . . . ∩ Fr | ≥ s bármely különböz® F1 , F2 , . . . , Fr ∈ F mellett,

(1)

Jelölje f (n; I(r, ≥s)) az n elemen lehet® legnagyobb r-szeresen legalább s-metsz® halmazrendszer méretét.

Ha vesszük az összes részhalmazt, amely tartalmaz s

rögzített elemet (ez is egy henger), ez kielégíti a feltételt, tehát következik, hogy

f (n; I(r, ≥s)) ≥ 2n−s minden n ≥ s ≥ 0-ra. A terület egyik legszebb eredménye Frankl tétele [11], mely szerint f (n; I(r, ≥s)) = 2n−s akkor és csak akkor, ha n < r +s vagy s ≤ 2r −r −1 kivéve az (r, s) = (3, 4) esetet. Egy kiváló összefoglaló cikk Frankltól való [12]. Természetesen merül fel az is, hogy a metszetek felülr®l korlátosak legyenek. Gronau egy kisebb eredménye szerint [19], ha bármely két halmaz metszete ≤ t akkor |F| arra a halmazcsaládra maximális, amely az összes legfeljebb t+1-elem¶ halmazból áll. Ez ismét egy gömb, aminek középpontja a (0, . . . , 0) és sugara t + 1. De azonnal megváltozik a helyzet, ha például bármely három halmaz metszete lehet legfeljebb t = 1. 3

Ekkor, mint az könnyen látható, a legnagyobb halmazcsalád az összes legfeljebb kételem¶ halmazon kívül még hármasoknak egy olyan családjából áll, amelyek minden kételem¶ halmazt pontosan egyszer tartalmaznak, ha a hármasoknak ilyen családja létezik. Itt tehát a kett® sugarú gömbön kívül hármasoknak egy olyan családja van, ami se nem gömb, se nem henger. Az ilyen tipusú rendszereket deniáljuk a következ®kben. Azt mondjuk, hogy F I(`, ≤t) tulajdonságú (vagy `-szeresen metsz®

legfeljebb

t-

), ha

|F1 ∩ F2 ∩ . . . ∩ F` | ≤ t bármely különböz® F1 , F2 , . . . , F` ∈ F halmazra,

(2)

Jelölje f (n; I(`, ≤t)) a legnagyobb ilyen halmazrendszer méretét n elemen. Egy k méret¶ részhalmazokból álló I(`, ≤t) tulajdonságú családot (n, k, t + 1, ≤` − 1) kolásnak

pa-

nevezünk és a maximális méretét jelöljük P (n, k, t + 1, ≤` − 1)-vel. Utóbbi

jelölést az magyarázza, hogy feltételünket úgy is fogalmazhatjuk, hogy a családban lév® k -elem¶ halmazok közül minden t + 1-est legfeljebb ` − 1 tartalmazhat. Általánosabban, egy F ⊆ 2[n] család (n, k + , j, ≤λ)

pakolás,

ha |F | ≥ k igaz minden F ∈ F

halmazára és minden j -elem¶ X ⊆ [n] halmazra teljesül, hogy X -et F -nek legfeljebb

λ tagja tartalmazza, azaz minden j -elem¶ halmaz legfeljebb λ-szer van lefedve. Itt is P (n, k + , j, ≤λ) jelöli a maximális méretet. Az alábbi els® egyenl®tlenség triviális, a második egyszer¶ kett®s leszámlálással adódik.

P (n, k, j, ≤λ) ≤ P (n, k , j, ≤λ) ≤ λ Ha itt egyenl®ség van egy F ⊆

λ = 1 esetén pedig

n j
. k j




+

[n] k




(3)

családra, akkor azt Sλ (n, k, j) blokkrendszernek,

Steiner rendszernek

hívjuk. Pakolásokról egy részletesebb

átakintés [4, 5]-ben található . Ilyen rendszerek létezése és konstruálása általában nagyon nehéz, most egy közis-

4

mert eredményt ismertetünk, a j = k − 1 esetet.   λ n−k n · ≤ P (n, k, k − 1, ≤λ) k n k−1

  λ n ≤ P (n, k , k − 1, ≤λ) ≤ . k k−1 +

(4)

A fels® korlát következik (3)-ból. Az alsó korláthoz konstruálunk egy
P F -et. Minden x ∈ [n] elemre tekintsük az Fx := {F ∈ [n] : f ∈F f ≡ x (mod n)} k

Bizonyítás:

halmazt. Nyilvánvaló, hogy Fx és Fy diszjunkt, ha x 6= y . Rögzítsünk egy k −1-elem¶

Y ⊂ [n] halmazt Könny¶ belátni, hogy Fx -nek legfeljebb egy tagja tartalmazza Y -t,
tehát Fx egy (n, k, k − 1, ≤ 1) pakolás, így F1 ∪ F2 ∪ · · · ∪ Fn a [n] család felbontása k (n, k, k − 1, ≤ 1) pakolásokra. Deniáljuk F -et, mint λ darab legnagyobb Fx unióját.

n Ekkor |F| ≥ nλ nk = λk n−k . n k−1 Ha a metszetekre egyszerre tesszük fel a fels® és alsó korlátokat, akkor a legegyszer¶bb eset, ha az alsó és fels® korlátok egyenl®ek, és azonos metszetekre vonatkoznak. Egy halmazrendszert `-szeresen

t-metsz®nek nevezünk, ha |F1 ∩ . . . ∩ F` | = t teljesül F bármely különböz® F1 , . . . , F` részhalmazaira. Jelölje pontosan

f (n, `, t) := f (n; I(`, ≤t), I(`, ≥t)) az ilyen halmazrendszerek maximális méretét n elemen. A legegyszer¶bb ilyen probléma a kétszeresen pontosan 1-metsz® halmazrendszerek esete, Erd®s és De Bruijn nevezetes eredményükben [6] belátták, hogy f (n, 2, 1) ≤ n és f (n, 2, 1) = n, ha

n = q 2 + q + 1, ahol q egy primszám hatványa. Általánosabban, t ≥ 2 esetére, Fisher egyenl®tlenségként ismert, hogy f (n, 2, t) ≤ n. Ugyan az egyenl®tlenséget el®ször Majumdar [25] bizonyította, de érdemes megemlíteni, hogy R.C. Bose egy egyszer¶bb bizonyítást talált és ez volt az els® eset, hogy valaki lineáris algebrai módszereket alkalmazott [3] egy kombinatorikai problémára. Jelen cikkben összefoglaljuk a szerz® (részben Füredi Zoltánnal közös) eredményeit, amelyek arra az esetre vonatkoznak, amikor a metszetek méretére egyszerre teszünk fel különböz® alsó és fels® becsléseket. Az eredmények idegen nyelven részben már megjelentek, részben megjelenés alatt vannak. 5

2.

Eredmények

E fejezetben felsoroljuk a kés®bbiekben bizonyítandó új eredményeket. Tekintsük az ` ≥ 3 esetet. Füredi Zoltán egy tételéb®l [15] könnyen bizonyítható, hogy az extremális családok ez esetben triviálisan metsz®k. Ebb®l már egyszer¶en következik, hogy 1. Tétel.

[23] Legyen ` ≥ 3 és n ≥

`(`+t) , ekkor `−2

f (n, `, t) =

` 2

 (n − t) + 1

.

Sok esetben az optimális családok nem triviálisan metsz®k, például az Erd®s-De Bruijn tétel esetében, a véges projektív sík egyike az optimális konstrukcióknak. Ez vezet a maximális nem triviálisan `-szeresen pontos t-metsz® rendszerek vizsgálatához Legyen g(n, `, t) =max|F|, ahol F `-szeresen pontosan t-metsz® és | ∩ F| < t. Természetesen g(n, `, t) ≤ f (n, `, t). Az el®bb említett példa miatt [6] g(n, 2, 1) =

n. A következ® tételekben a t = 1 esetben adott alsó és az általánosan adott aszimptotikus fels® korlátok ` = 3 esetén egybe esnek. 2. Tétel.

[23] g(n, 3, 1) = n2/3 (1 + o(1)).

Az általános esetben azonban különböz®ek. 3. Tétel.

[23] Ha l ≥ 2, akkor

1 1/` n (1 + o(1)) ≤ g(n, `, t) ≤ n(t+1)/(`+t−1) (1 + o(1)). t A fels® becslésb®l természetesen szintén következik, hogy az 1. tételben az optimális családok triviálisan metsz®k. A fenti 3 tételt a 3. fejezetben bizonyítjuk. Térjünk át arra az esetre, ha a fels® és alsó korlátok nem ugyanazon metszetekre vonatkoznak. Andrew Szilard zikus vette fel a problémát, hogy legfeljebb hány halmaz létezik n elemen, ha bármely kett® metszete nem üres, viszont bármely három 6

metszete üres. Ez könnyen megválaszolható, viszont az általanos eset a fedések elméletére vezethet® vissza, ahol kevés esetben megoldott a probléma. Ebb®l vet®dik fel a kérdés, hogy, mennyi f (n; I(2, ≥ 1), I(` ≤ 1), azaz legfeljebb hány halmaz lehet egy metsz® halmazrendszerben, amelyben bármely ` ≥ 2 halmaz metszete legfeljebb 1. A következ® tétellel a 4. fejezetben foglalkozunk. 4. Tétel.

[24] Legyen ` ≥ 2, ekkkor

f (n; I(2, ≥ 1), I(` ≤ 1) = (` − 1)n + o(n). Természetesen rátérünk az általános problémára is, azaz legfeljebb mekkora lehet egy halmazrendszer, ha bármely r halmaz metszete legalább s és bármely l metszete legfeljebb t. A problémát Füredi Zoltánnal közös cikkünben [16] aszimptotikusan megoldjuk a

t ≥ 2s esetre. Pontosabban, visszavezetjük a (3)-ban felmerült pakolási függvényre. Mint látható, az el®z® tételek speciális esetei az általános problémának, de az általános megoldás rájuk nem vonatkozik tehát volt értelme külön foglalkozni velük. A következ® tételt és a következményét együtt bizonyítjuk a 5. fejezetben. 5. Tétel.

r≥3

[16]

Legyen

t ≥ 2s ≥ 2, r ≥ 2, ` ≥ 2

és

n > n0 := n0 (r, s, `, t).

Ekkor

esetén

f (n; I(r, ≥s), I(`, ≤t)) = f (n − s; I(`, ≤t − s)). Ha pedig

r = 2,

akkor

f (n; I(2, ≥s), I(`, ≤t)) ≤ f (n − s; I(`, ≤t − s)) + ` − 2, és itt egyenl®ség áll, ha (3)-ban is egyenl®ség áll pakolásokra és

s ≥ ` − 1.

A tétellel együtt bizonyítjuk a következ®t.

7

(n − s, t + 2 − s, t + 1 − s, ≤ ` − 2)-

6. Következmény. A tétel aszimptotikusan a következ® formulát adja





t-metsz®

rendszerek

`−2 f (n; I(r, ≥s), I(`, ≤t)) = (1 + o(1)) 1 + t+2−s

`-szeresen

3.

pontosan

 n . t+1−s

Az 1. tétel bizonyításával kezdjük. Bizonyítás:

7. Tétel.

t-metsz®

Füredi [15]-beli tételének speciális esete a következ®.

[15] Legyen ` ≥ 3, t ≥ 1 és F legyen `-szeresen nem triviálisan, pontosan

halmazrendszer

n

elemen. Ekkor

|F| ≤ n + ` − 2.

Ezt itt nem bizonyítjuk, de ennél er®sebb a 3. tétel, amit majd a fejezet további részében bizonyítunk.

  El®ször azt bizonyítjuk, hogy |F| ≤ 2l (n − t) + 1, azaz meg fogunk adni `  ` (n − t) + 1 darab halmazt úgy, hogy | ∩ F| = t és mivel n ≥ `−2 (2 + t) esetén 2  ` (n − t) + 1 > n + ` − 2, így Füredi fenti tétele alapján csak a triviálisan metsz® 2 esettel kell foglalkoznunk. Tegyük fel, hogy ∩F = {n, n − 1, ..., n − t + 1}. Deniáljuk az F 0 = {F \{n, n −

1, ..., n − t + 1}|F ∈ F} családot, ekkor nyilván |F| = |F 0 |. Minden F 0 ∈ F 0 halmaz minden eleméhez rendeljünk egy

1 |F 0 |

nagyságú súlyt, kivéve az üres halmazt. Mivel

{1, 2, . . . n−t} minden eleme legfeljebb `−1 halmazban van benne, így minden elemen legfeljebb ` − 1 darab súly van. A két legnagyobb nem lehet mindkett® 1, hiszen a halmazok különböz®ek, így nem eshet egybe két egyelem¶ halmaz. A második legnagyobb súly tehát legfeljebb 21 , tehát az összes súly összege egy elemen legfeljebb

1+

`−2 2

=

` 2

. Összegezve az összes elemen a súlyokat az egyrészt legfeljebb (n − t) 2` ,

másrészt egyenl® |F 0 |-fel |F 0 | − 1-gyel (az üres halmaztól függ®en), mert a súlyok összege halmazonként 1 . Tehát

` |F| = |F 0 | ≤ (n − t) + 1. 2 8

(5)

  Ha n ≥ `+t tudunk konstruálni egy F halmazrendszert, amelyre |F| = 2` (n − t) +1.   Elég egy F 0 -et mutatni, amelyre |F 0 | = 2` (n − t) + 1 az {1, 2, . . . , n − t} alaphalmazon. Páros ` esetén legyen F 0 a ∅ ∪ {1} ∪ {2} ∪ . . . ∪ {n − t} ∪ F10 ∪ F20 ∪ . . . ∪ F 0`−2 2

rendszer, ahol Fi0 = {1, i + 1} ∪ {2, i + 2} ∪ . . . ∪ {n − t, n − t + i} (az elemeket értsük

(mod n − t)). Páratlan l esetén pedig legyen F 0 a ∅ ∪ {1} ∪ {2} ∪ . . . ∪ {n − t} ∪ F10 ∪        n−t  F20 ∪ . . . ∪ F 0 `−2 ∪ {1, n−t + 1} ∪ {2, n−t + 2} ∪ . . . ∪ { n−t , 2 2 } rendszer. 2 2 2 b 2 c A 2. és a 3. tételt egyszerre bizonyítjuk. El®ször a fels® korlátokat bizonyítjuk, közösen a két tételét, indukcióval `-re. Bizonyítás:

Megmutatjuk, hogy |F| ≤ n(t+1)/(`+t−1) (1+o(1)), ha F egy `-szeresen

pontosan t-metsz® halmazrendszer (` ≥ 2) és | ∩ F| < t. Az els® eset, ` = 2 Fisher egyenl®tlensége. Az indukciós lépés bizonyítása el®tt megjegyezzük, hogy a fels® becslés igaz és a bizonyítás m¶ködik akkor is, ha megengedünk többszörös halmazokat, azaz a halmazok nem feltétlenül különböz®ek F -ben. A többszörös halmazok kérdésére részletesebben is kitérünk a 6. fejezetben. Tegyük fel, hogy ` ≥ 3 és a becslés igaz ` − 1-re. Tekintsünk egy nem triviálisan

`-szeresen ponotsan t-metsz® F családot. Jelöljük F legkisebb halmazát X -szel és legyen |X| = k . Vegyük az X ∩ F metszeteket minden F ∈ F halmazra. Ezek egy olyan rendszert alkotnak, melyben X nem feltétlenül különböz® részhalmazai találhatók. Látható, hogy a rendszer nem triviálisan `-szeresen ponotsan t-metsz® (| ∩F ∈F X ∩ F | < t). Az indukció miatt ez azt jelenti, hogy

|F| ≤ k (t+1)/(`+t−2) (1 + o(1)).

(6)

Tehát kész vagyunk a bizonyítással, ha k ≤ n(`+t−2)/(`+t−1) , így feltehetjük, hogy
k > n(`+t−2)/(`+t−1) . Miel®tt folytatnánk terjesszük ki az xt jelölést nem egész x
ha x ≥ ` − 1 és f (x) = 0 egyébként. ekre. Legyen x` = f (x) = x(x−1)···(x−`+1) `! Látható, hogy ez a függvény monoton n® és konvex, tehát alkalmazhatjuk a Jensen
egyenl®tlenséget. Egy A ∈ [n] t-esre jelölje dA a |{F ∈ F|A ⊂ F }| mennyiséget, azaz t

F -beli A-t tartalmazó részhalmazok számát. Az `-szeresen ponotsan t-metsz® feltétel azt adja, hogy minden ` halmazhoz F -ben van egy A t-es, amely az ® metszetük. Egy 9

adott A

dA `




féleképpen lehet ` F -beli halmaz metszete, ha dA ≥ `. Tehát P
P !
dA A dA |F | [n] A∈ n ` ) ( t `
(t)
= ≥ n n ` t t

(7)

használva a Jensen egyenl®tlenséget is. Egy rögzített A-ra dA darab F ∈ F tartal
mazza A-t és egy rögzített F ∈ F halmaz |Ft | darab A-t tartalmaz , tehát folytatva (7)-ot, P

A dA n t

() `

!

P =

   (k) (|Ft |) |F| nt () (t)  . ≥ ` `

F ∈F n t

(8)

Feltehetjük, hogy |F| > n(t+1)/(`+t−1) , különben kész lennénk a bizonyítással. Mivel (k) k > n(`+t−2)/(`+t−1) , így |F| nt végtelenhez tart (n → ∞). Összegezve (7)-ot és (8)-et, (t)   !`

!` (kt) k k |F| n 1 1 − ε 1 (t)  ≥
|F|` ≥  |F| nt
− ` + 1 ≥ |F| nt
(9) n `! `! `! ` t t t bármely ε > 0-ra, ha n elég nagy. Tehát  `−1  ` n k (1 + o(1)) ≥ , t t

(10)

amib®l következik k ≤ (1 + o(1))n(`−1)/` ≤ (1 + o(1))n(`+t−2)/(`+t−1) , tehát (6) alapján

|F| ≤ (1 + o(1))nt+1/(`+t−1) . Most következik a 2. és 3. tételhez szükséges alsó becslések bizonyítása. Bizonyítás:

Konstrukciót adunk, véges projektív terek segítségével. P G(N, q) jelöli az N dimenziós q rend¶ véges projektív teret, ami q N +q N −1 +...+1 hipersíkból és ugyanennyi pontból áll. A hipersíkokat mint halmazokat tekintve a pontok alkotta alaphalmazon, bármely N halmaznak nemüres a metszete, nevezetesen egy K -dimenziós altér,

K < N − 1. 10

El®ször belátjuk, hogy g(3, 1, n) ≥ n2/3 (1 + o(1)), befejezve a 2. tétel bizonyítását. Megadunk egy F családot, amely [n]-nek n2/3 (1+o(1)) darab részhalazból áll, melyek

3-szorosan pontosan 1-metsz®k és ∩F = ∅. Tekintsük P G(3, q)-at, olyan q -val, hogy q 3 + q 2 + q + 1 = n legyen (ha van ilyen q prímhatvány). [3] és [28] alapján egy ovális

maximális mérete q 2 + 1, azaz legfeljebb ennyi pont adható meg úgy, hogy

bármely egyenesen legfeljebb kett® legyen. Vegyünk q 2 + 1 ilyen pontot. A duális síkjaikból (ezekb®l is q 2 + 1 van) álljon F . Ezek között nincs három, amely egy közös egyenest tartalmaz. Tehát 3 ilyen sík metszete egy pont, így F 3-szorosan pontosan

1-metsz®, méghozzá nem triviálisan. Azt kapjuk, hogy g(3, 1, n) ≥ n2/3 (1 + o(1)), mert az alaphalmaz q 3 + q 2 + q + 1 pontból áll. Ha nincs olyan q prímhatvány, melyre q 2 + q + 1 = n, akkor vegyük a legnagyobb m ≤ n úgy, hogy q 2 + q + 1 = m és q prímhatvány. Ez elegend®, hiszen tudjuk, hogy van prím n és (1 − ε)n között minden

ε > 0-ra, ha n elég nagy. A 3. tétel, azaz g(l, 1, n) ≥ n1/l (1 + o(1)) bizonyításához l ≥ 4-re, általánosítjuk az el®bbi konstrukciót. Minél több pontot keresünk P G(l, q)-ban (q l + ... + q + 1 = n) úgy, hogy legfeljebb l−1 van minden l−2-dimenziós (2-codimenziós) altérben. Sajnos √ nem ismert pontosan a maximális számuk l ≥ 4-re, de tudjuk, hogy van q + 2 q ilyen √ pont ([8] and [2]). Vegyünk q + 2 q ilyen pontot, ezek duális hipersíkjai alkotják majd F -et, amely l-szeresen pontosan 1-metsz® lesz, mint az el®z® konstrukcióban, így g(l, 1, n) ≥ n1/l (1 + o(1)). Vegül g(l, t, n) ≥ (1/t)n1/l (1 + o(1)) adódik, ha az alaphalmaz minden elemét t másikra cseréljük.

1. Megjegyzés. Ha létezik q 2 (1+o(1)) pont (ez a létez® fels® becslés) az el®bbi térben

úgy, hogy legfeljebb

l−1

g(l, 1, n) = n2/l (1 + o(1))

van minden

l − 2-dimenziós

altérben, akkor ebb®l következik

a fenti konstrukcióval.

A véges projektív terekben található fenti típusú halmazokkal foglalkozik a [20] összefoglaló cikk és a következ® változata [21]. 11

4.

Metsz®, de

`-szeresen

legfeljebb

1-metsz®

rends-

zerek

Rátérünk a 4. tétel bizonyítására. El®ször a fels® becsléssel foglalkozunk. A [24]-ben található eredeti bizonyítás helyett álljon itt Füredi Zoltán bizonyítása, mely nem csak aszimptotikus eredményt ad, nevezetesen azt bizonyítjuk, hogy (11)

f (n; I(2, ≥ 1), I(` ≤ 1) ≤ (` − 1)n.

A következ® lemma Motzkin [26] nevéhez f¶zödik, az ® eredményének könny¶ általánosítása. Eredetileg ® a c = 1 esetet bizonyította, ennek felhasználásával látjuk be minden c > 0-ra. 1. Lemma.

valós szám.

Legyen

G = G(A, B; E)

Tegyük fel, hogy

A-ban

páros gráf, melynek van éle és legyen

nincs olyan csúcs, ami szomszédos

csúcsával és, hogy minden nem összekötött csúcspárra, azaz minden

(a, b) 6∈ E

esetén

Bizonyítás:

deg(a) ≤ c deg(b).

Ekkor

B

c>0 összes

a ∈ A, b ∈ B ,

|A|c ≥ |B|.

Legyenek p és q pozitív egészek úgy, hogy p/q ≥ c teljesüljön. Belát-

juk, hogy (p/q)|A| ≥ |B|, és mivel (p/q) − c tetsz®legesen kicsi lehet, így ebb®l már következik c|A| ≥ |B|. Legyen G0 egy páros gráf, melynek csúcsai A0 ∪ B 0 úgy, hogy A0 A-nak p darab másolata, míg B 0 B -nek q darab másolata. Az éleket úgy adjuk meg, hogyha a0 ∈ A0 másolata az a ∈ A csúcsnak és b0 ∈ B 0 másolata a b ∈ B csúcsnak, akkor a0 -t akkor és csak akkor kössük össze b0 -vel G0 -ben, ha a össze van kötve b-vel G-ben. Ekkor

(a0 , b0 ) ∈ / E 0 esetén, 0



degG0 (a ) = q degG (a) ≤ q

 p degG (b) = p degG (b) = degG0 (b0 ). q

Tehát az eredeti Motzkin lemma (c = 1 eset) feltételei teljesülnek G0 -re, így |A0 | ≥

|B 0 |. Tehát pq |A| ≥ |B| is következik. Most rátérhetünk közvetlenül (11) bizonyítására. 12

Bizonyítás:

Legyen F egy metsz® halmazrendszer, melyben semely ` halmaz nem

tartalmaz két közös elemet. Deniáljuk a G(A, B; E) páros gráfot a következ®képpen. Legyen A := [n], B := F és x ∈ [n] legyen összekötve az F ∈ F csúccsal, ha x ∈ F . Ha a gráfnak nincs éle, akkor F = ∅ minden F ∈ F halmazra, így |F| ≤ 1. Ha van egy a ∈ A csúcs, amely szomszédos B összes csúcsával, akkor a benne van F minden halmazában. Azonban F -nek legfeljebb ` − 1 halmaza tartalmaz egy elempárt [n]-b®l, azaz

|F[x, y]| ≤ ` − 1,

(12)

ahol F[x, y] := {X ∈ F : x, y ∈ X}. Ezt az egyenl®tlenséget használva az (a, y) párokra azt kapjuk, hogy minden y 6= a elem F -nek legfeljebb ` − 1 halmazában van benne. Tehát |F| ≤ 1 + (` − 1)(n − 1) ≤ (` − 1)n. Megmutatjuk, hogy minden más esetben a 1. lemma feltételei teljesülnek c = ` − 1 mellett (ami pozitív, mert ` ≥ 2). Legyen x ∈ [n] = A és F ∈ F = B nem szomszédos csúcspár G-ben, azaz x ∈ / F. Tekintsük az F[x] := {X ∈ F : x ∈ X} rendszert, erre teljesül |F[x]| = degG (x). Mivel F metsz®, ezért F[x] minden tagja metszi F -et, így F[x] = ∪y∈F F[x, y]. Ekkor (12) miatt |F[x]| ≤ (` − 1)|F |, tehát degG (x) ≤ (` − 1) degG (F ). Az 1. lemmát alkalmazva G-re kapjuk, hogy (` − 1)n = (` − 1)|A| ≥ |B| = |F|.

A 4. tétel bizonyításából még hátra van az alsó becslés. Bizonyítás:

Konstrukciót adunk F -re véges projektív síkok segítségével úgy, hogy

|F| = (` − 1)n + o(n). Csima és Füredi bizonyította [10], hogy egy véges desargue-i q -rend¶ projektív sík pontjai színezhet®k q +1 színnel úgy, hogy nincs 3 egyszín¶ pont egy egyenesen. A dualitást használva ez azt jelenti, hogy az egyenesek is színezhet®k ennyi színnel úgy, hogy nincs 3 egyszín¶, amely átmegy egy ponton. Tekintsük P G(2, q)-t, ahol q a legnagyobb prímhatvány úgy, hogy q 2 + l(q + 1) ≤

n. Legyenek a1 , . . . , aq2 +q+1 a pontok és L1 , . . . , Lq2 +q+1 az egyenesek . Színezzük az egyeneseket a fenti módon, az Li egyenes színe legyen c(i) .

Vegyünk

(` − 2)(q + 1) extra pontot az egyenesek színeib®l (` − 2-t minden színb®l). Jelöljük 13

®ket e1,1 , . . . , eq+1,1 , e2,2 , . . . , eq+1,`−2 -vel (ei,j a j -edik extra pont az i-edik színnel). Legyen Fi,j = Li ∪ {ec(i),j } (1 ≤ i ≤ q 2 + q + 1,1 ≤ j ≤ ` − 2) és Fi,`−1 = Li . A halmazrendszer alaphalmaza legyen {a1 , . . . , aq2 +q+1 , e1,1 , . . . , eq+1,`−2 }, míg a halmazokat adjuk meg a következ®képpen F = {Fi,j : 1 ≤ i ≤ q 2 + q + 1, 1 ≤ j ≤

` − 1}. Könnyen látható, hogy a fent megadott halmazok különböz®ek és |F| = (` − 1)(q 2 + q + 1). Bármely két halmaz metszi egymást, mert Li ⊆ Fi,j , La ⊆ Fa,b , és Li ∩ La 6= ∅. Kell még, hogy ` különböz® részhalmaz metszete legfeljebb egyelem¶. Az halmazok közül biztos van kett®, amelynek különbözik az els® indexe (Fa,b , Fe,f , a 6= e). Ha b 6= f , akkor Fa,b ∩ Fe,f = La ∩ Le és a mértete pontosan egy. Ha b = f , akkor vegyünk egy harmadikat: Fg,h . Ha h 6= b, akkor g 6= a vagy g 6= e (feltehet®, hogy g 6= a), tehát Fa,b ∩ Fg,h = La ∩ Lg és a mérete pontosan egy. Végül, ha

b = f = h, akkor c(a) = c(e) = c(g) esetén Fa,b ∩ Fe,f ∩ Fg,h = {ec(a),b }, hiszen La ∩ Le ∩ Lg = ∅. Abban az esetben pedig, ha c(a), c(e), c(g) nem mind egyformák, akkor Fa,b ∩ Fe,f ∩ Fg,h = La ∩ Le ∩ Lg és a mérete egy. A konstrukcióban n ≥ q 2 + `(q + 1) és |F| = (` − 1)(q 2 + q + 1). Tehát Másrészt

|F | n

≤ l − 1.

q2 + q + 1 |F| ≥ (` − 1) n ((1 + ε)q)2 + l((1 + ε)q + 1)

minden ε > 0-ra, ha n elég nagy. Tehát

|F | n

tart ` − 1-hez, ha n → ∞. Ezzel a tételt

bebizonyítottuk

5.

Általános eset

Az általános tétel bizonyítása el®tt lássuk be, a 6. következményt a 5. tételb®l. Ehhez (4)-el együtt elég az alábbi állítás, hiszen (4) az alábbi pakolások méretére ad becslést. 2. Állítás.

Legyen

` ≥ 2, t ≥ 1. Ekkor X n  f (n; I(`, ≤t)) = + P (n, (t + 2)+ , t + 1, ≤` − 2). i 0≤i≤t+1 14

Az összes legfeljebb t + 1 méret¶ részhalmaz és a fenti pakolás együtt

Bizonyítás:

megfelel. Csak azt kell bizonyítani, hogy ennél jobb nincs. Legyen F ⊆ 2[n] , ami

I(`, ≤t) tulajdonságú. Feltehetjük, hogy [n] minden legfeljebb t elem¶ részhalmazát tartalmazza F , mert ha |X| ≤ t, akkor F ∪ {X} is I(`, ≤t) tulajdonságú. Ugyancsak
[n] feltehetjük, hogy minden (t + 1) elem¶ részhalmaz F -ben van, ugyanis ha X ∈ t+1 ,

X ∈ / F és |F[X]| ≤ ` − 2, akkor F ∪ {X} ismét I(`, ≤t) tulajdonságú. Másrészt |F[X]| = `−1 > 0 esetén vegyünk egy F ∈ F[X] halmazt és cseréljük X -re. A kapott F \ {F } ∪ {X} szintén I(`, ≤t) tulajdonságú. Ezt az eljárást addig ismételhetjük,
[n] míg t+1 összes eleme F -ben van.
S Ekkor az F \ 0≤i≤t+1 [n] család nyilván egy (n; (t + 2)+ , t + 1, ≤` − 2)-pakolás. i

Jegyezzük meg, hogy a fenti bizonyításból következik az alábbi, kicsit er®sebb állítás is. Ha az F család I(`, ≤t) tulajdonságú [n]-en és minden F ∈ F legalább t + 1 elem¶, akkor

 |F| ≤

 n + P (n, (t + 2)+ , t + 1, ≤` − 2). t+1

(13)

Most a 5. tétel bizonyítása következik. Bizonyítás:

Legyen

Σ :=

t+1−s X  i=0

 n−s + P (n − s, (t + 2 − s)+ , t + 1 − s, ≤` − 2). i

Könnyen adható olyan Σ részhalmazból álló család, amely kielégíti a metszési feltételeket és amelyben az összes részhalmaz tartalmazza [s] elemet, azaz triviálisan metsz®.

Legyen ugyanis P 0 egy P (n − s, (t + 2 − s)+ , t + 1 − s, ≤` − 2)

méret¶ pakolás az [n] \ [s] alaphalmazon . Legyen P = {P ∪ [s] : P ∈ P 0 } és

F0 = {F ⊂ [n] : |F | ≤ t + 1; [s] ⊂ F } ∪ P . Ekkor f (n; I(r, ≥s), I(`, ≤t)) ≥ |F0 | = Σ. 15

(14)

r = 2 esetén nagyobb családot is meg tudunk adni. Tegyük fel, hogy van egy optimális (n−s, (t+2−s)+ , t+1−s, ≤ `−2)-pakolás, amely csak (t+2−s) elem¶ halmazokból áll, vagyis (3)-ban egyenl®ség áll ezekre az értékekre. Ezután távolítsuk el [s]-et F0 ból és vegyünk hozzá min{s, ` − 1} darab [n] \ {i}, 1 ≤ i ≤ s alakú halmazt. Látható, hogy a kapott F1 rendszer kétszeresen legalább s-metsz® és I(`, ≤t) tulajdonságú. Legyen F egy tetsz®leges I(r, ≥s), I(`, ≤t) tulajdnoságokkal rendelkez® család. Meg fogjuk mutatni, hogy r ≥ 3 esetén |F| ≤ Σ és r = 2-re |F| ≤ Σ + ` − 2 r = 2-re. El®ször tekintsük az | ∩ F | ≥ s esetet. Ez azt jelenti, hogy F részhalmazaiban van s közös elem, például [s] ⊂ F minden F ∈ F esetén. Tekintsük az F 0 = {F \ [s] :

F ∈ F} rendszert. F 0 -ben bármely ` halmaz metszete legfeljebb t (t − s) elem¶, azaz F 0 I(`, ≤t − s) tulajdonságú. Tehát bármely t + 1 − s elem F 0 -nek legfeljebb ` − 1 tagjában van benne. Tehát |F| = |F 0 | ≤ Σ az 2. állítás miatt. Ezek után feltehetjük, hogy | ∩ F| < s. Deniáljuk az F(i) := {F ∈ F : |F | = i} és F(≥j) = F(j) ∪ F(j + 1) ∪ ... rendszereket, ezekkel, F = F(1) ∪ F(2) ∪ . . .. Triviálisan F(i) = ∅, ha i < s. Az F(i) család i-uniform az [n] alaphalmazon és

I(2, ≥s) tulajdnoságú, tehát az Erd®s-Ko-Rado tétel [9] miatt   n−s |F(i)| ≤ ha n > n(i, s). i−s

(15)

Ezt a becslést használjuk, ha s ≤ i ≤ t. (14) és (4) alapján feltehetjük, hogy |F| ≥ Tehát (15)-b®l következik, hogy  |F(≥t + 1)| ≥ 1 +

Pt−s

i=0

n−s i

`−2 n−t−2 t+2−s n−s




+ 1+



n−s t+1−s

Most egy fels® becslést adunk a nagy halmazok számára. 3. Lemma.

Ha

F ∈ F halmazra, akkor
  |A| n−s s (` − 1). |F(≥k)| ≤ k−s
t+1−s t+1−s

|A ∩ F | ≥ s

minden

16

`−2 n−t−2 t+2−s n−s






n−s t+1−s




.

(16)

Legyen A = {X ∈

: |A ∩ X| ≥ s}, ekkor nyilván |A| ≤ . Bármely t + 1 elem F -nek legfeljebb ` − 1 tagjában van benne és minden

k−s k−s F ∈ F(≥k) legalább t+1−s tagját tartalmazza A-nak. Tehát |F(≥k)| t+1−s ≤

Bizonyítás:

|A| s




n−s t+1−s

[n] t+1







|A|(` − 1). Mivel t ≥ 2s ≥ 2, ezért a

k s




/

k−s t+1−s




tört tetsz®legesen kicsi minden elég nagy

k ≥ k0 esetén. Például, ha k > k0 (t, s) := 4s2 + 6t2 , akkor
k 2t 1 s
< < . k−s k 3t t+1−s Vágjuk F(≥t + 1)-et ketté, a G ∪ F(≥k0 ) családokra, ahol G := F(t + 1) ∪ F(t +

2) ∪ . . . ∪ F(k0 − 1). Fels® becslést adunk F(≥k0 ) méretére. Ha nem üres, akkor válasszunk egy minimális méret¶ F0 ∈ F(≥k0 ) halmazt, azaz |F | ≥ |F0 | minden más F ∈ F(≥k0 ) halmazra. Jelöljük F0 méretét f0 -al. F0 megfelel A-nak a 3. lemmában, azt kapjuk, hogy

 f0 s
f0 −s t t+1−s


|F(≥k0 )| = |F(≥f0 )| ≤

   n−s n−s `−1 . (` − 1) < 3t t + 1 − s +1−s

Összehasonlítva ezt (16)-al, látható, hogy minden n > k0 számra    `−2 n−t−2 `−1 n−s |G| = |F(≥t + 1)| − |F(≥f0 )| ≥ 1 + − t+2−s n−s 3t t+1−s   `−1 n−s ≥ . (17) 3t t + 1 − s 4. Állítás.

Bizonyítás:

| ∩ G| = s. Ha | ∩ G| ≤ s − 1, akkor van egy A ⊂ [n], |A| < 3k0 halmaz, amelyre

|A ∩ G| ≥ s + 1 minden G ∈ G esetén. S®t vagy van egy A ∈ G , amely legalább s + 1 elemben metszi G összes többi elemét, vagy találhatunk G1 , G2 ∈ G halmazokat úgy, hogy |G1 ∩ G2 | = s. Ekkor van egy G3 ∈ G , amely nem tartalmazza G1 ∩ G2 -t. Tehát

|G1 ∩ G2 ∩ G3 | ≤ s − 1, ekkor pedig G1 ∪ G2 ∪ G3 megfelel® A-nak. Ilyen A halmaz létezése | ∩ G| ≥ s + 1 esetén nyilvánvaló. 17

A I(`, ≤t) tulajdonság miatt        |A| n−s−1 3k0 t + 1 − s n−s |G| ≤ (` − 1) ≤ (` − 1). s+1 t−s s+1 n−s t+1−s Ez pedig ellentmond (17)-nak, ha n > n0 (k, s). Tehát feltehetjük, hogy [s] ⊂ ∩G . Legyen S := {F ∈ F(≥t + 1) : [s] ⊂ F } és

H = {F ∈ F(≥t+1) : [s] 6⊂ F }. Ekkor F(≥t+1) = S ∪H. Az S 0 := {F \[s] : F ∈ S} család I(`, ≤t − s) tulajdonságú n − s elemen. Ezen kívül S 0 minden tagja legalább

t + 1 − s elem¶. Tehát a 2. állítás, pontosabban (13) miatt   n−s 0 |S| = |S | ≤ + P (n − s, (t + 2 − s)+ , (t + 1 − s), ≤` − 2). t+1−s

(18)

Ha H = ∅, akkor S = F(≥t + 1), (18) és (15) miatt |F| ≤ Σ, tehát kész vagyunk. Mostantól feltehetjük, hogy H = 6 ∅. Legyen H1 a legkisebb halmaz H-ban és a mérete |H1 | = h. Hogy megbecsüljük |S|-et, tekintsük a C := {C ⊂ [n] : C ⊃ [s], |C| = t + 1} családot. Mivel F(t + 1) ⊂ G ⊂ S , így F(t + 1) ⊂ C . Ezen kívül egyrészt S(≥t + 2) minden tagja C -nek legalább t + 2 − s tagját tartalmazza. Másrészt, C minden tagja

F -nek legfeljebb ` − 1 tagjában van benne. Azt kapjuk tehát, hogy   n−s (t + 2 − s) (|S| − |F(t + 1)|) + |F(t + 1)| ≤ (` − 1)|C| = (` − 1) . t+1−s Átrendezve,

 |S| ≤

`−2 1+ t+2−s



 n−s t+1−s (|C| − |F(t + 1)|) . − t+1−s t+2−s

Mivel F ∈ F(t+1), így (F \[s]) nem lehet benne [n]\H1 -ben, ezért |C|−|F(t+1)| ≥
. A (t − s + 1)/(t − s + 2) tört legalább 2/3, tehát

n−s−h t+1−s

 |S| ≤

`−2 1+ t+2−s



   n−s 2 n−h−s − . t+1−s 3 t+1−s 18

(19)

A 3. lemma segítségével adunk fels® becslést |H|-ra, tetsz®leges A ∈ G halmazzal. Mivel |A| ≤ k0 és minden H ∈ H halmazra |H| ≥ h, így
    k0 n−s 2t n−s s (` − 1) < (` − 1). |H| ≤ h−s
t + 1 − s h t + 1 − s t+1−s

(20)

A (19) és (20) fels® korlátokat összeadva és összehasonlítva a (16) alsó korláttal kapjuk, hogy    `−2 n−t−2 n−s 1+ ≤ |F(≥t + 1)| = |S| + |H| t+2−s n−s t+1−s        `−2 n−s 2 n−h−s 2t n−s ≤ 1+ − + (` − 1). t+2−s t+1−s 3 t+1−s h t+1−s Átrendezve,

      2 n−h−s 2t n−s 1 n−s ≤ + . 3(` − 1) t + 1 − s h t+1−s n−s t+1−s

(21)

Itt újradeniálhatjuk k0 (t, s)-t, mint k0 (t, s, `) úgy, hogy elég nagy legyen t, s,`-t®l függ®en, de n is elég nagy legyen az új k0 -hoz képest, azaz n > n0 (t, s, `). Ekkor (21) miatt h >

`−1 (n `

+ t), tehát a I(`, ≤t) tulajdonság miatt |H| ≤ ` − 1.

Ismét, (18) és (15)-b®l következik, hogy |F| ≤ Σ+|H| ≤ Σ+(`−1). Mivel |F| ≥ Σ,
(15) azt adja, hogy |F(s + 1)| ≥ n−s − |H| ≥ (n − s) − (` − 1) > k0 > s + 2. Tudjuk, 1 hogy F(s+1) tagjai páronként s elemben metszik egymást, így vagy |∪F(s+1)| ≤ s+2
és akkor |F(s + 1)| ≤ s+2 , vagy | ∩ F(s + 1)| = s. Legyen S0 az az s elem, melyet s+1 minden F ∈ F(s + 1) halmaz tartalmaz. Ha egy F részhalmaz F(s + 1)-nek minden tagját legalább s elemben metszi és |F | < |F(s + 1)|, akkor S0 ⊂ F . Tehát ∩G ⊃ S0 és S0 is benne van F(i) minden tagjában, ha s ≤ i ≤ t. Ekkor a 4. állítás miattt

S0 = [s]. Azt is kapjuk, hogy |H ∩ [s]| = s − 1 and H ⊃ (∪F(s + 1) \ [s]) teljesül minden H ∈ H esetén. Tekintsünk egy F1 6= F2 ∈ F(s+1) és egy H1 ∈ H halmazt. Ekkor |F1 ∩F2 ∩H1 | ≤

s − 1. Ez ellentmondás r ≥ 3-ra tehát |F| ≤ Σ ebben az esetben. 19

Végül, ha r = 2, akkor H 6= ∅ miatt az F rendszer nem tartalmazhatja az [s] halmazt, tehát |F(s)| = 0 és így |F \ H| ≤ f (n − s, I(`, ≤ t − s)) − 1. Tehát

|F| ≤ Σ − 1 + (` − 1) és ezzel a tételt bebizonyítottuk.

6.

Többszörös halmazok

Általában egy halmazrendszer halmazai különböz®ek, de néha érdekes lehet a probléma akkor is, ha megengedünk többszörös halmazokat is. Ebben az esetben F néhány nem feltétlenül különböz® halmazból áll. Jelöljük f 0 (n, `, t)-vel egy `-szeresen pontosan t-metsz® rendszer maximális méretét, ha megengedünk többszörös halmazokat. Hasonlóan, minden eddig deniált maximum vessz®s megfelel®je jelölje azt az esetet, amikor megengedünk többszörös halmazokat. Az Erd®s-de Bruijn tétel jól ismert általánosításai Ray-Chaudhuri-Wilson [30] és Frankl-Wilson [14] tételei a korlátozott metszetméret¶ halmazrendszerekr®l. Ezt folytatva Grolmusz és Sudakov [18] adott fels® becslést adott `-metszetméret¶ halmazrendszerekre. Ennek egy speciális esete az els® problémánkra azaz a 1. tételben szerepl® f (n, `, t) párjára, Jelöljük f 0 (n, `, t)-re a (` − 1)(n + 1) fels® becslést adja. További érdekes eredmények találhatók még Grolmusz [17]-ban. A 1. tétel bizonyítás többszörös halmazokra is azt adja, hogy |F| akkor maximális, ha |∩F| = 6 t. Ekkor könnyen számolható a maximum, ami kicsit jobb, mint Grolmusz és Sudakov eredménye, azaz 8. Tétel. Legyen

`≥3

és

n ≥ t,

ekkor

f 0 (n, `, t) = (` − 1)(n − t) + 1. Áttérve a 4. fejezetre, megállapíthatjuk, hogy a 4. tétel megfelel®je is igaz. 9. Tétel.

f 0 (n; I(2, ≥1), I(`, ≤1)) = (` − 1)n 20

teljesül minden

n

és

`≥2

esetén.

Vehetjük ugyanis a [6]-ban és [26]-ben szerepl® konstrukciókat ` − 1 példányban, például egy egyelem¶ halmazt és az azt az elemet tartalmazó kételem¶ halmazokat. Az általános problémánál is felmerül, hogy mennyiben változik a probléma, ha többszörös halmazokat is megengedünk.

Ha a többszörös halmazok között van

s ≤ |F | ≤ t méret¶ is, akkor ezekb®l bármennyit vehetnénk, a kérdés értelmetlen. Deniáljuk tehát most az f 0 (n; I(r, ≥s), I(`, ≤t)) mennyiséget, mint max m, ahol F egy család [n] elemen esetleges többszörös halmazokkal, amely rendelkezik az I(r, ≥s), I(`, ≤t) tulajdonságokkal és minden tagja legalább t + 1 elem¶. Ekkor az alábbi tétel érvényes. 10. Tétel.

Legyen

t ≥ 2s ≥ 2, r ≥ 2, ` ≥ 2

és

n > n0 := n0 (r, s, `, t).

Ekkor

r≥3

esetén

  n−s f (n; I(r, ≥s), I(`, ≤t)) = f (n − s; I(`, ≤t − s)) = (` − 1) t+1−s 0

Ha pedig

0

r = 2,

akkor

f 0 (n; I(2, ≥s), I(`, ≤t)) = f 0 (n − s; I(`, ≤t − s)) + ` − 1   n−s = (` − 1) + ` − 1. t+1−s A fels® korlát bizonyítása szinte ugyanaz, mint a 5. tételben. Annyival egyszer¶bb a dolgunk, hogy az alsó korlátot adó pakolási probléma itt triviális, az optimális rendszer csak (t + 1) elem¶ halmazokból áll (mindegyikb®l ` − 1 példány) r ≥ 3-ra és még néhány (n − 1) elem¶b®l r = 2-re.

7.

Összegzés

Az irodalomban nem volt ismeretlen az olyan halmazrendszerek maximális méretének vizsgálata, ahol bizonyos metszetekre alsó és fels® korlátok adottak. Például [13]-ben szerepel a sejtés, hogy (a korábbi jelöléseinket használva) X n − 1 . f (n; I(2, ≥1), I(2, ≤ k)) = i 0≤i≤k

21

Az összes legfeljebb (k + 1) elem¶ halmazt véve, amely tartalmaz egy adott elemet látjuk, hogy ez a legjobb lehetséges. n > 100k 2 / log(k +1)-re ezt Frankl és Füredi [13] bizonyította az úgynevezett ∆-rendszer módszerrel, n ≤ 2k + 2-re és 6(k + 1) ≤ n ≤

(1/5)(k + 1)2 -re pedig Pyber [27] a permutációs módszer zseniális alkalmazásával. Végül Ramanan [29] bizonyította a sejtést minden n-re lineáris algebrai módszerekkel. Ebben a cikkben összegeztük az általános problémára adott Füredi Zoltánnal közös megoldást [16] és olyan speciális eseteket [24], [23], melyeket nem fed az általános megoldás, de érdekesek abból a szempontból is, hogy más a struktúrájuk, mint az általános esetben. Ezen kívül részlegesen megoldjuk az Erd®s, De Brujin tétel általánosításával felmerül® problémát, amikor ` halmaz metszete adott méret¶, de kizárjuk a triviális kongurációt. Az általános megoldás csak a paraméterekre vonatkozó bizonyos feltételek mellett érvényes, melyek közül a leger®sebb, hogy t ≥ 2s. Maradtak tehet megoldatlan problémák, melyek közül talán a legszer¶bbek, azok amikor s = t. Például hány részhalmaz létezhet legfeljebb, ha bármely két részhalmaz metszete legalább t ≥ 2 elem¶, viszont bármely ` ≥ 3 részhalmaz metszete legfeljebb t elem¶. A korábbi jelöléseket használva ez

f (n; I(2, ≥ t), I(`, ≤ t)) A másik érdekes eset, amikor 3 ≤ t = s + 1. A legegszer¶bb probléma tehát az, hogy hány részhalmaz létezhet legfeljebb, ha bármely két részhalmaz metszete legalább két elem¶, viszont bármely háromé legfeljebb három elem¶, azaz

f (n; I(2, ≥ 2), I(3, ≤ 3)) meghatározása.

Hivatkozások

[1]

R. Ahlswede és L. H. Khachatrian,

A pushing-pulling method: new proofs of intersection theorems, Combinatorica 19 (1999), 115.

22

[2]

M.A. de Boer,

Almost MDS codes, Des. Codes Cryptogr. 9 (1996), 143-155.

Mathematical theory of the symmetrical factorial design, Sankkyã 8 (1947) 107-166.
[4] A. E. Brouwer, Packing and covering of kt -sets, in: Packing and Covering in Combinatorics, (edited by A. Schrijver), Mathematical Centre Tracts 106, Matematisch Centrum, Amsterdam, 1979. pp. 8997.

[3]

R. C. Bose,

[5]

A. E. Brouwer,

[6]

N. G. de Bruijn és P. Erd®s,

Block Designs, Chapter 14 in: Handbook of Combinatorics, R. Graham, M. Grötschel and L. Lovász Eds., Elsevier, Amsterdam, 1995. On a combinatorial problem, Nederl. Akad. Wetensch., Proc. 51 (1948), 12771279. = Indagationes Math. 10 (1948), 421423.

[7] J. Csima és Z. Füredi, Colouring Finite Incidence Structures, Graphs and Combinatorics 2 (1986) 339-346. [8]

S.M. Dodunekov és I.N. Landjev,

[9]

P. Erd®s, Chao Ko, és R. Rado,

On near-MDS codes, J. Geom. 54 (1995), 30-43

Intersection theorems for systems of nite sets, Quart. J. Math. Oxford Ser. (2) 12 (1961), 313320. Coloring Finite Incidence Structures, Graphs and Combina-

[10]

J. Csima és Z. Füredi,

[11]

P. Frankl,

[12]

P. Frankl,

[13]

P. Frankl és Z. Füredi,

[14]

P. Frankl és R. M. Wilson,

[15]

Z. Füredi,

[16]

Z. Füredi és Zs. Katona,

torics 2 (1986) 339-346.

Multiply-intersecting families, J. Combin. Theory, Ser. B 53 (1991), 195

234.

Extremal set systems, in: Handbook of Combinatorics, Vol. 1, 2, pp. 12931329, R. Graham, M. Grötschel and L. Lovász Eds., Elsevier, Amsterdam, 1995. Families of nite sets with missing intersections, in: Finite and innite sets, Vol. I, II (Eger, 1981), pp. 305318, Colloq. Math. Soc. János Bolyai, 37, North-Holland, Amsterdam, 1984. Intersection theorems with geometric consequences, Combinatorica, 1(4) (1981), 357-368 On a problem of Deza and Frankl, Ars Combinatortia, 13 (1982), 221-222

Multiply intersecting families of sets, Journal of Combinatorial Theory, Series A, Vol 106/2 (2004), 315-326

23

[17]

V. Grolmusz, Set-systems with restricted multiple intersections and explicit Ramsey hypergraphs, Electronic J. of Combinatorics, 9 (2002), R8.

[18]

k -wise Set-intersections and k -wise Hammingdistances, J. Combin. Theory Ser. A 99 (2002), no. 1, 180190.

[19]

Hans-Dietrich O.F. Gronau,

[20]

J. W. P Hirschfeld és L. Storme,

V.

Grolmusz

és

15 (1980), 29-30.

B.

Sudakov,

An extremal set problem, Studia Sci. Math. Hungar,

The packing problem in statistics, coding theory and nite projective spaces. R. C. Bose Memorial Conference (Fort Collins, CO, 1995) J. Statist. Plann. Inference 72 (1998), no. 1-2, 355380.

[21]

The packing problem in statistics, coding theory and nite projective spaces: update 2001 http://cage.rug.ac.be/ls/

[22]

Gy. Katona,

[23]

Zs. Katona,

[24]

Zs. Katona,

[25]

K.N. Majumdar,

[26] [27]

J. W. P Hirschfeld és L. Storme,

Intersection theorems for systems of nite sets, Acta Math. Acad. Sci. Hungar. 15 (1964), 329337. 3-wise exactly 1-intersecting families of sets, Graphs and Combinatorics

21 (2005), 7176.

Intersecting families of sets, no ` containing two common elements, Discrete Math. 226 (2001), 233241. On some theorems in combinatorics relating to incomplete block designs, Ann. Math. Stat. 24 (1953), 377-389. Th. Motzkin, The lines and planes connecting the points of a nite set, Trans. Amer. Math. Soc. 70 (1951), 451464.

L. Pyber,

268.

An extension of a Frankl-Füredi theorem, Discrete Math. 52 (1984), 253

Some remarks concerning curves of the second degree in a nite plane, Ann. Acad. Sci. Fenn. Ser. A. 134 (1952)

[28]

B. Qvist,

[29]

G. V. Ramanan,

[30]

D. K. Ray-Chaudhuri és R. M. Wilson,

Proof of a conjecture of Frankl and Füredi, J. Combin. Theory, Ser. A 79 (1997), 5367. 735-744

24

On t-designs, Osaka J. Math. 12 (1975),