Ehud Friedgut

The most complicated proof ever of Mantel’s theorem, and other applications of representation theory of the symmetric group

Mantel’s theorem is extremal graph theory 101, first lesson. A graph on n vertices, with more edges than any complete bipartite graph on the same set of vertices, must contain a triangle.
A seemingly unrelated topic is Kneser’s graph and the problems it encodes (e.g. the Erdos-Ko-Rado theorem). As in many cases, a key to understanding this graph is its eigenvalues and eigenvectors.
It turns out that these objects can be understood using the irreducible representations of the symmetric group.
In this talk I’ll give a (hopefully gentle) self contained description of the tools that the irreps of S_n offer us to tackle these problems and others.
Joint work with Yuval Filmus, Nathan Lindzey and Yuval Wigderson.