Extremal finite set theory

Cover......Page 1
Half Title......Page 2
Title Page......Page 4
Copyright Page......Page 5
Table of Contents......Page 6
Acknowledgement......Page 10
Preface......Page 12
Notation and Definitions......Page 14
 1.1 Sperner’s theorem, LYM-inequality, Bollobás inequality......Page 18
 1.2 The Erdős-Ko-Rado theorem - several proofs......Page 22
 1.3 Intersecting Sperner families......Page 29
 1.4 Isoperimetric inequalities: the Kruskal-Katona theorem and Harper’s theorem......Page 33
 1.5 Sunflowers......Page 41
 2.1 Stability of the Erdős-Ko-Rado theorem......Page 46
 2.2 t-intersecting families......Page 52
  2.3.1 Erdős’s matching conjecture......Page 60
  2.3.2 Supersaturation - minimum number of disjoint pairs......Page 64
  2.3.3 Most probably intersecting families......Page 70
  2.3.4 Almost intersecting families......Page 71
 2.4 L-intersecting families......Page 72
 2.5 r-wise intersecting families......Page 76
 2.6 k-uniform intersecting families with covering number k......Page 81
 2.7 The number of intersecting families......Page 89
  2.8.1 The sum of the sizes of cross-intersecting families......Page 93
  2.8.2 The product of the sizes of cross-intersecting families......Page 98
 3.1 More-part Sperner families......Page 102
 3.2 Supersaturation......Page 110
 3.3 The number of antichains in 2[n] (Dedekind’s problem)......Page 114
 3.4 Union-free families and related problems......Page 119
 3.5 Union-closed families......Page 123
4: Random versions of Sperner’s theorem and the Erdős-Ko-Rado theorem......Page 132
 4.1 The largest antichain in Qn(p)......Page 133
 4.2 Largest intersecting families in Qn,k(p)......Page 140
 4.3 Removing edges from Kn(n, k)......Page 143
 4.4 G-intersecting families......Page 145
 4.5 A random process generating intersecting families......Page 150
5: Turán-type problems......Page 156
 5.1 Complete forbidden hypergraphs and local sparsity......Page 159
 5.2 Graph-based forbidden hypergraphs......Page 164
  5.2.1 Expansions......Page 165
  5.2.2 Berge hypergraphs......Page 172
  5.2.4 Inflated graphs......Page 179
  5.2.5 Suspensions......Page 183
  5.2.6 Other graph-based hypergraphs......Page 186
 5.3 Hypergraph-based forbidden hypergraphs......Page 190
  5.3.1 Extensions and Lagrangians of hypergraphs......Page 192
 5.4 Other forbidden hypergraphs......Page 195
  5.5.1 Supersaturation......Page 198
  5.5.2 Flag algebras......Page 199
  5.5.3 Hypergraph regularity......Page 204
  5.5.4 Spectral methods......Page 206
 5.6 Non-uniform Turán problems......Page 207
6: Saturation problems......Page 212
 6.1 Saturated hypergraphs and weak saturation......Page 213
 6.2 Saturating k-Sperner families and related problems......Page 218
7: Forbidden subposet problems......Page 228
 7.1 Chain partitioning and other methods......Page 230
 7.2 General bounds on La(n, P) involving the height of P......Page 237
 7.3 Supersaturation......Page 241
 7.4 Induced forbidden subposet problems......Page 242
 7.5 Other variants of the problem......Page 247
 7.6 Counting other subposets......Page 250
8: Traces of sets......Page 266
 8.1 Characterizing the case of equality in the Sauer Lemma......Page 267
 8.2 The arrow relation......Page 270
 8.3 Forbidden subconfigurations......Page 274
 8.4 Uniform versions......Page 281
 9.1 Basics......Page 292
 9.2 Searching with small query sets......Page 299
 9.3 Parity search......Page 301
 9.4 Searching with lies......Page 303
 9.5 Between adaptive and non-adaptive algorithms......Page 305
Bibliography......Page 312
Index......Page 350