Acknowledgement |
|
ix | |
Preface |
|
xi | |
Notation and Definitions |
|
xiii | |
|
|
1 | (28) |
|
1.1 Sperner's theorem, LYM-inequality, Bollobas inequality |
|
|
1 | (4) |
|
1.2 The Erdos-Ko-Rado theorem - several proofs |
|
|
5 | (7) |
|
1.3 Intersecting Sperner families |
|
|
12 | (4) |
|
1.4 Isoperimetric inequalities: the Kruskal-Katona theorem and Harper's theorem |
|
|
16 | (8) |
|
|
24 | (5) |
|
|
29 | (56) |
|
2.1 Stability of the Erdos-Ko-Rado theorem |
|
|
29 | (6) |
|
2.2 t-intersecting families |
|
|
35 | (8) |
|
2.3 Above the Erdos-Ko-Rado threshold |
|
|
43 | (12) |
|
2.3.1 Erdos's matching conjecture |
|
|
43 | (4) |
|
2.3.2 Supersaturation - minimum number of disjoint pairs |
|
|
47 | (6) |
|
2.3.3 Most probably intersecting families |
|
|
53 | (1) |
|
2.3.4 Almost intersecting families |
|
|
54 | (1) |
|
2.4 L-intersecting families |
|
|
55 | (4) |
|
2.5 r-wise intersecting families |
|
|
59 | (5) |
|
2.6 k-uniform intersecting families with covering number k |
|
|
64 | (8) |
|
2.7 The number of intersecting families |
|
|
72 | (4) |
|
2.8 Cross-intersecting families |
|
|
76 | (9) |
|
2.8.1 The sum of the sizes of cross-intersecting families |
|
|
76 | (5) |
|
2.8.2 The product of the sizes of cross-intersecting families |
|
|
81 | (4) |
|
|
85 | (30) |
|
3.1 More-part Sperner families |
|
|
85 | (8) |
|
|
93 | (4) |
|
3.3 The number of antichains in 2[ n] (Dedekind's problem) |
|
|
97 | (5) |
|
3.4 Union-free families and related problems |
|
|
102 | (4) |
|
3.5 Union-closed families |
|
|
106 | (9) |
|
4 Random versions of Sperner's theorem and the Erdos-Ko-Rado theorem |
|
|
115 | (24) |
|
4.1 The largest antichain in Qn(p) |
|
|
116 | (7) |
|
4.2 Largest intersecting families in Qn,k(p) |
|
|
123 | (3) |
|
4.3 Removing edges from Kn(n, k) |
|
|
126 | (2) |
|
4.4 G-intersecting families |
|
|
128 | (5) |
|
4.5 A random process generating intersecting families |
|
|
133 | (6) |
|
|
139 | (56) |
|
5.1 Complete forbidden hypergraphs and local sparsity |
|
|
142 | (5) |
|
5.2 Graph-based forbidden hypergraphs |
|
|
147 | (26) |
|
|
148 | (7) |
|
|
155 | (7) |
|
5.2.3 Minimal Berge hypergraphs |
|
|
162 | (1) |
|
|
162 | (4) |
|
|
166 | (3) |
|
5.2.6 Other graph-based hypergraphs |
|
|
169 | (4) |
|
5.3 Hypergraph-based forbidden hypergraphs |
|
|
173 | (5) |
|
5.3.1 Extensions and Lagrangians of hypergraphs |
|
|
175 | (3) |
|
5.4 Other forbidden hypergraphs |
|
|
178 | (3) |
|
|
181 | (9) |
|
|
181 | (1) |
|
|
182 | (5) |
|
5.5.3 Hypergraph regularity |
|
|
187 | (2) |
|
|
189 | (1) |
|
5.6 Non-uniform Turan problems |
|
|
190 | (5) |
|
|
195 | (16) |
|
6.1 Saturated hypergraphs and weak saturation |
|
|
196 | (5) |
|
6.2 Saturating k-Sperner families and related problems |
|
|
201 | (10) |
|
7 Forbidden subposet problems |
|
|
211 | (38) |
|
7.1 Chain partitioning and other methods |
|
|
213 | (7) |
|
7.2 General bounds on La(n, P) involving the height of P |
|
|
220 | (4) |
|
|
224 | (1) |
|
7.4 Induced forbidden subposet problems |
|
|
225 | (5) |
|
7.5 Other variants of the problem |
|
|
230 | (3) |
|
7.6 Counting other subposets |
|
|
233 | (16) |
|
|
249 | (26) |
|
8.1 Characterizing the case of equality in the Sauer Lemma |
|
|
250 | (3) |
|
|
253 | (4) |
|
8.3 Forbidden subconfigurations |
|
|
257 | (7) |
|
|
264 | (11) |
|
9 Combinatorial search theory |
|
|
275 | (20) |
|
|
275 | (7) |
|
9.2 Searching with small query sets |
|
|
282 | (2) |
|
|
284 | (2) |
|
|
286 | (2) |
|
9.5 Between adaptive and non-adaptive algorithms |
|
|
288 | (7) |
Bibliography |
|
295 | (38) |
Index |
|
333 | |