On cocliques in commutative Schurian association schemes of the symmetric group

Abstract

Given the symmetric group $G=\mathrm{Sym}(n)$ and a multiplicity-free subgroup $H\le G$, the orbitals of the action of $G$ on $G/H$ by left multiplication induce a commutative association scheme. The irreducible constituents of the permutation character of $G$ acting on $G/H$ are indexed by partitions of $n$ and if $\lambda ⊢n$ is the second largest partition in dominance ordering among these, then the Young subgroup $\mathrm{Sym}(\lambda )$ admits two orbits in its action on $G/H$, which are ${\mathcal{S}}_{\lambda }$ and its complement. In their monograph [Erdős-Ko-Rado theorems: Algebraic Approaches. {\it Cambridge University Press}, 2016] (Problem~16.13.1), Godsil and Meagher asked whether ${\mathcal{S}}_{\lambda }$ is a coclique of a graph in the commutative association scheme arising from the action of $G$ on $G/H$. If such a graph exists, then they also asked whether its smallest eigenvalue is afforded by the $\lambda$-module. In this paper, we initiate the study of this question by taking $\lambda =[n-1,1]$. We show that the answer to this question is affirmative for the pair of groups $\left(G,H\right)$, where $G=\mathrm{Sym}(2k+1)$ and $H=\mathrm{Sym}(2)\wr \mathrm{Sym}(k)$, or $G=\mathrm{Sym}(n)$ and $H$ is one of $\mathrm{Alt}(k)\times \mathrm{Sym}(n-k),\mathrm{Alt}(k)\times \mathrm{Alt}(n-k)$, or $\left(\mathrm{Alt}(k)\times \mathrm{Alt}(n-k)\right)\cap \mathrm{Alt}(n)$. For the pair $(G,H)=\left(\mathrm{Sym}(2k),\mathrm{Sym}(k)\wr \mathrm{Sym}(2)\right)$, we also prove that the answer to this question of Godsil and Meagher is negative.