On Tuesday Ehud Friedgut gave a beautiful talk in the Bristol Combinatorics Seminar, titled ‘The most complicated proof ever of Mantel’s theorem, and other applications of the representation theory of the symmetric group’, based on joint work with Yuval Filmus, Nathan Lindzey and Yuval Wigderson. As the title promised, he used the representation theory of the symmetric group to prove Mantel’s Theorem, that if a graph on vertices has more edges than the complete bipartite graph with bipartition into two parts of size then it contains a triangle. He illustrated the method by instead proving the Erdős–Ko–Rado Theorem, that the maximum size of a family of -subsets of such that any two members of the family have a non-trivial intersection is . The purpose of this post is to outline the new proof (as I understand it from Ehud’s talk) of this result, dropping in my own proof of one of the lemmas he used. At the end I’ll record a possible generalization/variation I raised at the end of the talk. Let me emphasise that — apart from the minor proof of the lemma, which in any case uses results of James — no originality is claimed for anything in this post.

### A graph for the Erdős–Ko–Rado Theorem

The graph we need to prove the Erdős–Ko–Rado Theorem is the Kneser graph, having as its vertices the -subsets of . Two subsets and are connected by an edge if and only if . The Erdős–Ko–Rado Theorem is then the claim that the maximum size of an independent set in is . As we shall see below, this follows from the Hoffman bound, that an independent set in a -regular graph on vertices with adjacent matrix and least eigenvalue has size at most . (Note that since the sum of the eigenvalues is the trace of the adjacency matrix, namely , and the largest eigenvalue is the degree , the least eigenvalue is certainly negative.)

### Representations

To find the eigenvalues of , Ehud and his coauthors use the representation theory of the symmetric group. Let be the permutation module of acting on the -subsets of . It is well known that has character

Since this character is multiplicity-free, there is a unique direct sum decomposition of into Specht modules,

The adjacent matrix acts as a linear map on that commutes with the -action. Therefore, by Schur’s Lemma, for each with there is a scalar such that acts on as multiplication by . Thus the are the eigenvalues (possibly with repetition, but this turns out not to be the case) of .

**Lemma.** The adjacency matrix acts on by scalar multiplication by .

*Proof.* It follows from the theory in Chapter 17 of James’ Springer lecture notes on the symmetric groups that has a filtration

such that and for . The submodule is spanned by certain ‘partially symmetrized’ polytabloids. Rather than introduce this notation, which is a bit awkward for a blog post, let me instead suppose that acts on the set where . Let be a fixed -subset of . Then is a cyclic -module generated (using right modules) by where

There is a ‘raising map’ which — viewing as a submodule of the permutation module of acting on -subsets — is defined on the generator by

Applying the adjacency matrix sends an -subset to all those -subsets that it does not meet. Hence if we first apply then to then, in order to get a scalar multiple of , we must pick an -subset not meeting that contains , i.e. an -subset of the form

where is an -subset of . Since , there are possible choices. Each comes with sign .

### End of proof

The lemma implies that is the least eigenvalue of . Putting this into Hoffman’s bound and using that the graph is regular of degree , since this is the number of -subsets of not meeting , we get that the maximum size of an independent set is at most

which is just a shade more than . Thus we (or rather Ehud and his coauthors) have proved the Erdős–Ko–Rado Theorem for sufficiently large. Ehud mentioned that it was legitimate to apply the Hoffman bound to a scaled adjacency matrix, and by choosing a clever scaling, one could get the theorem on the nose. He then went on to outline how the method applies to Mantel’s Theorem: the relevant representation is, in the usual notation, ; note one may interpret an -tabloid as an ordered pair encoding the path of length 3 with edges and . There is a proof of Mantel’s Theorem by double counting using these paths: as Ehud remarked (quoting, if I heard him right, Kalai) ‘It’s very hard not to prove Mantel’s Theorem’.

### Possible variations

I’ll end with two possible avenues for generalization, both motivated by the classification of multiplicity-free permutation characters of symmetric groups. My paper built on work of Saxl and was published at about the same time as parallel work of Godsil and Meagher.

#### Foulkes module

The symmetric group acts on the set of set partitions of into sets each of size . The corresponding permutation character is multiplicity free: it has the attractive decomposition , where is the partition obtained from by doubling the length of each path. Moreover, my collaborator Rowena Paget has given an explicit Specht filtration of the corresponding permutation module, analogous to the filtration used above of . So everything is in place to prove a version of the Erdős–Ko–Rado Theorem for perfect matchings.

#### Finite general linear groups

There is a remarkably close connection between the representations of and the unipotent representations of the finite general linear group , which perhaps will, one day, be explained by defining the symmetric group as a group of automorphisms of a vector space over the field with one element. Coming down to earth, the analogue of the permutation module of acting on -subsets is the permutation module of acting on -subspaces of . This decomposes as a direct sum of irreducible submodules exactly as in above, replacing the Specht modules with their -analogues. So once again the decomposition is multiplicity-free. This suggests there might be a linear analogue of the Erdős–Ko–Rado Theorem in which we aim to maximize the size of a family of subspaces of such that any two subspaces have at least a -dimensional intersection.

#### A Putnam problem

The second suggested generalization might tie in with another project I’ve worked on but neglected to write up beyond a blog post: to prove the -analogue of the spectral results on the Kneser graph motivated by Problem A2 in the 2018 Putnam.