You are here

Extremal Problems for Finite Sets

Peter Frankl and Norihide Tokushige
American Mathematical Society
Publication Date: 
Number of Pages: 
Student Mathematical Library 86
BLL Rating: 

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

[Reviewed by
Mark Hunacek
, on

A year ago, I taught a one-semester undergraduate course in combinatorics, and, as one does, spent some time discussing the Pigeonhole Principle and some of its applications. Among the results I mentioned was this one: “if \(\mathcal F\) is a collection of subsets of an \(n\)-element set \(X\), and if any two elements of \(\mathcal F\) intersect nontrivially, then \(\mathcal F\) contains at most \(2^{n-1}\) sets.”

This is an easy result to prove (just pair off every subset of \(X\) with its complement), but it belongs to a class of problems many of which are very much more difficult. For example, if we add to the assumptions of the previous statement the requirement that the sets in \(\mathcal F\) all have cardinality \(k\) (with \(2k\leq n\)), then it can be shown that the number of elements in \(\mathcal F\) is less than or equal to the binomial coefficient \(\binom{n-1}{k-1}\). This is the Erdős-Ko-Rado theorem, several proofs of which are given in this book.

The book under review is filled with results of this general type, in which bounds for the size of a family of subsets of a given finite set are established under the assumption that the family of subsets satisfies certain conditions. Various applications of some of these results to areas like finite geometry are also explored.

The prerequisites for reading this book are never explicitly stated, but it seems clear that, although the book is evidently intended for undergraduates, a pretty strong background in mathematics is assumed. For example, the authors use the term “hypergraph” on page 1 and the term “metric space” on page 5, without definitions. Ideas from linear algebra are also used freely in the text.

While there was an occasional result that I was familiar with (the book commences, for example, with Sperner’s theorem, on the maximum possible size of an antichain of subsets of an \(n\)-element set), most of the results in this book struck me as fairly technical and (based on my own experience, anyway) not likely well-known to non-specialists in the area. The back of the book blurb tells us that some of the proofs appearing in the text are new. Some of the results are also quite modern.

This book is the latest entry in the Student Mathematical Library series, which is intended, according to the AMS webpage, to “spark students’ interests in modern mathematics and increase their appreciation for research.” This book succeeds in that goal: it makes cutting-edge results reasonably accessible to undergraduates. The book ends with a discussion of challenging open problems in the area, and contains an extensive bibliography. Consistent with its desire to foster research, the bibliography contains almost no textbooks; all but one or two of the 114 entries are papers.

In this regard, the book struck me as having a somewhat different feel to it than do other recent additions to this series such as Volterra Adventures, A Conversational Introduction to Algebraic Number Theory, or Game Theory: A Playful Introduction. These books all have a casual, conversational tone to them and could be recommended for a senior course to most graduating mathematics majors. This book, by contrast, struck me, as noted earlier, as somewhat more technical, and therefore of less general interest; I would recommend it primarily to students who have a strong existing interest in combinatorics and who aspire to do research in this subject.

Although the optimal audience for this text is perhaps narrow, the members of that audience will likely find this book to be very valuable. The authors do take pains to make the material accessible, and I am not aware of any other source for this material that allows well-prepared undergraduates to get up to speed in this area of mathematics.


Buy Now

Mark Hunacek ([email protected]) teaches mathematics at Iowa State University.