SZAKDOLGOZAT

Kombinatorikus problémák az adatbázisok elméletében

1998

Írta: Tichler Krisztián Témavezető: Katona Gyula

Tartalomjegyzék

1. Bevezetés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Alaptulajdonságok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3. Direkt szorzatok reprezentációja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4. s(L_{k}^{n}) nagyságrendje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

5. s(L_{k}^{n}) meghatározása k néhány értékére . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

6. Egy kulcsrendszer reprezentációja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Hivatkozási jegyzék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

1.Bevezetés

Egy adatbázis legegyszerűbb modellje egy mátrix. Egy-egy oszlopban azonos fajta adatok szerepelnek (például név, születés ideje, születés helye, stb.), míg a különböző sorokban a különböző egyének adatai. Egy bizonyos fajta adatokat (az irodalomban használatos elnevezéssel) attributumnak nevezünk, mely azonosítható a fenti mátrix egy oszlopával. Az attributumok halmazát Ω = {a_{1}, a_{2}, …, a_{n}}-nel fogjuk jelölni. A lehetséges értékek halmazát az i-edik oszlopban a_{i} értékkészletének nevezzük, és D(a_{i})-vel jelöljük. Így tehát egy egyén adatait (a mátrix egy sorát) tekinthetjük a D(a_{1}) × D(a_{2}) × … × D(a_{n}) direkt szorzat egy elemének (n-esének). Ezért az egész adatbázis (vagy mátrix) leírható az r ⊆ D(a_{1}) × D(a_{2}) × … × D(a_{n}) relációval, azaz az n-esek halmazával. Ennek a modellnek a neve relációs adatbázis modell.

Az adatok között fennállhatnak bizonyos logikai összefüggések. Például a születés dátuma meghatározza a kort (egy adott évben), vagy a vezetéknév és a keresztnév meghatározza a monogramot. Azt mondjuk, hogy egy attributum (funkcionálisan) függ attributumok egy halmazától, ha az azokban felvett értékek együttesen egyértelműen meghatározzák az ottani értéket. A funkcionális függőség fogalmát W.W. ARMSTRONG és E.F. CODD vezették be. Formálisan:

1.1 Definició [1],[5] Legyen A, B ⊆ Ω. Azt mondjuk, hogy B funkcionálisan függ A-tól, ha tetszőleges b ∈ B esetén nem létezik r-nek 2 sora (n-ese), melyek A oszlopaiban (attributumaiban) megegyeznek, de b-ben különböznek. Ennek jelölése: A → B.

A funkcionális függőségek nagyon hasznosnak bizonyultak. Valamennyi adatbázist működtető rendszer ezen a koncepción alapul. Tekintsük a következő példát. Tegyük fel, hogy Ω = {a_{1}, a_{2}, a_{3}, a_{4}} és a_{1} → a_{2} valamint a_{3} → a_{4}. Ha a teljes mátrixot tároljuk a számítógép memóriájában, akkor a legrosszabb esetben 4N_{1}N_{3} regiszterre van szükség, ahol N_{i} = |D(a_{i})| (i = 1, 3). Valóban, a_{1} és a_{3} egymástól függetlenül vehetnek fel értékeket, de ezek meghatározzák a_{2}-t és a_{4}-et. Így a különböző sorok száma legfeljebb N_{1}N_{3}. Azonban az adott funkcionális függőségek használatával számottevő memóriát takaríthatunk meg. Valóban, elegendő az a_{1} és a_{3} oszlopaiból álló mátrixot (2N_{1}N_{3} regiszter) valamint két kis mátrixot tárolni. Az egyik a_{1} és a_{2} értékeiből áll az első illetve második oszlopban. Az első oszlop tartalmazza a_{1} lehetséges értékeit, míg a második az a_{1} → a_{2} függőség által meghatározott értékeket. A másik kis mátrix a_{3}-ból és a_{4}-ből ugyanígy épül fel. A tárolt értékek száma legfeljebb 2N_{1}N_{3} + 2(N_{1} + N_{3}), ami általában szignifikánsan kisebb 4N_{1}N_{3}-nál.

A szakdolgozat célja megvizsgálni a fukcionális függőség tulajdonságait. Ennek során számos érdekes kombinatorikai probléma merül fel. A 2. fejezet megismerteti az olvasót a témakör fogalmaival és problémáival. A 3. fejezet direkt szorzatok, a 4. és 5. fejezet a gyakran vizsgált L_{k}^{n} lezáráscsalád minimális reprezentációjával foglalkozik. A 6. fejezet új eredménye egy új típusú kulcsrendszercsalád minimális reprezentációját vizsgálja.

2. Alaptulajdonságok

Ebben a fejezetben a legfontosabb definiciók és néhány egyszerűbb, de alapvető tétel kerül tárgyalásra. Legyen Ω = {a_{1}, a_{2}, …, a_{n}}.

2.1 Definició [17] Az Ω halmaz részhalmazaibol álló A ↪ B párok egy D rendszerét determinációnak nevezzük, ha Ω bármely A, B, C, D részhalmazára

A ↪ A,  (2.1)
A ↪ B, B ↪ C ⇒ A ↪ C,  (2.2)
A ⊆ C, D ⊆ B,A ↪ B ⇒ C ↪ D,  (2.3)
A ↪ B, C ↪ D ⇒ A ∪ B ↪ C ∪ D.  (2.4)

Könnyen látható, hogy egy r reláció (adatbázis) összes A → B funkcionális függőségei determinációt alkotnak Ω részhalmazain.

2.2 Definició [1] Egy r reláció összes funkcionális függőségét teljes családnak nevezzük.

2.3 Tétel [1] Az A ↪ B párok egy rendszere teljes család akkor és csak akkor ha determináció.

2.4 Definició Egy L halmazfüggvényt lezárási operációnak vagy röviden lezárásnak nevezünk Ω részhalmazain, ha minden A, B ⊆ Ω-ra

A ⊆ L(A),  (2.5)
A ⊆ B ⇒L(A) ⊆ L(B),  (2.6)
L(L(A)) = L(A).  (2.7)

2.5 Állítás [17] Egy adott Ω halmazon létezik bijekció a determinációk halmaza és a lezárások halmaza között.

Bizonyítás: Ha adott egy D determináció Ω-n, akkor definiáljuk az L(D) halmazfüggvényt: L(A) = {a| A ↪ a} minden A ⊆ Ω-ra. Könnyen látható hogy L(D) lezárás, valamint hogy D ⟶ L(D) injekció.

Fordítva, ha adott egy L lezárás, akkor D(L) álljon azon A ↪ B párokból, melyre B ⊆ L(A). Könnyen látható, hogy D(L) determináció, és most is L ⟶ D(L) injekció. Mivel Ω véges halmaz, ezért mindkét injekció valójában bijekció.

További bijekciók is megadhatók a determinációk halmazával (például a metszet-félhálókkal vagy a metszetmentes halmazcsaládokkal) [4],[9],[12],[17].

2.6 Definició K ⊆ Ω kulcs, ha K ↪ Ω; minimális kulcs, ha minimális a tartalmazásra, mint részbenrendezésre nézve a kulcsok között. A ⊆ Ω antikulcs, ha nem kulcs; maximális antikulcs, ha maximális a tartalmazásra, mint részbenrendezésre nézve az antikulcsok között.

Azaz egy r reláció esetén K kulcs, ha a K-beli értékek meghatároznak minden más értéket is.

Egy L lezárás (vagy D determináció, stb.) meghatározza a minimális kulcsok K = K(L) (vagy K = K(D)) családját. Ez nyilván egy nem-üres Sperner-rendszer (egy S halmazrendszer Sperner ha tartalmazásmentes, vagyis ha A, B ∈ S ⇒ A ⊈ B) Fordítva, ha adott egy K nem-üres Sperner-rendszer, akkor

L(A) = \{ \begin{matrix}A & ha nincs olyan K ∈ K, melyre K ⊆ A \\ Ω & ha van olyan K ∈ K, melyre K ⊆ A \end{matrix}  (2.8)

lezárás, és a minimális kulcsok halmaza éppen K.

2.7 Állítás [17] Bármely nem-üres K Sperner-rendszerhez létezik olyan r reláció, melyben a minimális kulcsok halmaza K.

Bizonyítás: Az állítás következik a 2.3 Tételből és a 2.5 Állításból valamint (2.8)-ból.

Természetesen K nem határozza meg L-et egyértelműen.

2.8 Definició A D_{k}^{n} determináció álljon azon A ↪ B párokból melyekre B ⊆ A ⊆ Ω, valamint azon A ↪ B párokból melyekre A, B ⊆ Ω és |A| ≥ k. Ennek megfelel az

L_{k}^{n} = L(D_{k}^{n}) = \{ \begin{matrix}A & ha |A| < k, \\ Ω & ha |A| ≥ k, \end{matrix} A ⊆ Ω  (2.9)

lezárás. K_{k}^{n} = K(L_{k}^{n}) = \binom{Ω}{k} pedig az Ω alaphalmaz k elemű részhalmazainak családja.

2.9 Tétel [6] A minimális kulcsok száma legfeljebb \binom{n}{⌊\frac{n}{2}⌋}, és ez éles.

Bizonyítás: Az egyenlőtlenség könnyen következik E. SPERNER tételéből [21], mely szerint minden S tartalmazásmentes halmazrendszerre |S| ≤ \binom{n}{⌊\frac{n}{2}⌋}. Most tekintsük D_{⌊n/2⌋}^{n}-et. A 2.3 Tétel szerint van olyan r reláció, melynek teljes családja D_{⌊n/2⌋}^{n}. Nyilvánvaló, hogy a minimális kulcsok halmaza ebben a relációban K_{⌊n/2⌋}^{n}, azaz Ω ⌊\frac{n}{2}⌋ elemű részhalmazai. Tehát az egyenlőtlenség nem javítható.

2.10 Lemma (YBLM-egyenlőtlenség, [22],[3],[19],[20]) Ha S Sperner-rendszer egy n elemű alaphalmazon és f_{i} az i elemű tagok száma, akkor

∑_{i=0}^{n} \frac{f_{i}}{\binom{n}{i}} ≤ 1.  (2.10)

2.11 Tétel [17] Tegyük fel, hogy az A → B funkcionális függőségekre |B − A| ≤ k, ahol k ≤ n/2. Ekkor a minimális kulcsok száma legfeljebb \binom{n}{k}.

Bizonyítás: A feltétel miatt a kulcsok mérete legalább n − k. Alkalmazzuk a 2.10 Lemmát, ahol a Sperner-rendszer a minimális kulcsok halmaza. Ekkor f_{0} = f_{1} = … = f_{n−k−1} = 0. Felhasználva, hogy

\binom{n}{i} ≤ \binom{n}{n − k} ha k ≤ n/2, n − k ≤ i ≤ n,

kapjuk (2.10)-ből, hogy

1 ≥ ∑_{i=n−k}^{n} \frac{f_{i}}{\binom{n}{i}} ≥ ∑_{i=n−k}^{n} \frac{f_{i}}{\binom{n}{n−k}} = \frac{1}{\binom{n}{n−k}} ∑_{i=n−k}^{n} f_{i} = \frac{|S|}{\binom{n}{n−k}},

amiből a tétel következik.

A fentiekből tudjuk, hogy bármely D determinációhoz, L lezáráshoz, vagy K minimális kulcsok rendszeréhez létezik olyan r reláció, hogy r éppen az adott D-t, L-t, illetve K-t generálja. Ekkor azt mondjuk, hogy r (vagy a neki megfelelő M mátrix) reprezentálja őket. Nem világos azonban, hogy mekkora a fentieket reprezentáló relációk közül |r| minimuma, más szóval hány sora van a fentieket generáló legkevesebb sorral rendelkező mátrixnak. Jelölje ezeket a minimumokat s(D), s(L), illetve s(K).

2.12 Tétel [6],[8] Egy adott Ω n-elemű alaphalmazon

\frac{1}{n^{2}} \binom{n}{⌊\frac{n}{2}⌋} < max_{K}\{s(K)| K ≠ ∅ Sperner Ω-n\} ≤ 1 + \binom{n}{⌊\frac{n}{2}⌋}.  (2.11)

Az első egyenlőtlenség bizonyítása nem konstruktív, mivel nem ismerjük a (közel) legrosszabb Sperner-rendszereket. Egy lehetséges jelölt K_{⌊n/2⌋}^{n}. Ez az egyik motivációja s(L_{k}^{n}) vizsgálatának. Ugyanis a következő lemma miatt ez ekvivalens s(K_{k}^{n}) vizsgálatával, mivel a két szám megegyezik.

2.13 Lemma [7] Legyen L az n-elemű Ω alaphalmaz egy tetszőleges lezárása. Ekkor

K(L) = K_{k}^{n} ⇔ L = L_{k}^{n}.  (2.12)

Bizonyítás: Nyilván K(L_{k}^{n}) = K_{k}^{n}. A másik irányhoz elég belátni, hogy L(A) = A, ha A ⊆ Ω, |A| < k, ugyanis ekkor L(A) = Ω, |A| ≥ k könnyen következik K(L) = K_{k}^{n} -ből és (2.6)-ból. Legyen tehát a ∈ L(A)\A. Ekkor létezik egy olyan B halmaz melyre |B| = k, B ⊇ A ∪ {a}. (2.5) miatt L(B\{a}) ⊇ B\{a}, míg (2.6) miatt L(B\{a}) ⊇ L(A) ∋ a. Ezért L(B\{a}) ⊇ B Most (2.6)-ból és (2.7)-ből L(B\{a}) = L(L(B\{a})) ⊇ L(B) = Ω. Így találtunk egy k-nál kisebb számosságú halmazt, aminek a lezártja Ω. Ez az ellentmondás mutatja (2.5) felhasználásával, hogy L(A) = A. Tehát L = L_{k}^{n}.

A következő lemma egyszerűsége ellenére meglepően erősnek bizonyult.

2.14 Lemma [10],[7]

\binom{s(L_{k}^{n})}{2} ≥ \binom{n}{k − 1} (0 ≤ k ≤ n).  (2.13)

Bizonyítás: Tegyük fel, hogy M reprezentálja L_{k}^{n}-et és legyen |A| = k − 1 Ω egy részhalmaza, továbbá b ∉ A. Ekkor L_{k}^{n} definíciója miatt A ↛ b, azaz létezik két olyan sor (i és j), hogy ezek megegyeznek A-n, de különbözik a b-beli értékük. Ha lenne Ω-nak egy másik (k − 1)-elemű B részhalmaza, hogy i és j megegyeznek B-n, akkor A ∪ B ↛ b állna, de mivel |A∪B| ≥ k, ezért L_{k}^{n} definiciója miatt ez lehetetlen. Így a különböző sorpárokhoz különböző oszlop-(k − 1)-eseket rendelhetünk.

Azonban lesz amikor az előző lemma nem elegendő. A következő lemma mátrixok egy egyszerű tulajdonságát mutatja be. Legyen M egy m × n-es mátrix és G(M) jelölje a következő gráfot: a gráf csúcsai feleljenek meg M sorainak, és két csúcs pontosan akkor legyen összekötve, ha azon oszlopok A halmaza, ahol a két sor megegyezik nem-üres. Az élet cimkézzük meg A-val.

2.15 Lemma [7] Legyen M egy mátrix és legyenek A_{1}, …, A_{r} a G(M) gráf egy körének cimkéi. Ekkor

( ⋂_{{i=1 \atop i≠j}}^{r}A_{i})\A_{j} = ∅ (1 ≤ j ≤ r).  (2.14)

Bizonyítás: Átindexelés után feltehető, hogy j = r. Indirekt tegyük fel, hogy az u-adik oszlop eleme minden A_{i}-nek (1 ≤ i < r), de nem eleme A_{r}-nek. Legyenek a kör pontjai k_{1}, …, k_{r} úgy, hogy a (k_{i}, k_{i+1}) él cimkéje legyen A_{i} (1 ≤ i < r) és (k_{r}, k_{1}) cimkéje A_{r}. u ∈ A_{1}-ből következik, hogy az u-adik oszlop k_{1}-edik és k_{2}-edik eleme megegyezik. Hasonlóan kapjuk, hogy az u-adik oszlop k_{2}-edik és a k_{3}-adik, …, a k_{r−1}-edik és a k_{r}-edik eleme megegyezik. Ezért így a k_{1}-edik és a k_{r}-edik elem megegyezik, tehát u ∈ A_{r}, ami ellentmond az indirekt feltevésünknek.

Ha adott a minimális kulcsok K halmaza, akkor jelölje K^{−1} a maximális antikulcsok halmazát.

2.16 Lemma [7] M reprezentálja a K Sperner-rendszert akkor és csak akkor, ha egyrészt bármely A ∈ K^{−1}-hez létezik M-nek két különböző sora, hogy ezekben A oszlopaiban ugyanaz az érték szerepel, másrészt ha bármely két olyan sor, ami megegyezik K ∈ K-n, megegyezik mindenütt.

Bizonyítás: Ha M reprezentálja K-t, akkor K = K(L_{M}). Ha K ∈ K, akkor L_{M}(K) = Ω, és a második feltétel nyilván teljesül. Hasonlóan, ha A ∈ K^{−1}, akkor L_{M}(K) ≠ Ω, és így a második feltétel is következik.

Fordítva, ha mindkét feltétel teljesül M-re és K-ra, akkor

(i) L_{M}(A) ≠ Ω minden A ∈ K^{−1}-re és (ii) L_{M}(K) = Ω minden K ∈ K-ra.

(ii) és (2.6) szerint L_{M}(C) = Ω ha C ⊇ K valamely K ∈ K-ra. Tegyük fel most, hogy C nem tartalmazza K semelyik tagját sem. Ekkor definició szerint létezik olyan A ∈ K^{−1}, hogy C ⊆ A. (i) és (2.6) miatt L_{M}(C) ≠ Ω. Tehát a minimális kulcsok halmaza éppen K.

2.17 Lemma [7]

\binom{s(K)}{2} ≥ |K^{−1}| ≥ s(K) − 1.  (2.15)

Bizonyítás: A második egyenlőtlenséget a következő egyszerű konstrukció mutatja: A nulladik sor álljon csupa 0-ból, míg az i-edik sor (1 ≤ i ≤ |K^{−1}|) 0-kból és i-kből. A nullák álljanak K^{−1} i-edik tagjának oszlopaiban.

A másik irányhoz legyen A ∈ K^{−1}, ekkor a 2.16 Lemma szerint van két különböző i, j sor, hogy ezek A-ban megegyeznek. Most legyen B K^{−1} egy másik eleme. Ha ehhez ugyanaz az (i, j) pár tartozna, akkor ezek a sorok megegyeznének A ∪ B-n. Következésképp L(A ∪ B) ≠ Ω és létezik C ∈ K^{−1}, hogy C ⊇ A ∪ B. K^{−1} definiciója miatt ez csak úgy lehetséges, ha C = A és C = B, ami ellentmond az A ≠ B feltételnek. Tehát K^{−1} különböző elemeihez különböző sorpárok rendelhetők, ami bizonyítja az első egyenlőtlenséget.

3. Direkt szorzatok reprezentációja

Keveset tudunk s(L)-ről az L_{k}^{n}-től különböző lezárásokra. Egy eredmény azonban ismert direkt szorzatok s-függvényére.

3.1 Definició Legyen Ω = Ω_{1} ∪Ω_{2} az Ω alaphalmaz egy particiója, és legyenek L_{1} és L_{2} két lezárás Ω_{1}-n illetve Ω_{2}-n. Ekkor az L_{1} × L_{2} direkt szorzat definiciója

(L_{1} × L_{2})(A) = L_{1}(A ∩ Ω_{1}) ∪ L_{2}(A ∩ Ω_{2}).  (3.1)

3.2 Tétel [7]

s(L_{1} × L_{2}) = s(L_{1}) + s(L_{2}) − 1.  (3.2)

Bizonyítás: Először egy konstrukcióval bizonyítjuk az

s(L_{1} × L_{2}) ≤ s(L_{1}) + s(L_{2}) − 1.  (3.3)

egyenlőtlenséget. Reprezentálják az s(L_{1}) × n_{1} -es M_{1} és az s(L_{2}) × n_{2} -es M_{2} mátrixok az L_{1} illetve L_{2} lezárásokat. Jelölje α az M_{1} mátrix utolsó sorát, míg β az M_{2} mátrix első sorát. Definiáljuk az (s(L_{1}) + s(L_{2}) − 1) × (n_{1} + n_{2})-es M mátrixot a következőképpen:

Ω_{1}  Ω_{2}

β

M_{1}  ⋮

β

α β

α

⋮  M_{2}

α

Megmutatjuk, hogy ez a mátrix reprezentálja L_{1} × L_{2}-t, azaz

a ∈ L_{M}(A) ⇔ a ∈ L_{1}(A ∩ Ω_{1}) ∪ L_{2}(A ∩ Ω_{2}).  (3.4)

A szimmetria miatt feltehetjük, hogy a ∈ Ω_{1}. Ekkor a (3.4) feltétel két implikációra bontható:

a ∈ L_{1}(A ∩ Ω_{1}) ⇒ ha M két sora megegyezik A-ban, akkor a-ban is, (3.5)
a ∉ L_{1}(A ∩ Ω_{1}) ⇒ M két sora megegyezik A-ban, de különbözik a-ban. (3.6)

(3.5) bizonyításához tegyük fel, hogy a ∈ L_{1}(A ∩ Ω_{1}), és válasszuk ki M két olyan sorát, melyek megegyeznek A-ban. Ha mindkettő α-val kezdődik, akkor természetesen megegyeznek a-ban. Ha legalább az egyik nem α-val kezdődik, akkor ezeknek a soroknak az első fele M_{1}-nek két különböző sora, így tehát ha megegyeznek A ∩ Ω_{1}-ben, akkor megegyeznek a-ban is.

(3.6) bizonyításához tegyük fel, hogy a ∉ L_{1}(A ∩ Ω_{1}). M_{1} tartalmaz két sort, melyek megegyeznek A ∩ Ω_{1}-ben, de különböznek a-ban. Ezek a sorok ugyanúgy folytatódnak, tehát megegyeznek A-ban.

Tehát M reprezentálja L_{1} × L_{2}-t, így (3.3)-t bebizonyítottuk.

Most két lemma segítségével bebizonyítjuk a

s(L_{1} × L_{2}) ≥ s(L_{1}) + s(L_{2}) − 1.  (3.7)

egyenlőtlenséget. Reprezentálja az M mátrix L_{1} × L_{2}-t és tegyük fel, hogy az első n_{1} oszlop felel meg L_{1} Ω_{1} alaphalmazának, míg a második n_{2} oszlop L_{2} Ω_{2} alaphalmazának. Azt szeretnénk bizonyítani, hogy M-nek legalább s(L_{1})+s(L_{1})−1 sora van. Jelölje az első n_{1} oszlop által meghatározott részmátrixot M_{1}, míg a maradékot M_{2}.

3.3 Lemma L_{M_{2}} = L_{2}.

Bizonyítás: Tegyük fel, hogy A ⊆ Ω_{2}, a ∈ Ω_{2} és a ∈ L_{2}(A). Ekkor a ∈ (L_{1} × L_{2})(A). Ha M két sora megegyezik A-ban, akkor M definiciója miatt a-ban is, és ez igaz marad akkor is, ha csak az M_{2} részmátrixot tekintjük. Azaz bebizonyítottuk, hogy a ∈ L_{M_{2}}(A). Fordítva, most tegyük fel, hogy A ⊆ Ω_{2}, a ∈ Ω_{2} és a ∉ L_{2}(A). Mivel így a ∉ (L_{1} ×L_{2})(A), ezért M-nek van két olyan sora, hogy ezek megegyeznek A-ban, de különböznek a-ban. Ezeknek a soroknak M_{2}-be eső része mutatja, hogy a ∉ L_{M_{2}}(A).

Analóg módon L_{M_{1}} = L_{1}. Azonban M_{1}-re egy valamivel erősebb állításra van szükség:

3.4 Lemma Tegyük fel, hogy az N mátrix sorai k osztályba sorolhatók úgy, hogy ha a ∉ L_{N}(A), akkor létezik egy osztályban két olyan sor, melyek megegyeznek A-ban, de különböznek a-ban. Ekkor

(N sorainak száma) ≥ s(L_{N}) + k − 1.  (3.8)

Bizonyítás: k-ra vonatkozó indukcióval bizonyítunk. k = 1-re (3.8) s(L_{N}) definiciója miatt igaz. Tegyük fel, hogy N már particionálva van k ≥ 2, a lemma feltételeit teljesítő osztályra, és hogy az állítás igaz kisebb értékekre.

L_{N} csak attól függ, hogy N mely elemei egyenlők, illetve melyek nem. Ezért feltehető, hogy a mátrix csak pozitív egész értékeket tartalmaz.

Töröljük N azon oszlopait, melyekben csak egyfajta érték áll, és jelöljük az új mátrixot N_{1}-nel. N sorainak particiója N_{1}-nek is egy “jó” particióját adja. Másfelől nyilván

s(L_{N_{1}}) = s(L_{N}).  (3.9)
Továbbá L_{N_{1}}(∅) = ∅.

Legyenek p_{1}, p_{2}, …, p_{k} N_{1} minden eleménél nagyobb prímszámok. Szorozzuk be az i-edik sorosztály minden elemét p_{i}-vel (1 ≤ i ≤ k). Jelölje az új mátrixot N_{2}. Könnyen látható, hogy

L_{N_{2}} = L_{N_{1}},  (3.10)

mivel L_{N_{1}}(∅) = ∅ és különböző sorosztályokban N_{2} nem tartalmaz egyforma elemeket.

Legyen γ = (γ_{1}, …, γ_{u}) illetve δ = (δ_{1}, …, δ_{u}) az N_{2} első illetve második osztályának egy-egy sora. Most töröljük a γ sort és cseréljünk ki minden γ_{i}-t δ_{i}-re az i-edik oszlopban (minden 1 ≤ i ≤ u -ra). Jelölje az új mátrixot N_{3}. Ennek eggyel kevesebb sora van, mint N_{2}-nek. Most bizonyítsuk be, hogy

L_{N_{3}} = L_{N_{2}}.  (3.11)

Tegyük fel először, hogy a ∈ L_{N_{2}}(A) és válasszuk ki N_{3} két sorát, μ_{3}-t és ν_{3}-t, melyek megegyeznek A-ban. A megfelelő sorokat N_{2}-ben jelölje μ_{2} illetve ν_{2}. Ha N_{2}- ben μ_{2} és ν_{2} azonos osztályban van, de nem az elsőben, akkor μ_{2} = μ_{3}, ν_{2} = ν_{3}. Ezért μ_{2} és ν_{2} megegyeznek A-ban és így a ∈ L_{N_{2}}(A) miatt a-ban is. Ugyanez áll μ_{3}-ra és ν_{3}-ra, tehát a ∈ L_{N_{3}}(A). Ha μ_{2} és ν_{2} egyaránt az első osztályban van, akkor μ_{3} csak annyiban különbözik μ_{2}-től, hogy γ_{i} helyett δ_{i} áll mindenütt. Ugyanez igaz ν_{2}-re és ν_{3}-ra. Következésképp μ_{2} és ν_{2} megegyezik A-ban, és így a-ban is. Kapjuk tehát, hogy μ_{3} és ν_{3} is megegyezik a-ban és így a ∈ L_{N_{3}}(A). Az utolsó esetben μ_{2} és ν_{2} különböző osztályban vannak. Mivel a feltevés szerint μ_{3} és ν_{3} megegyezik A-ban, ezért vagy A = ∅, vagy μ_{2} és ν_{2} az első és a második sorosztályból való. L_{N_{2}}(∅) = ∅ miatt az első esetet kizárhatjuk. Tehát μ_{2} ≠ γ az első osztályban van, míg ν_{2} a másodikban. Nyilván ν_{2} = ν_{3}. Mivel μ_{3} és ν_{3} megegyezik A-ban, ezért mindkettőben az i-edik helyen i ∈ A-ra δ_{i}-nek kell állnia. Ekkor ν_{2} = ν_{3} és δ megegyeznek A-ban, következésképp a-ban is. Jelölje a közös értéket itt δ_{a}. Ha μ_{3}-ban az i-edik helyen δ_{i} áll i ∈ A-ra, akkor μ_{2} ott γ_{i}-t tartalmaz. Tehát μ_{2} és γ megegyezik A-ban és így a-ban is. A közös értékük itt γ_{a}. Ebből azt kapjuk μ_{3}-nak is δ_{a} az értéke ebben az oszlopban. Ezért μ_{3} és ν_{3} megegyezik a-ban, és így a ∈ L_{N_{3}}(A).

Tegyük most fel, hogy a ∉ L_{N_{2}}(A). Ekkor van N_{2}-nek két sora, hogy ezek megegyeznek A-ban, de különböznek a-ban. Ha A ≠ ∅, akkor ez a két sor ugyanabban az osztályban van, következésképp a megfelelő sorok N_{3}-ban szintén megegyeznek Aban és különböznek a-ban (γ-nak δ felel meg). Tehát ebben az esetben a ∉ L_{N_{3}}(A). A = ∅, a ∈ L_{N_{3}}(∅) azt jelen tené, hogy van egy olyan oszlop, amiben ugyanazok az értékek szerepelnek. Ez k ≥ 3-ra lehetetlen. k = 2-re ez csak úgy lehetséges, ha N_{2} csak γ_{a}-t és δ_{a}-t tartalmaz az a-nak megfelelő oszlopban. Azonban ebben az esetben nem tudnánk találni két sort ugyanabban az osztályban, melyek teljesítik a lemma feltételét a ∉ L_{N_{2}}(∅)-ra. Ez az ellentmondás mutatja, hogy a ∉ L_{N_{3}}(A), és így (3.11) -t bebizonyítottuk.

Sőt N_{3}-ra teljesül a lemma feltétele (legalább) k−1 osztállyal. Így az indukciós feltevés alapján:

(N_{3} sorainak száma) ≥ s(L_{N_{3}}) + k − 2.

Ebből és (3.9)-(3.11)-ből kapjuk:

(N sorainak száma) ≥ s(L_{N}) + k − 1,

amivel a lemmát bebizonyítottuk.

Térjünk most vissza a tétel bizonyításához, pontosabban (3.7)-hez. Particionáljuk M_{1} sorait aszerint, hogy a folytatásuk M_{2}-ben megegyezik-e. Célunk a 3.4 Lemmát alkalmazni M_{1}-re. A 3.3 Lemma alapján L_{M_{1}} = L_{1}. Tegyük fel, hogy valamely A ⊆ Ω_{1}-re és a ∈ Ω_{1}-re a ∉ L_{M_{1}}(A) = L_{1}(A). Ekkor a ∉ L_{1}(A) ∪ Ω_{2} = (L_{1} × L_{2})(A ∪ Ω_{2}) teljesül és ezért M-nek van olyan két sora, melyek megegyeznek A ∪ Ω_{2}-n, de különböznek a-ban. Másszóval van M_{1}-nek két sora, melyek megegyeznek A-ban, különböznek a-ban, és ugyanabban a particióosztályban vannak. Alkalmazzuk a 3.3 Lemmát M_{1}-re:

(M_{1} sorainak száma) ≥ s(L_{1}) + (M_{2} különböző sorainak száma) − 1. (3.12)

Ismét felhasználva a 3.3 Lemmát kapjuk

(M_{2} különböző sorainak száma) ≥ s(L_{2}).  (3.13)

(3.12)-ből és (3.13)-ból:

(M sorainak száma) ≥ s(L_{1}) + s(L_{2}) − 1,

ami bizonyítja (3.7)-t és így a tételt is.

Analóg módon definiálhatjuk Sperner-rendszerek direkt szorzatát.

3.5 Definició Legyen Ω = Ω_{1} ∪Ω_{2} az Ω alaphalmaz egy particiója, és legyenek K_{1} és K_{2} Sperner-rendszerek Ω_{1}-n illetve Ω_{2}-n. Ekkor a direkt szorzat definiciója K_{1} × K_{2} = {A ∪ B| A ∈ K_{1}, B ∈ K_{2}}

Az előző tétel bizonyításában szereplő konstrukció mutatja, hogy s(K_{1} ×K_{2}) ≤ s(K_{1}) + s(K_{2}) − 1. Bár számos esetben fennáll az egyenlőség, a 3.2 Tétel állítása nem igaz kulcsrendszerekre.

3.6 Példa [7] Legyen Ω_{1} = {1, 2, 3, 4, 5}, Ω_{2} = {6, 7, 8, 9, 10}, K_{1} = {{1, 2}, {3, 4}, {1, 5}, {2, 5}, {3, 5}, {4, 5}}, K_{2} = {{6, 7}, {8, 9}, {6, 10}, {7, 10}, {8, 10}, {9, 10}}. Könnyen látható, hogy

K_{1}^{−1} = {{5}, {1, 3}, {1, 4}, {2, 3}, {2, 4}}.

A 2.14 Lemma szerint s(K_{1}) ≥ 4. Tegyük fel, hogy s(K_{1}) = 4 és ezt az M mátrix realizálja. Ekkor a 2.15 Lemmában szereplő G(M) gráfnak 4 csúcsa van és 5 éle K^{−1} elemeivel cimkézve. Néhány eset megkülönböztetésével látható, hogy a 2.15 Lemma miatt a hatodik él cimkéje {1, 2}, {1, 2, 5}, {3, 4} vagy {3, 4, 5} lehet. Ezek azonban mind kulcsok, ami ellentmondás. Tehát s(K_{1}) = s(K_{2}) ≥ 5. Másfelől a következő mátrix mutatja, hogy s(K_{1} × K_{2}) ≤ 8:

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 0 1 0 1 0
1 1 1 1 0 0 0 0 0 0
1 1 1 1 0 1 1 1 1 0
1 1 1 1 0 1 0 0 1 2
0 1 0 1 1 0 0 0 0 0
1 0 0 1 2 1 1 1 1 0

(nem triviális, (K_{1} × K_{2})^{−1} bonyolult struktúrája miatt).

4. s(L_{k}^{n}) nagyságrendje

Ebben a fejezetben rögzített k mellett n → ∞-re vizsgáljuk s(L_{k}^{n}) és s(L_{n−k}^{n}) értékét.

4.1 Tétel [7]

\sqrt{2}(\frac{1}{k−1})^{(k−1)/2}n^{(k−1)/2} < s(L_{k}^{n}) < 2^{3k/2}n^{(k−1)/2} (2 ≤ k < n).  (4.1)

Bizonyítás: (4.1) első egyenlőtlensége a 2.14 Lemma egyszerű következménye. Most mutatunk egy konstrukciót, mely bizonyítja a második egyenlőtlenséget.

Legyen p egy prímszám. Megmutatjuk, hogy létezik egy 2⌊\sqrt{p}⌋ számosságú D halmaz, hogy minden i egész számhoz léteznek d_{1}, d_{2} ∈ D, hogy

i ≡ d_{1} − d_{2} (mod p).  (4.2)

Egy ilyen D halmaz definiciója például:

D = {0, 1, 2, …, a − 1, 2a, 3a, …, (a − 1)a},

ahol a = ⌈\sqrt{p}⌉. Tegyük fel, hogy valamely i-re 0 ≤ i < p és i = al + r (0 ≤ r < a). Ha 1 ≤ l ≤ a − 2 és 0 < r < a, akkor d_{1} = (l + 1)a és d_{2} = a − r teljesíti (4.2)-t. Ha i = al (2 ≤ l ≤ a − 1), akkor d_{1} = al és d_{2} = 0 megfelelő. a = 3a − 2a, míg a többi kifejezhető 0 és az 1, 2, …, a − 1 számok különbségeként (p = 2-re vagy p = 3-ra D = {0, 1} jó). Ekkor D számossága:

|D| = 2a − 2 = 2(⌈\sqrt{p}⌉ − 1) = 2⌊\sqrt{p}⌋.

Most definiáljuk polinomok egy 2^{k}⌊\sqrt{p}⌋^{k−1} számosságú P halmazát:

P = {c_{k−1}x^{k−1} + c_{k−2}x^{k−2} + … + c_{1}x + c_{0}| c_{0}, c_{1}, …, c_{k−1} ∈ D, c_{k−1} = 0 vagy 1}.

Legyen M egy |P| × p-es mátrix. A sorok feleljenek meg P tagjainak. A z(x) ∈ P-nek megfelelő sor j. eleme legyen z(j) (mod p) (0 ≤ j ≤ p − 1, 0 ≤ z(j) ≤ p − 1). Belátjuk, hogy M reprezentálja L_{k}^{p} -t. A 2.13 Lemma alapján elegendő belátni, hogy M reprezentálja K_{k}^{p}-t. Elég azonban csak a 2.16 Lemma feltételeit ellenőrizni K = \binom{Ω}{k}, K^{−1} = \binom{Ω}{k−1}-re (ahol |Ω| = p).

Tegyük fel, hogy a z_{1}(x)-nek és z_{2}(x)-nek megfelelő sorok k helyen megegyeznek:

z_{1}(t_{i}) ≡ z_{2}(t_{i}) (mod p) (0 ≤ t_{1} < t_{2} < … < t_{k} < p).

A z_{1}(x) − z_{2}(x) legfeljebb (k − 1)-edfokú polinomnak k különböző gyöke van. Ez az ellentmondás mutatja, hogy z_{1} és z_{2} ugyanaz, és a “két” sor valójában egy.

Válasszuk most a 0 ≤ t_{1} < t_{2} < … < t_{k−1} < p egész számokat tetszőlegesen. Találnunk kell két sort, melyek megegyeznek a t_{1}-edik, t_{2}-edik,…,t_{k−1}-edik helyen. Tekintsük a

w(x) = (x − t_{1})(x − t_{2}) … (x − t_{k−1}) = x^{k−1} + a_{k−2}x^{k−2} + … + a_{1}x + a_{0}

polinomot. a_{i}-hez (0 ≤ i ≤ k − 1) található D-nek két c_{i} és c′_{i} eleme, hogy a_{i} ≡ c_{i} − c′_{i} (mod p). Ekkor w(x) = z(x) − z′(x), ahol

z(x) = x^{k−1} + c_{k−2}x^{k−2} + … + c_{1}x + c_{0} és

z′(x) = c′_{k−2}x^{k−2} + … + c′_{1}x + c′_{0}.

z(x) és z′(x) nyilván két különböző eleme P-nek. Másfelől valóban z(t_{i}) ≡ z′(t_{i}) (mod p). A 2.16 Lemma mindkét feltételét ellenőriztük, így M tényleg reprezentálja L_{k}^{p}-t. Tehát:

s(L_{k}^{p}) ≤ 2^{k}p^{(k−1)/2}.

Tetszőleges n-re válasszunk egy p prímet, melyre n ≤ p ≤ 2n. Ilyen P.L. CSEBISEV tétele (például [13]-ban) szerint létezik. Most készítsünk egy mátrixot, mely reprezentálja L_{k}^{p}-t, és hagyjuk el p − n oszlopát. Ez a mátrix reprezentálja L_{k}^{n}-t, ezért

s(L_{k}^{n}) ≤ 2^{k}p^{(k−1)/2} ≤ 2^{k}(2n)^{(k−1)/2} ≤ 2^{3k/2}n^{(k−1)/2},

tehát a tételt bebizonyítottuk.

Azt mondjuk, hogy egy n oszlopból álló M mátrix egy tökéletes k-hibajavító adatbázis, ha tetszőleges k oszlopát törölve a megmaradt mátrix bármely két sora különbözik, de bármelyik k + 1 sorát törölve lesz két sor, melyek megegyeznek. Egy n attributumú tökéletes k-hibajavító adatbázis lehetséges sorai számának meghatározása nyilván ekvivalens s(L_{n−k}^{n}) meghatározásával. A következő tétel első egyenlőtlensége megjavítja erre az esetre a 2.14 Lemmát.

4.2 Tétel [14] n > n_{0}(k), k ≥ 1-re

\frac{1}{(k+1)!}n^{(2k+1)/3} < s(L_{n−k}^{n}) < \frac{1}{k!}n^{k}.  (4.3)

Bizonyítás: A második egyenlőtlenséget egy egyszerű konstrukció mutatja. Legyenek Ω k-elemű részhalmazai E_{1}, E_{2}, …, E\binom{n}{k}. Az i-edik sor j-edik helyén álljon 0 ha j ∉ E_{i}, ha pedig j ∈ E_{i}, akkor i. Az így kapott mátrix k ≥ 1-re reprezentálja L_{n−k}^{n}-t.

A másik irány bizonyításához tegyük fel, hogy M reprezentálja L_{n−k}^{n}-t. Felhasználjuk K^{}ŐV^{}ÁRI-S^{}ÓS-TUR^{}ÁN egy extremális gráfelméleti eredményét.

4.3 Lemma [18] Tegyük fel, hogy a G(V, E) gráf nem tartalmazza részgráfként a K(2, p) teljes páros gráfot. Ekkor

|E| < \sqrt{\frac{p − 1}{2}}|V |^{3/2} + \frac{|V |}{2}.  (4.4)

Szükségünk van még néhány jelölésre. Jelölje V az adatbázis sorainak a halmazát. Legyenek α, β ∈ V,ekkor D(α, β) = {i| α(i) ≠ β(i)}. Jelölje H(α, β) = |D(α, β)| az α és β sorok Hamming-távolságát. Definiáljuk az M-hez tartozó G minimális távolsággráfot a V csúcshalmazon úgy, α-t és β-t pontosan akkor kössük össze éllel, ha H(α, β) = k + 1. (α, β) ∈ G színe legyen D (ahol D ⊆ Ω, |D| = k + 1), ha D = D(α, β). Jelölje szokásos módon deg(α) α fokát, Γ(α) pedig α szomszédainak halmazát. Minden k + 1 elemű D ⊆ Ω-hoz válasszuk ki G egy D színű élét. Ez az \binom{n}{k+1} pár alkotja a G_{0} redukált minimális távolsággráfot. Ebben deg_{0}-lal illetve Γ_{0}-lal jelöljük egy pont fokát illetve szomszédai halmazát.

4.4 Lemma

(i) amennyiben (α, β) ∉ G, akkor |Γ(α) ∩ Γ(β)| < 3^{2k+2}, (ii) n > n_{0}(k) esetén tetszőleges α, β ∈ V -re |Γ_{0}(α) ∩ Γ_{0}(β)| < n3^{k}.

Bizonyítás: Legyen C = {x ∈ Ω| α(x) ≠ β(x)}, ekkor |C| = H(α, β). Feltehető, hogy |C| ≤ 2k+2, ugyanis különben a lemma triviálisan igaz, mert ekkor nem létezik γ ∈ V, hogy {α, γ} ∈ G, {β, γ} ∈ G.

Vegyük észre, hogy minden x ∈ C-re γ(x) különbözik α(x)-től vagy β(x)-től, ezért

C ⊆ D(α, γ) ∪ D(β, γ).  (4.5)

Továbbá D(α, γ)\C = D(β, γ)\C.

Szükségünk van egy állításra, mely szerint γ -t (majdnem) meghatározza D(α, γ) és D(β, γ) C-beli nyoma.

4.5 Állítás Tegyük fel, hogy γ, γ′ ∈ Γ(α) ∩ Γ(β), γ ≠ γ′, valamint azt, hogy D(α, γ) ∩ C = D(α, γ′) ∩ C és D(β, γ) ∩ C = D(β, γ′) ∩ C. Ekkor |C| = k + 1 és (D(α, γ)\C) = (D(α, γ′)\C) = ∅.

Bizonyítás: (4.5) szerint D(γ, γ′) ⊆ D(α, γ) ∪ D(α, γ′). γ és γ′ megegyezik C\(D(α, γ) ∩ D(β, γ))-n, ezért

H(γ, γ′) ≤ |D(α, γ) ∩ D(β, γ) ∩ C| + |D(α, γ)\C| + |D(α, γ′)\C|.  (4.6)

Mivel |D(α, γ′)\C| = |D(β, γ)\C|, azért (4.6) jobb oldala egyenlő 2(k+ 1) − |C|-kel. Ha |C| > k + 1, akkor ez a H(γ, γ′) < k + 1 ellentmondáshoz vezet. Így |C| = k + 1, és (4.6)-ban egyenlőség áll fenn. Ezért a D(α, γ)\C és D(α, γ′)\C halmazok diszjunktak.

Most térjünk vissza 4.4 Lemma bizonyításához. Az (i) esetben a 4.5 Állítás szerint |Γ(α) ∩ Γ(β)| legfeljebb annyi, mint azon A, B ⊆ C = D(α, β) halmazpárok száma, melyekre |A| = |B|, A∩B = ∅ és |A| ≥ |C|−k−1. (Itt A = D(α, γ)\D(β, γ) és B = D(β, γ)\D(α, γ).) Ezért

|Γ(α) ∩ Γ(β)| ≤ ∑_{i≥|C|−k−1} \binom{|C|}{2i}\binom{2i}{i} < 3^{|C|} ≤ 3^{2k+2}.

(ii) bizonyításához most már feltehető, hogy |C| = k +1. Válasszunk A, B ⊆ C halmazokat, melyekre |A| = |B| = i, A ∩ B = ∅, és tekintsük az összes γ ∈ Γ_{0}(α) ∩ Γ_{0}(β)-t, hogy A = D(α, γ)\D(β, γ) és B = D(β, γ)\D(α, γ). Ekkor G_{0} definiciója miatt tetszőleges γ ∈ Γ_{0}(α)-ra |D(α, γ)\C| = i > 0. Így a 4.5 Állítás szerint az ilyen γ-k száma legfeljebb (n − |C|)/i. Ezért

|Γ_{0}(α) ∩ Γ_{0}(β)| ≤ ∑_{i≥1} \binom{|C|}{2i}\binom{2i}{i}\frac{n − k − 1}{i} < n ∑_{i≥1} \binom{k + 1}{2i}\binom{2i}{i}\frac{1}{i} < n3^{k}.

A 4.2 tétel bizonyításához tekintsük a G_{0} M-hez tartozó redukált minimális távolsággráfot. A 4.4 Lemma szerint G_{0} nem tartalmazza részgráfként a K(2, n3^{k}) teljes páros gráfot. Ekkor a 4.3 Lemma szerint

\binom{n}{k + 1} = |G_{0}| ≤ \sqrt{\frac{n3^{k}}{2}} |V |^{3/2} + \frac{|V |}{2},

amiből a tétel következik.

5. s(L_{k}^{n}) meghatározása k néhány értékére

Ebben a fejezetben s(L_{k}^{n}) néhány konkrét értékét határozzuk meg.

5.1 Tétel [10],[7]

s(L_{1}^{n}) = 2, s(L_{2}^{n}) = ⌈(1 + \sqrt{1 + 8n})/2⌉,
s(L_{n−1}^{n}) = n, s(L_{n}^{n}) = n + 1.

Bizonyítás: Az első három esetben a tétel azt állítja, hogy a 2.14 Lemmából származó becslés (természetesen ha nem egész, akkor a felső egészrésze) éles. Tehát elég 3 konstrukciót mutatni. Hogy ezek tényleg jók, a 2.16 Lemma alapján könnyen ellenőrizhető.

k = 1 esetén:

\begin{matrix}0 & 0 & … & 0 \\ 1 & 1 & … & 1 \end{matrix}

k = 2 esetén: (minden oszlopban pontosan 2 darab nulla áll úgy, hogy különböző oszlopokhoz tartozó nullák különböző sorpárokhoz tartoznak)

\begin{matrix}0 & 0 & 0 & … & 0 & 1 & 1 & … & 1 \\ 0 & 2 & 2 & … & 2 & 0 & 0 & … & 2 \\ 3 & 0 & 3 & … & 3 & 0 & 3 & … & 3 \\ 4 & 4 & 0 & … & 4 & 4 & 0 & … & 4 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ s − 1 & s − 1 & s − 1 & … & s − 1 & s − 1 & s − 1 & … & s − 1 \\ s & s & s & … & 0 & s & s & … & s \end{matrix}

k = n − 1 esetén:

\begin{matrix}1 & 0 & … & 0 \\ 0 & 1 & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & 1 \end{matrix}

A k = n esetben a 2.15 Lemma van segítségünkre. Tegyük fel, hogy egy M mátrix reprezentálja K_{n}^{n} = {Ω}-t. Ekkor Ω bármely (n−1)-elemű A részhalmazához létezik egy él G(M)-ben, melynek cimkéje A. Ezen élekből alkotott részgráf a lemma szerint körmentes. Így G(M)-nek legalább n + 1 csúcsa van, tehát s(L_{n}^{n}) ≥ n + 1. Az egyenlőséget a következő példa mutatja:

\begin{matrix}0 & 0 & … & 0 \\ 1 & 0 & … & 0 \\ 0 & 1 & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & 1 \end{matrix}

Ezzel a tétel bizonyítását befejeztük.

Még két k értékre ismertek tételek. Ezeket bizonyítás nélkül megemlítjük. s(L_{n−2}^{n})-re ad jobb becslést a 4.2 Tétel első egyenlőtlenségénél a következő

tétel, mely egyben megmondja a pontos nagyságrendet is.

5.2 Tétel [14]

\frac{1}{12}n^{2} < s(L_{n−2}^{n}) < \frac{1}{2}n^{2}.  (5.1)

A 2.14 Lemmából éppen s(L_{3}^{n}) ≥ n adódik, egyenlőség akkor áll, ha tudunk konstruálni egy n × n-es M mátrixot, melyre:

1) bármely különböző a, b, c ∈ Ω-hoz létezik két sor, melyek megegyeznek a-ban és b-ben, de különböznek c-ben,

2) bármely különböző a, b, c ∈ Ω-hoz nem létezik két sor, melyek mindháromban megegyeznek. Tekintsük a duális problémát. Egy oszlop természetes módon meghatározza a

sorok V halmazának egy particióját az elemek egyenlősége alapján. Azt mondjuk, hogy egy partició lefedi az (α, β) párt (α, β ∈ V, α ≠ β) akkor és csak akkor, ha α és β a particiónak ugyanabban az osztályában van. Ekkor a fenti két feltétel a következőképpen fogalmazható:

Találjunk n particióját V -nek (|V | = n), melyekre: 1’) bármely két particióhoz létezik egy (α, β) pár, melyet mindkettő lefed, 2’) semelyik (α, β) párt nem fedi le három partició.

Azonban a particiópárok száma szintén \binom{n}{2} és 2’) miatt különböző particiópárok nem fedhetik le ugyanazt a párt. Tehát 1’) és 2’) ekvivalens a következőkkel:

(i) bármely két particióhoz pontosan egy pár létezik, melyet mindkettő lefed, (ii) bármelyik párt pontosan két partició fedi le.

5.3 Definició [15] Az (i)-t és (ii)-t teljesítő particiók egy osztályát ortogonális dupla fedésnek nevezzük.

A mi szempontunkból a következő eredmény a leglényegesebb.

5.4 Tétel [2] [16] n ≥ 7, n ≠ 8-ra létezik az n-elemű halmaznak n particióval történő ortogonális dupla fedése.

Az ortogonális dupla fedések elmélete szerteágazó, általában design-típusú problémákra vezet. Rövid összefoglalók találhatók például [17]-ben és [11]-ben a legújabb eredményekről, ugyanitt további hivatkozások is találhatók.

6. Egy kulcsrendszer reprezentációja

Ebben a fejezetben egy, az eddigiektől eltérő K_{n} kulcsrendszer minimális reprezentációja kerül tárgyalásra. Először egy, a bizonyítás lényegét adó kombinatorikai segédtételt (6.5 Tétel) bizonyítok. Majd ez alapján a 6.6 Tételben belátom, hogy

s(K_{n}) \sqrt{|K_{n}^{−1}|} és |K_{n}^{−1}| közül (2.17 Lemma) az utóbbihoz van közelebb. Végül a 6.7 tételben |K_{n}^{−1}| nagyságrendjének meghatározása teszi teljessé a bizonyítást.

6.1 Definició Egy F fát nevezzünk irányított fának, ha fa, és ha van az éleknek egy olyan irányítása, hogy pontosan egy csúcsból (gyökér) érhető el a többi az irányítás szerint. Jelöljük egy v csúcs kimenő szomszédai halmazát N(v)-vel, míg (a gyökér kivételével) az egyértelműen létező bemenő szomszédot n(v)-vel. A fa levelei halmazát jelölje l(F).

6.2 Definició Legyen adva egy U (véges) halmaz. Egy F = F (U) fát nevezzünk cimkézett fának, ha F minden v csúcsához hozzá van rendelve U-nak egy A(v) részhalmaza.

Legyen U egy tetszőleges m elemű halmaz, mondjuk U = {1, 2, ..., m} (m ≥ 2). Tekintsük irányított cimkézett fáknak azt az F = F^{(m)} családját, amely család F fáinak csúcsai a következőképpen vannak cimkézve. A g gyökér cimkéje A(g) = U. Tetszőleges gyökértől különböző v csúcsra pedig valamely N(v) = N_{0}(v) ·∪N_{1}(v) diszjunkt felbontás mellett:

A(v) ⊆ A(n(v)),  (6.1)
|A(v)| ≥ 2,  (6.2)
w_{1}, w_{2} ∈ N_{i}(v) ⇒ A(w_{1}) ∩ A(w_{2}) = ∅ (i = 0, 1),  (6.3)
w_{1} ∈ N_{i}(v), w_{2} ∈ N_{1−i}(v) ⇒|A(w_{1}) ∩ A(w_{2})| ≤ 1 (i = 0, 1).  (6.4)

Jelölje T (m) = max_{F ∈F^{(m)}} |l(F)|. T (m) becslése előtt szükségünk van két egyszerű

technikai lemmára.

6.3 Lemma

T (m_{1}) + T (m_{2}) + … + T (m_{k}) ≤ T (m_{1} + m_{2} + … m_{k}).  (6.5)

Bizonyítás: Elég belátni, hogy T (m_{1}) + T (m_{2}) ≤ T (m_{1} + m_{2}). Ha adott két irányított cimkézett fa az U_{1} illetve U_{2} m_{1} illetve m_{2} elemű diszjunkt halmazokkal cimkézve a gyökerüknél, melyek rendelkeznek a (6.1)-(6.4) tulajdonságokkal, akkor az a fa, amelyiknek a gyökerének a cimkéje U_{1} ∪ U_{2} és a gyökér össze van kötve a két kisebb fa gyökerével szintén rendelkezik a (6.1)-(6.4) tulajdonságokkal.

A következő lemmában a 6.5 Tételben használt függvények néhány tulajdonságát említem meg. Most, és a fejezet további részeben is az e alapú logaritmust log jelöli.

6.4 Lemma Rögzített 0 < ε, δ < 1-re x > 1 esetén:

f(x) = e^{log^{1−δ} x} szigorúan monoton növő,  (6.6)
g(x) = x^{ε+log^{−δ} x} szigorúan monoton növő,  (6.7)
h(x) = x^{1+ε+log^{−δ} x} szigorúan monoton növő,  (6.8)
h(x_{1})+h(x_{2}) + … + h(x_{k}) ≤ h(x_{1} + x_{2} + … x_{k}).  (6.9)

Bizonyítás: f′(x) = \frac{1−δ}{x log^{δ} x}e^{log^{1−δ} x} > 0 bizonyítja (6.6)-t. g(x) illetve h(x) két szigorúan monoton függvény szorzata. (6.7) alapján

h(x_{1}) + h(x_{2}) = x_{1}^{1+ε+log^{−δ} x_{1}} + x_{2}^{1+ε+log^{−δ} x_{2}} ≤ x_{1}(x_{1} + x_{2})^{ε+log^{−δ} (x_{1}+x_{2})}+
+ x_{2}(x_{1} + x_{2})^{ε+log^{−δ} (x_{1}+x_{2})} = h(x_{1} + x_{2}),

ami bizonyítja (6.9)-t. Tehát beláttuk a lemma összes állítását.

6.5 Tétel Minden (ε_{0} ≥)ε > 0-hoz létezik csak ε-tól függő δ, hogy minden m ≥ 2 egészre

T (m) ≤ m^{1+ε+log^{−δ} m}.  (6.10)

Bizonyítás: Legyen ε rögzített. m-re vonatkozó indukcióval bizonyítunk. Mivel a jobb oldalon m kitevője fix m-re δ → 0 esetén (2 + ε)-hoz tart és nyilván T (m) ≤ \binom{m}{2}, ezért ha M csak ε -tól függő (elég nagy) konstans (amit később választunk meg), akkor feltehető hogy m ≤ M esetén igaz az állítás.

Tegyük most fel, hogy minden m(> M)-nél kisebbre igaz az állítás. Tekintsük azt az F fát, amelyre |l(F)| maximális. Legyen N(g) = {v_{1}, v_{2}, …, v_{s}, v_{s+1}, …, v_{t}} valamint N_{1}(g) = {v_{1}, v_{2}, …, v_{s}} és N_{2}(g) = {v_{s+1}, v_{s+2}, …, v_{t}} az F definiciójában szereplő felbontás. Jelölje m_{i} = |A(v_{i})| valamint F_{i} a v_{i}-ből mint gyökérből induló részfát 1 ≤ i ≤ t-re. Ez csak úgy lehetséges, ha T (m_{i}) = |l(F)| minden 1 ≤ i ≤ t -re. Tehát azt elég belátni, hogy

∑_{i=1}^{t} T (m_{i}) ≤ m^{1+ε+log^{−δ} m}.  (6.11)

Legyen c = c(ε) olyan nagy, hogy (1 − (\frac{1}{6})^{1/ε})^{ε} ≤ 1 − \frac{1}{c} és 2 < c^{ε} valamint M = M(ε) olyan nagy, hogy M^{ε} > 4c^{2} max_{2≤h≤c^{2}} T (h) Most 4 részre bontjuk az

1 ≤ i ≤ t indexhalmazt:

P = {i| m_{i} ≤ c^{2}},
Q = \{i| c^{2} < m_{i} ≤ \frac{m}{c}\},
R = \{i| \frac{m}{c} < m_{i} ≤ m(1 − \frac{1}{c})^{1/ε}\},
S = \{i| m(1 − \frac{1}{c})^{1/ε} < m_{i}\}.

Vegyük észre, hogy c választása miatt

S ⊆ \{i| (\frac{m−m_{i}}{m})^{ε} < \frac{1}{6}\}.  (6.12)

1. Eset: S ≠ ∅. Legyen j ∈ S. F definiciójának szimmetriája miatt feltehető, hogy 1 ≤ j ≤ s. Ekkor

∑_{i=1}^{t} T (m_{i}) = T (m_{j}) + ∑_{{i=1 \atop i≠j}}^{t} T (m_{i}) ≤ T (m_{j}) + T (m − m_{j}) + T (2m − 2m_{j}), (6.13)

felhasználva (6.5)-t, valamint hogy (6.3) miatt ∑_{{i=1 \atop i≠j}}^{s} m_{i} ≤ m − m_{j} és hogy (6.2)-(6.4)

miatt ∑_{i=s+1}^{t} m_{i} ≤ m − m_{j} + (t − s) ≤ 2(m − m_{j}). Az indukciós feltevést, valamint

(6.7)-t felhasználva:

T (m_{j}) ≤ m^{1+ε+log^{−δ} m} − (m − m_{j})m^{ε+log^{−δ} m},  (6.14)
T (m − m_{j}) ≤ (m − m_{j})^{1+ε+log^{−δ}(m−m_{j})},  (6.15)
T (2m − 2m_{j}) ≤ (2m − 2m_{j})^{1+ε+log^{−δ}(2m−2m_{j})}.  (6.16)

Vegyük észre, hogy

(2m − 2m_{j})^{1+ε+log^{−δ}(2m−2m_{j})} ≤
≤2^{1+ε+log^{−δ}(m−m_{j})} · (m − m_{j})^{1+ε+log^{−δ}(m−m_{j})} ≤
≤5 · (m − m_{j})^{1+ε+log^{−δ}(m−m_{j})},  (6.17)

felhasználva, hogy m_{j} ≤ m−3 esetén 2 kitevőjében a harmadik tag 1-gyel becsülhető felülről. Az m_{j} = m−1 vagy m_{j} = m−2 esetek külön ellenőrizhetők (például ekkor

∑_{i=1}^{t} T (m_{i}) ≤ T (m − 1) + 3, ami elég nagy m esetén az indukciót felhasználva kisebb

mint a tétel jobboldalán lévő függvény). A fentiek alapján

(m − m_{j})^{1+ε+log^{−δ}(m−m_{j})} + (2m − 2m_{j})^{1+ε+log^{−δ}(2m−2m_{j})} ≤
≤ 6 · (m − m_{j})^{1+ε+log^{−δ}(m−m_{j})} =
= (m − m_{j})m^{ε+log^{−δ} m}(6 · (\frac{m−m_{j}}{m})^{ε}e^{log^{1−δ}(m−m_{j})−log^{1−δ} m}).  (6.18)

Most (6.12)-(6.18)-t összevetve és felhasználva (6.6)-t kapjuk a (6.11) egyenlőtlenséget.

2. Eset: S = R = ∅. Ekkor az 1-től t-ig menő összegzés P ∪ Q -n megy. Az indukciós feltevés szerint

∑_{i=1}^{t} T (m_{i}) ≤ ∑_{i∈P ∪Q} m_{i}^{1+ε+log^{−δ} m_{i}} =

= ∑_{i∈P ∪Q} m_{i}(\frac{m_{i}}{m})^{ε}m^{ε+log^{−δ} m} e^{log^{1−δ} m_{i}−log^{1−δ} m}.  (6.19)

Q definiciója és a c-re tett második feltevés miatt minden 1 ≤ i ≤ t-re (\frac{m_{i}}{m})^{ε} ≤ \frac{1}{2}. (6.6) felhasználásával:

∑_{i∈P ∪Q} m_{i}(\frac{m_{i}}{m})^{ε}m^{ε+log^{−δ} m} e^{log^{1−δ} m_{i}−log^{1−δ} m} ≤ \frac{1}{2} ∑_{i∈P ∪Q} m_{i}m^{ε+log^{−δ} m}. (6.20)

A nyilvánvaló ∑_{i=1}^{t} m_{i} = ∑_{i=1}^{s} m_{i} + ∑_{i=s+1}^{t} m_{i} ≤ m + m = 2m egyenlőtlenségből (al-

kalmaztuk (6.3)-t) (6.19) és (6.20) felhasználásával adódik a (6.11) egyenlőtlenség.

3. Eset: S = ∅, R ≠ ∅. Ekkor ∑_{i=1}^{t} T (m_{i}) = ∑_{i∈P} T (m_{i}) + ∑_{i∈Q} T (m_{i}) + ∑_{i∈R} T (m_{i}).

Továbbá az indukciós feltevés szerint:

∑_{i∈R} T (m_{i}) ≤ ∑_{i∈R} m_{i}^{1+ε+log^{−δ} m_{i}} =

=\frac{1}{2} ∑_{i∈R} m_{i}m^{ε+log^{−δ} m}(2 · (\frac{m_{i}}{m})^{ε}e^{log^{1−δ} m_{i}−log^{1−δ} m}).  (6.21)

Felhasználva (6.6)-t és R definicióját:

\frac{1}{2} ∑_{i∈R} m_{i}m^{ε+log^{−δ} m}(2 · (\frac{m_{i}}{m})^{ε}e^{log^{1−δ} m_{i}−log^{1−δ} m}) ≤

≤\frac{1}{2} ∑_{i∈R} 2m_{i}(1 − \frac{1}{c})m^{ε+log^{−δ} m} =

=\frac{1}{2}(∑_{i∈R}(m_{i} + m_{i} − \frac{m_{i}}{c} ))m^{ε+log^{−δ} m} − \frac{1}{2}(∑_{i∈R} \frac{m_{i}}{c} )m^{ε+log^{−δ} m}.  (6.22)

R definiciója miatt és mivel R ≠ ∅

\frac{1}{2}(∑_{i∈R} \frac{m_{i}}{c} )m^{ε+log^{−δ} m} ≥ \frac{1}{2c^{2}} m^{1+ε+log^{−δ} m}.  (6.23)

M választása miatt

2c^{2} ∑_{i∈P} T (m_{i}) < m · M^{ε} ≤ m^{1+ε+log^{−δ} m}.  (6.24)

A Q-ra történő összegzést hasonlóan becsülhetjük, mint a 2. esetben:

∑_{i∈Q} T (m_{i}) ≤ ∑_{i∈Q} m_{i}(\frac{m_{i}}{m})^{ε}m^{ε+log^{−δ} m} e^{log^{1−δ} m_{i}−log^{1−δ} m} ≤

≤ \frac{1}{2} ∑_{i∈Q} m_{i}m^{ε+log^{−δ} m}.  (6.25)

Azonban vegyük észre, hogy

∑_{i∈Q} m_{i} + ∑_{i∈R}(m_{i} + (m_{i} − \frac{m_{i}}{c})) ≤ 2m.  (6.26)

Ugyanis egy tetszőleges i ∈ R-hez (feltehető, hogy 1 ≤ i ≤ s) tartozó A(v_{i}) halmazba (6.3) miatt csak az s + 1 ≤ j ≤ t-hez tartozó A(v_{j}) diszjunkt halmazok metszhetnek bele. Mivel minden j ∈ Q ∪ R-re m_{j} > c^{2}, ezért legfeljebb \frac{m}{c^{2}} darab A(v_{j}), j ∈ Q ∪ R metszhet bele A(v_{i})-be, mivel azonban R választása miatt |A(v_{i})| > \frac{m}{c} ezért (6.4) miatt A(v_{i}) elemeinek legfeljebb c-edrésze lehet valamelyik A(v_{j}), j ∈ Q ∪ R eleme, másszóval legalább m_{i} − \frac{m_{i}}{c} elem nem lehet s + 1 ≤ j ≤ t, j ∈ Q ∪ R-hez tartozó A(v_{j})-vel lefedve. Ezért

∑_{{i=s+1 \atop i∈Q∪R}}^{t} m_{i} + ∑_{{i=s+1 \atop i∈R}}^{t}(m_{i} − \frac{m_{i}}{c} ) ≤ m és ∑_{{i=1 \atop i∈Q∪R}}^{s} m_{i} ≤ m.

Így ebben az esetben is (6.21)-(6.26) alapján fennáll a (6.11) egyenlőtlenség. Ezzel tehát a tétel bizonyítását befejeztük.

6.6 Tétel Legyen K_{n} = {{1, 2}, {2, 3}, …, {n−2, n−1}, {n−1, n}, {n, 1}}. Ekkor minden (ε_{0} ≥)ε > 0 létezik n_{0}, hogy n > n_{0} esetén |K_{n}^{−1}|^{1−ε} ≤ s(K_{n}) ≤ |K_{n}^{−1}| + 1.

Bizonyítás: Legyen ε tetszőleges (elég kis) pozitív szám. A második egyenlőtlenség a 2.17 Lemma miatt igaz.

Határozzuk meg most K_{n}^{−1}-t. Azt állítom, hogy

K_{n}^{−1} = {{a_{1}, …, a_{k}}| a_{1} < ... < a_{k}, 2 ≤ a_{i+1} − a_{i} ≤ 3
és n − 3 ≤ a_{k} − a_{1} ≤ n − 2}.  (6.27)

Valóban, ezek nyilván antikulcsok, hiszen nem tartalmazzák K_{n} egyetlen elemét sem, maximális antikulcsok, hiszen egy ilyennél bővebb már tartalmazna szomszédos elemet. Más nem tartozik hozzájuk, hiszen aminek van két (ciklikusan) szomszédos eleme az kulcs, ami pedig legalább hármat kihagy, az nem lehet maximális, hiszen valamelyik középsőt hozzávéve még mindig antikulcsot kapunk.

A 2.16 Lemma szerint egy M mátrix reprezentálja K_{n} -et pontosan akkor, ha minden A ∈ K_{n}^{−1}-hez létezik két sor, hogy A-ban azonos elemek állnak, és ha K ∈ K_{n} és két sor megegyezik K-ban, akkor mindenütt. Az utóbbi viszont minimális sorszámú reprezentáció esetén nem lehetséges, hiszen a két egyforma sor közül az egyik elhagyásával egy kevesebb sorral rendelkező mátrixot kapunk, ami szintén reprezentálja K_{n}-et. Így tehát feltehető, hogy semelyik K ∈ K_{n}-re nem létezik M-nek két sora melyek megegyeznek K-ban.

Nézzük meg, hogy milyen “sűrűn” lehetnek a K_{n}^{−1} -beli elemekhez tartozó sorpárok. Ezek a párok persze különböző antikulcsra különbözőek, mert ha nem, akkor lenne két sor, mely két K_{n}^{−1}-beli unióján megegyezne, ami viszont egy kulcs. Legyen M egy olyan mátrix ami reprezentálja K_{n} -et és s(K_{n}) sora van. Rögzítsük M egy oszlopát, mondjuk az elsőt. Most felépítünk F_{i} cimkézett irányított fákat (annyit, ahányféle elemből legalább 2 szerepel az első oszlopban).

Legyen U = {1, …, s(K_{n})} a sorok egy sorszámozása és U ⊇ ⋃ U_{i}, |U_{i}| ≥ 2, ahol U_{i} az első oszlopban szereplő azon i-edik fajta elemhez tartozó sorok sorszámainak halmaza, amely elemből legalább 2 van. Legyen |U_{i}| = m_{i}. Az F_{i} fa g gyökerének cimkéje legyen A(g) = U_{i}. Tegyük fel, hogy már definiáltuk a fa egy v csúcsát és A(v) cimkéjét, és hogy A(v) úgy volt definiálva, hogy valamely j-edik oszlopban bizonyos egyenlő elemekhez tartozó sorok sorszámainak halmaza. Legyen

A(v) ⊇ ⋃_{i=1}^{s} A_{i}, ahol A_{i} a (ciklikusan) (j + 2)-edik oszlopban szereplő azon A(v)-

beli i-edik fajta elemekhez tartozó sorok sorszámainak halmaza, amiből legalább 2

van, míg A(v) ⊇ ⋃_{i=s+1}^{t} A_{i}, ahol A_{i} a (ciklikusan) (j + 3)-adik oszlopban szereplő

azon A(v)-beli i-edik fajta elemekhez tartozó sorok sorszámainak halmaza, amiből legalább 2 van. Legyen N(v) = {v_{1}, …, v_{t}} és A(v_{i}) = A_{i} (1 ≤ i ≤ t). Vegyük észre még azt, hogy |A_{k} ∩ A_{l}| ≤ 1 (1 ≤ k ≤ s, 1 ≤ l ≤ t), ugyanis ha legalább kételemű lenne a metszet, akkor lenne két sor mely a {j +2, j +3} kulcs oszlopaiban megegyezne, ami viszont a fentiek szerint nem lehet. Így tehát azt is látjuk, hogy az F_{i} fák rendelkeznek a (6.1)-(6.4) tulajdonságokkal.

A 6.5 Tételt alkalmazva:

|l(F_{i})| ≤ T (m_{i}) ≤ m_{i}^{1+ε+log^{−δ} m_{i}}.  (6.28)

Ebből (6.9) alapján

∑_{i} |l(F_{i})| ≤ s(K_{n})^{1+ε+log^{−δ} s(K_{n})}.  (6.29)

s(K_{n}) → +∞ miatt (ami például a korábbi állításokat nem használó (6.36) és (6.32) állítások, valamint a 2.17 Lemma miatt igaz) s(K_{n}) > m_{0}-ra (ami n > n_{0} esetén igaz):

s(K_{n})^{1+ε+log^{−δ} s(K_{n})} ≤ s(K_{n})^{1+2ε}.  (6.30)

∑_{i} |l(F_{i})| ≥ |{K ∈ K_{n}^{−1} melyre 1 ∈ K}|.  (6.31)

Ugyanis az F_{i} fák definiciója miatt a jobboldalon szereplő halmaz egy tetszőleges eleméhez (azaz egy 1-et tartalmazó antikulcshoz) tartozó azon sorok (legalább 2) halmaza, melyek megegyeznek ebben az antikulcsban részhalmaza valamely A(v)- nek (v ∈ ⋃ l(F_{i})), másrészt egy ⋃ l(F_{i})-beli elemhez nem tartozhat két {K ∈ K_{n}^{−1} melyre 1 ∈ K}-beli elem, ugyanis akkor lenne két sor, mely egy K_{n}^{−1}-belinél bővebb halmazon, azaz egy kulcson megegyezne.

Könnyen láthatóan legalább minden harmadik K_{n}^{−1}-beli antikulcs áthalad 1-n, és így:

|K_{n}^{−1}| ≥ |\{K ∈ K_{n}^{−1} melyre 1 ∈ K\}| ≥ \frac{1}{3}|K_{n}^{−1}|.  (6.32)

Mivel s(K_{n}) → +∞, ezért (6.29)-(6.32) alapján n > n_{0} esetén tényleg

|K_{n}^{−1}| ≤ s(K_{n})^{1+3ε},

amiből a tétel következik.

6.7 Tétel Legyen κ a

23x^{3} − 23x^{2} + 9x − 1 = 0  (6.33)

egyenlet egyetlen valós megoldása, azaz

κ = \frac{1}{3} − \frac{2}{3 ^{3} \sqrt{46}}( ^{3} \sqrt{\sqrt{\frac{27}{23}} + 1} − ^{3} \sqrt{\sqrt{\frac{27}{23}} − 1}).  (6.34)

Ekkor

\frac{log_{2} s(K_{n})}{n} ⟶ κ log_{2} \frac{1 − κ}{2κ} + \frac{1 − 3κ}{2} log_{2} \frac{1 − κ}{1 − 3κ}.  (6.35)

Jegyezzük meg, hogy κ ≈ 0.1770088227 …, és ha λ jelöli a fenti határértéket, akkor λ ≈ 0.4056852313 … Bizonyítás: Becsüljük meg |K_{n}^{−1}|-t:

|\{K ∈ K_{n}^{−1} melyre 1 ∈ K\}| = ⌊\frac{n}{3}⌋ ; ∑ ; {t=0 \atop t≡n(2)} \binom{\frac{n−t}{2}}{t}.  (6.36)

Ugyanis legyen K_{1} = {1, a_{1}, …, a_{k}} a baloldalon szereplő halmaz egy eleme, ekkor K_{1}-hez egyértelműen hozzárendelhető az Ω = {1, …, n} alaphalmaz egy {1, …, a_{1} − 1}, {a_{1}, …, a_{2} − 1}, …, {a_{k}, …, n} 2 és 3 nagyságú blokkokra történő felbontása. Fordítva, ha adott egy ilyen egymást követő 2-es, 3-as blokkokra bontás, akkor a blokkok első elemei meghatároznak egy kívánt antikulcsot. (6.36) jobboldalán éppen az ilyen felbontások száma szerepel (ha t a hármas blokkok száma, akkor \frac{n−t}{2} az összes blokkok száma).

|K_{n}^{−1}| becsléséhez tehát elég (6.36) jobboldalán a legnagyobb tag nagyságrendjét megbecsülni, ugyanis ekkor (6.32) alapján ez ad egy alsó becslést, ennek \frac{3(n+2)}{6} -szorosa pedig felső becslést.

Ehhez írjuk fel az összeg két egymást követő tagjának hányadosát és nézzük meg, mikor lesz ez 1. Egyszerűsítések után:

\frac{(\frac{n−t}{2} − t + 3)(\frac{n−t}{2} − t + 2)(\frac{n−t}{2} − t + 1)}{(\frac{n−t}{2} + 1)t(t − 1)} = 1.

Ezt rendezve és az x = \frac{t}{n} változót bevezetve:

23x^{3} − (23 + \frac{96}{n})x^{2} + (9 + \frac{68}{n} + \frac{112}{n^{2}})x − (1 + \frac{12}{n} + \frac{44}{n^{2}} + \frac{48}{n^{3}} ) = 0.  (6.37)

Mivel a (6.37) baloldalán álló polinomok függvénysorozata minden véges intervallumban egyenletesen tart a (6.33) baloldalán álló polinomhoz, ezért (6.37)-nek elég nagy n esetén, úgy mint (6.33)-nak, egyetlen valós κ_{n} megoldása van, és minden ε > 0 -hoz létezik n_{0}, hogy n > n_{0} esetén κ − ε ≤ κ_{n} ≤ κ + ε.

Most a fentiek alapján t = κ_{n}n-et helyettesítve (6.36)-ba

\binom{(\frac{1−κ}{2} − ε)n}{(κ − ε)n} ≤ |K_{n}^{−1}| ≤ \frac{n + 2}{2}\binom{(\frac{1−κ}{2} + ε)n}{(κ + ε)n}.  (6.38)

A Stirling-formulát

n! = (\frac{n}{e})^{n}\sqrt{2πn} e^{\frac{Θ_{n}}{12n}} (0 < Θ_{n} < 1)

alkalmazva

\binom{cn}{dn} = (\frac{c}{d})^{dn}(\frac{c}{c − d})^{(c−d)n}\sqrt{\frac{c}{2πnd(c−d)}} e\frac{Θ_{n}}{12n}(\frac{1}{c} − \frac{1}{d} − \frac{1}{c−d}) =

= 2n(d log_{2} \frac{c}{d} + (c − d) log_{2} \frac{c}{c−d} + o(1)) (1 ≥ c ≥ d > 0).

Ezt (6.38)-ba helyettesítve

2n(κ log_{2} \frac{1−κ}{2κ} + \frac{1−3κ}{2} log_{2} \frac{1−κ}{1−3κ} − ε′) ≤ |K_{n}^{−1}| ≤ ≤ 2n(κ log_{2} \frac{1−κ}{2κ} + \frac{1−3κ}{2} log_{2} \frac{1−κ}{1−3κ} + ε′),

amiből a 6.6 Tétel alapján a tétel következik.

Hivatkozási jegyzék

[1] W.W. ARMSTRONG, Dependency structures of database relationship, Information Processing 74 (North Holland, Amsterdam, 1974) 580-583.

[2] F.E. BENETT, LISHENG WU, On minimum matrix representation of closure operations, Discrete Appl. Math. 26 (1990) 25-40.

[3] B. BOLLOB^{}ÁS, On generalized graphs, Acta Math. Hungar. 16 (1965) 447-452.

[4] G. BUROSCH, J. DEMETROVICS, G.O.H. KATONA, The poset of closures as a model of changing databases, Order 4 (1987) 127-142.

[5] E.F. CODD, A relational model of data for large shared data banks, Comm. ACM 13 (1970) 377-387.

[6] J. DEMETROVICS, On the equivalence of candidate kays with Sperner systems, Acta Cybernet. 4 (1979) 247-252.

[7] J. DEMETROVICS, Z.F^{}ÜREDI, G.O.H. KATONA, Minimum matrix representation of closure operations, Discrete Appl. Math. 11 (1985) 115-128.

[8] J. DEMETROVICS, GY. GYEPESI, A note on minimal matrix representation of closure operations, Combinatorica 3 (1983) 177-180.

[9] J. DEMETROVICS, G. HENCSEY, L.O. LIBKIN, I.B. MUCHNIK, On the interaction between closure operations and choice functions with applications to relational databases, Acta Cybernetica 10 (1992) 129-140.

[10] J. DEMETROVICS, G.O.H. KATONA, Extremal combinatorial problems in relational database, in Fundamentals of Computation Theory 81, Proc. of the 1981 International FCT-Conference, Szeged, Hungary, 1981, Lecture Notes in Computer Science 117 (Springer, Berlin 1981) 110-119.

[11] J. DEMETROVICS, G.O.H. KATONA, A.SALI, Design Type Problems Motivated by Database Theory, preprint

[12] J. DEMETROVICS, SON HUA NAM, Closures and Sperner families, Bolyai Society Mathematical Studies, 3 Extremal Problems for Finite Sets (Ed. P. Frankl, Z. Füredi, Gy. Katona, D. Miklós) (Visegrád, Hungary, 1991) 199-204.

[13] P. ERD^{}ŐS, J. SUR^{}ÁNYI Válogatott fejezetek a számelméletből, Polygon Könyvtár 193-195.

[14] Z. F^{}ÜREDI, Perfect error-correcting databases, Discrete Appl. Math. 28 (1990) 171-176.

[15] B. GANTER, H.-D.O.F. GRONAU, R.C. MULLIN, On orthogonal double covers of K_{n}, Ars Combinatorica 37 (1994) 209-221.

[16] H.-D.O.F. GRONAU, R.C. MULLIN, preprint

[17] G.O.H. KATONA, Combinatorial and algebraic results for database relations, Database Theory - ICDT ’92, Berlin, 1992, Lecture Notes in Comput Science, 646 (Ed. J. Biskup, R. Hull) (Springer Verlag, Berlin, 1992) 1-20.

[18] T. K^{}ŐV^{}ÁRI, V.T. S^{}ÓS, P. TUR^{}ÁN, On a prblem of K. Zarankiewicz, Colloq. Math. 3 (1959) 50-57.

[19] D. LUBELL, A short proof of Sperner’s lemma, J. Combinat. Theory 1 (1966) 299.

[20] L.D. MESHALKIN, A generalization of Sperner’s theorem on the number of subsets of a finite set (in Russian), Teor. Veroyatnost. i Primenen. 8 (1963) 219-220.

[21] E. SPERNER, Ein Satz über Untermengen einer endlichen Menge, Math Z. 27 (1928) 544-548.

[22] K. YAMAMOTO, Logarithmic order of free distributive lattices, J. Math. Soc. Japan 6 (1954) 347-357.