Extremal Problems for Finite Sets (Student Mathematical Library)

Description

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. 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