Characterization of the group association scheme of the symmetric group (Q1268385)

Let \(G\) be a finite group. Let \(C_0, C_1,\dots, C_d\) be the conjugacy classes of \(G\). Define relations \(R_i\) (\(i=0,1,\dots,d\)) on \(G\) by \(R_i=\{(x,y):yx^{-1}\in C_i\}\). Then \({\mathcal X}(G)=(G,\{R_i\}_{0 \leq i \leq d})\) is a commutative association scheme of \(G\). Let \(G=S_n\) be the symmetric group of degree \(n\). Let \(\Lambda(n)\) be the set of all partitions of \(n\). For \(\lambda \in \Lambda(n)\) let \(C_{\lambda}=\{x \in S_n: x\) has cycle-shape \(\lambda \}\). Then \(\{(C_{\lambda})\}_{\lambda \in \Lambda(n)}\) are the conjugacy classes of \(G=S_n\). A class \(R_{\lambda}\) of \({\mathcal X}(S_n)\) is that defined by \(C_{\lambda}\). Let us write \(\lambda=(i_1, \dots, i_m)\) for a partition \(\lambda=(1,\dots,1, i_1, \dots, i_m) \in \Lambda(n)\) (\(i_s \geq 2\) for \(1 \leq s \leq m\)). The main result of the paper is the following theorem: Let \({\mathcal X} = (X, \{(R_{\lambda})\}_{\lambda \in \Lambda(n)})\) be an association scheme having intersection numbers identical to those of \({\mathcal X}(S_n)\). Suppose that there exist no four vertices \(x_1, x_2, x_3, x_4 \in X\) satisfying \((x_1, x_2), (x_2, x_3),\) \( (x_3, x_4), (x_4, x_1) \in R_2, (x_1, x_3) \in R_3\) and \((x_2, x_4) \in R_{(2, 2)}\). Then \({\mathcal X}\) is isomorphic to \({\mathcal X}(S_n)\). In a forthcoming paper the authors show that \({\mathcal X}\) does not possess four vertices of the above type if \(n\geq 5\). This result together with the theorem mentioned above implies that the group association scheme \({\mathcal X}(S_n)\) of the symmetric group \(S_n\) of degree \(n\) is characterized by its intersection numbers if \(n \neq 4\).