Event № 329
Erdős-Ko-Rado type problems' have been widely studied in Combinatorics and Theoretical Computer Science over the last fifty years. In general, these ask for the maximum possible size of a family of objects, subject to the constraint that any two (or three…) of the objects `intersect' or `agree' in some way. A classical example is the so-called Erdős-Ko-Rado theorem, which gives the maximum possible size of a family of k-element subsets of an n-element set, subject to the constraint that any two sets in the family have nonempty intersection. As well as families of sets, one may consider families of more highly structured objects, such as graphs or permutations; one may also consider what happens when additional `symmetry' requirements are imposed on the families. A surprisingly rich variety of techniques from different areas of mathematics have been used successfully in this area: combinatorial, probabilistic, analytic and algebraic. For example, Fourier analysis and representation theory have recently proved useful. I will discuss some results and open problems in the area, some of the techniques used, and some links with other areas.