Intersection Problems in Extremal Combinatorics: Theorems, Techniques and Questions Old and New

DOI10.1017/9781009093927.005arXiv2107.06371MaRDI QIDQ6143998

Author name not available (Why is that?)

Publication date: 5 January 2024

Published in: Surveys in Combinatorics 2022 (Search for Journal in Brave)

Abstract: The study of intersection problems in Extremal Combinatorics dates back perhaps to 1938, when Paul ErdH{o}s, Chao Ko and Richard Rado proved the (first) `ErdH{o}s-Ko-Rado theorem' on the maximum possible size of an intersecting family of

k

-element subsets of a finite set. Since then, a plethora of results of a similar flavour have been proved, for a range of different mathematical structures, using a wide variety of different methods. Structures studied in this context have included families of vector subspaces, families of graphs, subsets of finite groups with given group actions, and of course uniform hypergraphs with stronger or weaker intersection conditions imposed. The methods used have included purely combinatorial ones such as shifting/compressions, algebraic methods (including linear-algebraic, Fourier analytic and representation-theoretic), and more recently, analytic, probabilistic and regularity-type methods. As well as being natural problems in their own right, intersection problems have connections with many other parts of Combinatorics and with Theoretical Computer Science (and indeed with many other parts of Mathematics), both through the results themselves, and the methods used. In this survey paper, we discuss both old and new results (and both old and new methods), in the field of intersection problems. Many interesting open problems remain; we will discuss several. For expositional and pedagogical purposes, we also take this opportunity to give slightly streamlined versions of proofs (due to others) of several classical results in the area. This survey is intended to be useful to PhD students, as well as to more established researchers. It is a personal perspective on the field, and is not intended to be exhaustive; we apologise for any omissions. It is an expanded version of a paper that will appear in the Proceedings of the 29th British Combinatorial Conference.

Full work available at URL: https://arxiv.org/abs/2107.06371

zbMATH Keywords

maximum possible size of a uniform intersecting family with transitive automorphism group symmetric intersecting subfamily

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Extremal set theory (05D05)