You are here

Combinatorics of Finite Sets

Ian Anderson
Publisher: 
Dover Publications
Publication Date: 
2002
Number of Pages: 
272
Format: 
Paperback
Price: 
19.95
ISBN: 
9780486422572
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
John T. Saccoman
, on
04/1/2017
]

In the preface to the first edition of his book, Ian Anderson wrote in 1985,” The past quarter century has seen the remarkable rise of combinatorics as a distinctive and important area of mathematics.” It is no less true after more than a quarter century.

His book, as much a set theory book as one on combinatorics, is something of a throwback. While virtually every combinatorics text strives to include copious applications, Anderson’s main focus is the theory. For example, an overarching theme of the text is Sperner’s theorem (in various contexts) and its generalizations. Sperner’s Theorem, as you may recall, is concerned with the cardinality of a collection of subsets of a certain size with the property that no members of the collection are subsets of each other.

Anderson presents several proofs of Sperner’s Theorem, as well as applications of it. For example, he demonstrates its importance in the development of the notion of partially ordered sets. This then leads to a rather elegant treatment of posets and Stirling numbers. In addition, Anderson develops a probabilistic version of the theorem.

While applications are not the main focus, they are nonetheless covered. In the thirteen chapters of the text, Anderson treats such important combinatorial theorems as Erdős-Ko-Rado and Kruskal-Katona, while also including multisets, lattices, and even some coverage of simplicial complexes, graph theory, and networks as posets. Obviously, a background in abstract algebra as well as discrete mathematics is necessary for a true appreciation of this text.

There are numerous exercises, with hints and solutions for many of them included. The development of the main ideas utilizes first principles. That, coupled with the presentation of alternate proofs of Sperner’s and other theorems, make it ideal for discussing the aesthetic of proof. This text is excellent for advanced undergraduates and beginning graduate students. 


John T. Saccoman is Professor of Mathematics at Seton Hall University in South Orange, NJ.

 

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