Combination of Finite Sets: (Dover Books on Mathema 1.4tics)

Coherent treatment provides comprehensive view of basic methods and results of the combinatorial study of finite set systems. The Clements-Lindstrom extension of the Kruskal-Katona theorem to multisets is explored, as is the Greene-Kleitman result concerning k-saturated chain partitions of general partially ordered sets. Connections with Dilworth's theorem, the marriage problem, and probability are also discussed. Each chapter ends with a helpful series of exercises and outline solutions appear at the end. ""An excellent text for a topics course in discrete mathematics."" - Bulletin of the American Mathematical Society.

Table of Contents:
Notation 1. Introduction and Sperner's theorem 1.1 A simple intersection result 1.2 Sperner's theorem 1.3 A theorem of Bollobas Exercises 1 2. Normalized matchings and rank numbers 2.1 Sperner's proof 2.2 Systems of distinct representatives 2.3 LYM inequalities and the normalized matching property 2.4 Rank numbers: some examples Exercises 2 3. Symmetric chains 3.1 Symmetric chain decompositions 3.2 Dilworth's theorem 3.3 Symmetric chains for sets 3.4 Applications 3.5 Nested Chains 3.6 Posets with symmetric chain decompositions Exercises 3 4. Rank numbers for multisets 4.1 Unimodality and log concavity 4.2 The normalized matching property 4.3 The largest size of a rank number Exercises 4 5. Intersecting systems and the Erdos-Ko-Rado theorem 5.1 The EKR theorem 5.2 Generalizations of EKR 5.3 Intersecting antichains with large members 5.4 A probability application of EKR 5.5 Theorems of Milner and Katona 5.6 Some results related to the EKR theorem Exercises 5 6. Ideals and a lemma of Kleitman 6.1 Kleitman's lemma 6.2 The Ahlswede-Daykin inequality 6.3 Applications of the FKG inequality to probability theory 6.4 Chvatal's conjecture Exercises 6 7. The Kruskal-Katona theorem 7.1 Order relations on subsets 7.2 The l-binomial representation of a number 7.3 The Kruskal-Katona theorem 7.4 Some easy consequences of Kruskal-Katona 7.5 Compression Exercises 7 8. Antichains 8.1 Squashed antichains 8.2 Using squashed antichains 8.3 Parameters of intersecting antichains Exercises 8 9. The generalized Macaulay theorem for multisets 9.1 The theorem of Clements and Lindstrom 9.2 Some corollaries 9.3 A minimization problem in coding theory 9.4 Uniqueness of a maximum-sized antichains in multisets Exercises 9 10. Theorems for multisets 10.1 Intersecting families 10.2 Antichains in multisets 10.3 Intersecting antichains Exercises 10 11. The Littlewood-Offord problem 11.1 Early results 11.2 M-part Sperner theorems 11.3 Littlewood-Offord results Exercises 11 12. Miscellaneous methods 12.1 The duality theorem of linear programming 12.2 Graph-theoretic methods 12.3 Using network flow Exercises 12 13. Lattices of antichains and saturated chain partitions 13.1 Antichains 13.2 Maximum-sized antichains 13.3 Saturated chain partitions 13.4 The lattice of k-unions Exercises 13 Hints and solutions; References; Index