Extremal Problems For Finite Sets

Extremal Problems For Finite Sets is a mathematics book on the extremal combinatorics of finite sets and families of finite sets. It was written by Péter Frankl and Norihide Tokushige, and published in 2018 by the American Mathematical Society as volume 86 of their Student Mathematical Library book series. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

First edition

Topics

The book has 32 chapters. Its topics include:

• Sperner's theorem, on the largest antichain in the family of subsets of a given finite set.
• The Sauer–Shelah lemma, on the largest size of a family of sets that avoids shattering any set of given size.
• The Erdős–Ko–Rado theorem, on the largest pairwise-intersecting family of subsets of a given finite set, with multiple proofs; the closely related Lubell–Yamamoto–Meshalkin inequality; the Hilton-Milner theorem, on the largest intersecting family with no element in common; and a conjecture of Václav Chvátal that the largest intersecting family of any downward-closed family of sets is always achieved by a family with an element in common.
• The Kruskal–Katona theorem relating the size of a family of equal-sized sets and the size of the family of subsets of its sets of a smaller equal size.
• Cap sets and the sunflower conjecture on families of sets with equal pairwise intersection.
• Open problems including Frankl's union-closed sets conjecture.

Many other results in this area are also included.

Audience and reception

Although the book is intended for undergraduate mathematics students, reviewer Mark Hunacek suggests that readers will either need to be familiar with, or comfortable looking up, terminology for hypergraphs and metric spaces. He suggests that the appropriate audience for the book would be advanced undergraduates who have already demonstrated an interest in combinatorics. However, despite the narrowness of this group, he writes that the book will likely be very valuable to them, as the only source for this material that is written at an undergraduate level.