Halmazrendszerek

Tartalom

Előszó.......................................................................I
1. Halmazrendszerek .........................................................1
1.1. A halmazrendszer és hipergráf fogalma............................1
1.2. Halmazrendszerek legegyszerűbb paraméterei......................3
1.3. Halmazrendszerek és hipergráfok megadása .......................5
1.4. Műveletek halmazrendszerekkel és hipergráfokkal..................7
1.5. Halmazrendszerek automorfizmusai ...............................9
2. Halmazrendszerek lefogása és páronként diszjunkt részrendszerek keresése .......11
2.1 Független élek....................................................11
2.2. Lefogó ponthalmazok .............................................12
2.3. Elemi becslések, mohó algoritmusok ...............................15
2.4. Lineáris programozási módszer....................................17
2.5. A és paraméterek különbsége .................................23
2.6. -kritikus halmazrendszerek ......................................25
2.7. Halmazrendszerek Kőnig-tulajdonsága ............................28
2.8. Normális hipergráfok .............................................34
2.9. Halmazrendszerek Erdős-Pósa tulajdonsága .......................41
3. Halmazrendszerek színezése ................................................45
3.1. Alapfogalmak ....................................................45
3.2 Uniform halmazrendszerek 2-színezhetősége.......................46
4. Halmazrendszerek Vapnyik-Cservonyenkisz-dimenziója........................55
4.1. Alapfogalmak ....................................................55
4.2. Az alaptétel ......................................................56
4.3. Végtelen halmazrendszerek és a Vapnyik-Cservonyenkisz-dimenzió...60
4.4. Származtatott halmazrendszerek ..................................61
4.5. A Vapnyik-Cservonyenkisz-dimenzió és a lefogási probléma ......62
5. Halmazrendszerek diszkrepanciája ...........................................67
5.1. Alapfogalmak ....................................................67
5.2. A diszkrepancia becslése az alaphalmaz méretével és a halmazok számával ........69
5.3. A diszkrepancia becslése a maximális fokszámmal..................69
6. Extremális halmazrendszerek....................71
6.1. Halmazrendszerekre vonatkozó extremális kérdések.....................71
6.2. Sperner-tétel ..............72
6.3. Sperner-tulajdonságú részbenrendezett halmazok..............76
6.4. Erdős-Ko-Rado-tétel...........................81
6.5. Extrémális kérdések metszet feltételekkel...................83
6.6. Alkalmazások ...................................88
6.7. Erdős-Rado tétel...........................93
7. A halmazrendszerekkel kapcsolatos problémák egymáshoz való viszonya..........95
7.1. Halmazrendszerekre vonatkozó problémák.......95
7.2. Halmazrendszerek kódolása.....................96
7.3. Relatív nehézség, redukció............97
7.4. Halmazrendszerekkel kapcsolatos problémák redukciói............98
7.5. Az NP problémaosztály, NP-teljesség.............103
7.6. Kiutak a nehezen kezelhető problémák megoldása esetén.................104
8. Blokkrendszerek........................107
8.1. Blokkrendszerek alapfogalmai....................107
8.2. Steiner-rendszerek..................................109
8.3. Steiner-rendszerek elemi geometriai konstrukciói.....................110
8.4. Steiner-rendszerek rekurzív definíciói...........113
8.5. Steiner-rendszerek számelméleti konstrukciói..........116
8.6. Steiner-rendszerek alaptétele.................. ...117
8.7. Feloldható blokkrendszerek..................117
8.8. Hadamard-mátrixok..............................121
8.9. Véges projektív síkok.....................128
8.10. Véges affin síkok ..................................133
8.11. Optimalizálási problémák véges síkokra.......138
8.12. Latinnégyzetek...................................147
8 13. Szimmetrikus blokkrendszerek ......................149
8.14. t-blokkrendszerek...........................154
9. Hibajavító kódok...............157
9.1. A kódoláselmélet alapkérdései...............157
9.2. Alapfogalmak ...........................160
9.3. Kódok és halmazrendszerek, gráfelmélet kapcsolata ..163
9.4. Kódok hatékonysága és hibajavítási paramétere......163
9.5. Lineáris kódok ................168
9.6. Hibafelderítés és hibajavítás lineáris kódok esetén .....171
9.7. Hamming-kódok..........174
9.8. Hadamard-kódok.........................................................175
9.9. Ciklikus kódok.............................175
9.10. Reed-Muller-kódok.......................................177
9.11. Lineáris kódok súlyszámláló polinomja........................178
10. Matroidok................................................................181
10.1. Történeti előzmények............................................181
10.2. Két alappélda és alapfogalmak.........................................187
10.3. További példák..............................................193
10.4. Ekvivalens definíciók......................................197
10.5. Megszorítás...............................................................204
10.6. Kontrakció......................................................205
10.7. Minorok...........................................................208
10.8. Dualizálás...................................................208
10.9. Direkt összeg..........................................................210
10.10. Homomorfizmus......................................................213
10.11. Összeg................................................................214
10.12. Metszet........................................................215
10.13. Minimax tételek....................................................217
10.14. Reprezentációelmélet......................................227
11. Geometriai halmazrendszerek...................................235
11.1. Példák geometriai halmazrendszerekre..........................235
11.2. Konvex geometriák.............................................236
11.3. Lezárási operáció..................................................238
11.4. Hámozási sorozatok.............................................241
11.5. Konvex geometriai alapfogalmak....................................243
11.6. Geometriai optimalizálási problémák konvex geometriákban.......246
11.7. Az Erdős-Szekeres-probléma........................................252
11.8. Greedoidok...........................................................253
11.9. Geometriai halmazrendszerek diszkrepanciája........................254
12. Boole-függvények......................................................259
12.1. Bevezetés.................................................259
12.2. Döntési fák..............................................260
12.3. Alsó becslések a döntési fa bonyolultságára...........................266
12.4. Elágazó programok...............................................269
12.5. Alsó becslések az elágazó program bonyolultságára.........................273
12.6. Kommunikációs bonyolultság..............................................275
12.7. Alsó becslések a kommunikációs bonyolultságra..................282
12.8. Formulák.............................;..............................285
12.9. Alsó becslések a formula bonyolultságára............................294
12.10. Hálózatok...................................................... 304
12.11. Approximációs módszer .........................................308
12.12. Alsó becslések monoton hálózati bonyolultságra................309
13. Szimpliciális komplexusok ................................................. 317
13.1. Alapfogalmak ...................................................317
13.2. Szimpliciális komplexusok kombinatorikus, geometriai és topológiai ekvivalenciája ..................................... 321
13.3. Döntési fák és szimpliciális komplexusok .........................327
13.4. Szimpliciális komplexusok f-vektora .............................335
13.5. Szimpliciális komplexusok f-vektorainak karakterizációja, Katona-Kruskal tétel ....339
13.6. Szimpliciális politop határa......................................344
13.7. Szimpliciális politop határának szép felépítése, h-vektor, Dehn-Sommerville-összefüggések...............................350
13.8. Szimpliciális politop határának f-vektora, felső becslés tétel ......362
13.9. Szimpliciális politop határának f-vektora, alsó becslés tétel ...... 365
13.10. Szimpliciális politop határának f-vektora, karakterizáció ........ 367
Jelölések ....................................................................369
Név- és tárgymutató .........................................................373
Irodalomjegyzék ............................................................. 381

Témakörök