Combinatorics of Finite Sets

by Ian Anderson

Overview

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.

Product Details

ISBN-13:	9780486143712
Publisher:	Dover Publications
Publication date:	04/30/2012
Series:	Dover Books on Mathematics
Sold by:	Barnes & Noble
Format:	eBook
Pages:	272
File size:	21 MB
Note:	This product may take a few minutes to download.

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 Bollobás
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 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 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 Chvátal'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 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 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

Editorial Reviews

Anderson (U. of Glasgow) explores collections of subsets of a finite set where the collection is described in terms of intersection, union, or inclusive conditions. He also considers more general partially ordered sets. The 1989 edition, published by University Press, Oxford, has been slightly corrected. Annotation c. Book News, Inc., Portland, OR