14 - Permutations

Summary

We have seen many EKR-type theorems for objects other than sets. In Chapter 9 we gave a version of the EKR Theorem for vector spaces; in Chapter 10 we proved an EKR-type theorem for integer sequences. In this chapter we consider how an EKR-type theorem can be established for permutations.

To start, we recall from Section 7.5 our definition of intersection for permutations: two permutations π, σ? Sym(n) are said to be intersectingif π(i) = σ(i) for some i∈ ﹛1 , …, n﹜. Such permutations are also said to agreeon the point i. For an integer t≥ 1, a pair of permutations from Sym(n) are said to be t-intersectingif they agree on at least tpoints from ﹛1 , …, n﹜. A set of permutations is called intersecting (or t-intersecting) if any two permutations in the set are intersecting (or t-intersecting).

An example of a set of intersecting permutations is the set of all permutations in Sym(n) that fix some point i(this is the stabilizerof the point i). The stabilizer of a point is a set of intersecting permutations of size (n- 1)!. Similarly, the pointwise stabilizer of any tdistinct elements is a set of t-intersecting permutations with size (n- t)!. Further, any coset of these groups is also a set of t-intersecting permutations of size (n- t)!.

One generalization (perhaps the most natural) of the EKR Theorem for permutations is the assertion that the largest set of intersecting permutations has size (n - 1)!, and the only sets that meet this bound are the cosets of point stabilizers. Cameron and Ku [40] and Larose and Malvenuto [113] independently proved this result in 2006. Since then other proofs of this result have appeared (see [168, Section 2] for a particularly simple proof).

In this chapter we present a proof that uses the ratio bound for cocliques, and an analysis of the corresponding eigenspaces. This is the proof given in [85]. We will consider extending this result to sets of t-intersecting permutations.We will also look at the largest subsets of intersecting permutations from subgroups of the symmetric group.