Extremal Problems for Finite Sets

Peter Frankl, Norihide Tokushige

• Publisher: American Mathematical Society
• Year: 2018
• Print ISBN:
  9781470440398
• eBook ISBN:
  9781470448479
• Topic: Mathematics
• Subtopic: Discrete Mathematics
• Index: Mathematics

One of the great appeals of Extremal Set Theory as a subject is that the statements are easily accessible without a lot of mathematical background, yet the proofs and ideas have applications in a wide range of fields including combinatorics, number theory, and probability theory. Written by two of the leading researchers in the subject, this book is aimed at mathematically mature undergraduates, and highlights the elegance and power of this field of study.The first half of the book provides classic results with some new proofs including a complete proof of the Ahlswede–Khachatrian theorem as well as some recent progress on the Erd?s matching conjecture. The second half presents some combinatorial structural results and linear algebra methods including the Deza–Erd?s–Frankl theorem, application of Rödl's packing theorem, application of semidefinite programming, and very recent progress (obtained in 2016) on the Erd?s–Szemerédi sunflower conjecture and capset problem. The book concludes with a collection of challenging open problems.

Table of contents

• Cover
• Title page
• Contents
• Notation
• Chapter 1. Introduction
• Chapter 2. Operations on sets and set systems
• Chapter 3. Theorems on traces
• Chapter 4. The Erdős–Ko–Rado Theorem via shifting
• Chapter 5. Katona’s circle
• Chapter 6. The Kruskal–Katona Theorem
• Chapter 7. Kleitman Theorem for no 𝑠 pairwise disjoint sets
• Chapter 8. The Hilton–Milner Theorem
• Chapter 9. The Erdős matching conjecture
• Chapter 10. The Ahlswede–Khachatrian Theorem
• Chapter 11. Pushing-pulling method
• Chapter 12. Uniform measure versus product measure
• Chapter 13. Kleitman’s correlation inequality
• Chapter 14. 𝑟-Cross union families
• Chapter 15. Random walk method
• Chapter 16. 𝐿-systems
• Chapter 17. Exponent of a (10,{0,1,3,6})-system
• Chapter 18. The Deza–Erdős–Frankl Theorem
• Chapter 19. Füredi’s structure theorem
• Chapter 20. Rödl’s packing theorem
• Chapter 21. Upper bounds using multilinear polynomials
• Chapter 22. Application to discrete geometry
• Chapter 23. Upper bounds using inclusion matrices
• Chapter 24. Some algebraic constructions for 𝐿-systems
• Chapter 25. Oddtown and eventown problems
• Chapter 26. Tensor product method
• Chapter 27. The ratio bound
• Chapter 28. Measures of cross independent sets
• Chapter 29. Application of semidefinite programming
• Chapter 30. A cross intersection problem with measures
• Chapter 31. Capsets and sunflowers
• Chapter 32. Challenging open problems
• Bibliography
• Index
• Back Cover