×

zbMATH — the first resource for mathematics

Erdős-Ko-Rado theorems. Algebraic approaches. (English) Zbl 1343.05002
Cambridge Studies in Advanced Mathematics 149. Cambridge: Cambridge University Press (ISBN 978-1-107-12844-6/hbk; 978-1-316-41495-8/ebook). xvi, 335 p. (2016).
The Erdős-Ko-Rado (EKR) theorem is a beautiful result in extremal combinatorics. In its basic form, it states that, for positive integers \(n\) and \(k\) with \(n \geq 2k\), a family \(\mathcal{F}\) of pairwise intersecting \(k\)-element subsets of \(\{1,\dots,n\}\) satisfies \(|\mathcal{F}| \leq \binom{n-1}{k-1}\), and furthermore that equality for \(n>2k\) implies all sets in \(\mathcal{F}\) contain a common element. In alternative language, the EKR theorem concerns the size (and structure) of a largest independent set in the Kneser graph \(K(n,k)\). This viewpoint leads to many possible variations of the basic result, even to regimes quite different from the one above.
This book is a wonderful survey on the EKR theorem and numerous results of a similar theme. As the subtitle suggests, the focus is on algebraic methods, particularly association schemes and algebraic graph theory. Although many other proofs exist for EKR, the algebraic approach is extremely satisfying. First, it helps to make precise the general “theme” common to EKR-style theorems. And, not only does it unify the proof of so many different results, but it also sets up the technology to cast an even wider net and attack other problems. To offer some (admittedly highly anecdotal) evidence for this, I have personally never touched an EKR theorem, and yet this book nicely sets up or supports various “nearby problems” I know, such as permutation codes and graph decompositions.
Chapter 1 nicely summarizes the classical EKR theorem and its early treatment. The next several chapters provide extensive background on algebraic graph theory and association schemes, but very early on (Section 2.5) the bound in the classical EKR theorem is proved using eigenvalues of \(K(n,k)\). This is nicely placed to motivate a more detailed look at the methods. In particular, the structural component of the EKR theorem is proved (using linear algebra) by the end of Chapter 6 and the extension to \(t\)-intersecting families is the focus of Chapter 8.
The variations considered later in the text include intersecting subspaces (the \(q\)-analog of EKR), words, permutations and partitions. These frame Chapters 9, 10, 14 and 15. Some helpful background on representation theory of the symmetric group (needed for permutations) appears in the intervening chapters.
Each chapter concludes with a section of thoughtfully chosen exercises. Opportunities for research are given throughout the text, but there is also a concluding chapter highlighting in detail several key open problems. The above features make this book an excellent resource for graduate or keen undergraduate students (and their supervisors)!

MSC:
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05D05 Extremal set theory
05E30 Association schemes, strongly regular graphs
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI