Combinatorics of Finite Sets (eBook)

Ian Anderson (Autor)

eBook Download: EPUB

2012
272 Seiten
Dover Publications (Verlag)
9780486143712 (ISBN)

Infos

Among other subjects explored are the Clements-Lindström extension of the Kruskal-Katona theorem to multisets and the Greene-Kleitmen result concerning k-saturated chain partitions of general partially ordered sets. Includes exercises and solutions.

---

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. "e;An excellent text for a topics course in discrete mathematics."e; — Bulletin of the American Mathematical Society.

Inhalt

Notation1. Introduction and Sperner's theorem 1.1 A simple intersection result 1.2 Sperner's theorem 1.3 A theorem of Bollobás Exercises 12. 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 23. 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 34. 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 45. Intersecting systems and the Erdös-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 56. 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 Chvátal's conjecture Exercises 67. 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 78. Antichains 8.1 Squashed antichains 8.2 Using squashed antichains 8.3 Parameters of intersecting antichains Exercises 89. The generalized Macaulay theorem for multisets 9.1 The theorem of Clements and Lindström 9.2 Some corollaries 9.3 A minimization problem in coding theory 9.4 Uniqueness of a maximum-sized antichains in multisets Exercises 910. Theorems for multisets 10.1 Intersecting families 10.2 Antichains in multisets 10.3 Intersecting antichains Exercises 1011. The Littlewood-Offord problem 11.1 Early results 11.2 M-part Sperner theorems 11.3 Littlewood-Offord results Exercises 1112. Miscellaneous methods 12.1 The duality theorem of linear programming 12.2 Graph-theoretic methods 12.3 Using network flow Exercises 1213. 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

Produkt-Details

• Erscheint lt. Verlag: 30.4.2012
• Reihe/Serie: Dover Books on Mathematics
• Reihe/Serie: Dover Books on Mathematics
• Sprache: englisch
• Maße: 140 x 140 mm
• Themenwelt: Mathematik / Informatik ► Mathematik
• Schlagworte: advanced mathematics • advanced undergraduate • Antichains in mathematics • applied science and math • binomial coefficients • clements lindstrom • college level studies • combinatorial study • Combinatorics of finite sets • dilworth theorem • Discrete Mathematics • exercises and solutions • finite sets • general partially ordered sets • Geometric probability • Graduate level • greene kleitman • kruskal katona theorem • k saturated chain partitions • Multisets • Probability • Symmetric chains • the marriage problem
• ISBN-13: 9780486143712 / 9780486143712