A characterization of the group association scheme of \(A_n\) (Q1885096)

Let \(G\) be a finite group. Let \(C_0=\{1\},C_2,\dots,C_d\) be the conjugacy classes of \(G\). Define relations \(R_i\) (\(i=0,\dots,d\)) on \(G\) by \(R_i=\{(x,y)\mid yx^{-1}\in C_i\}\). Then \({\mathcal X}(G)=(G,\{R_i\}_ {0\leq i\leq d})\) is a commutative association scheme of \(d\) classes called the group association scheme of \(G\). Let \(\Lambda(n)\) be the set of all partitions of \(n\) (for example, \((3)=(1,2,3)\in \Lambda(n)\)). For \(\lambda=(i_1,\dots,i_m)\in \Lambda(n)\) let \(\varphi(\lambda)=\sum_{s=1} ^m(i_s-1)\) and let \(C_\lambda=\{x\in S_n\mid x\) has the cycle-shape \(\lambda\}\). Define \(R_\lambda^*=\{(x,y)\in S_n\times S_n\mid yx^{-1}\in C_\lambda\}\) and \(\Lambda^e(n)=\{\lambda\in \Lambda(n)\mid \varphi(\lambda)\) is an even integer\}. The principal object of this paper is \(\widetilde{\mathcal X}(A_n)=(A_n,\{R_\lambda^*\cap (A_n\times A_n)\}_{\lambda\in \Lambda^e(n)})\). We denote by \(\Gamma^*\) the relation graph \((A_n,R_{(3)}^*)\) of \(\widetilde{\mathcal X}(A_n)\). For subsets \(Y\) and \(Z\) of \(\Gamma^*\) we denote by \(e(Y,Z)\) the number of edges crossing between \(Y\) and \(Z\). Then \(\Gamma^*\) satisfies the following conditions \((\text{M}_1)-(\text{M}_4)\): \((\text{M}_1)\) The size of any maximal clique is 3 or \(n-1\). \((\text{M}_2)\) For any triangle \(xyz\) in \(\Gamma^*\), there exists a unique maximal clique containing \(xyz\). \((\text{M}_3)\) For any pair of adjacent vertices \(x,y\) in \(\Gamma^*\), there exists a unique element \(M_1\in {\mathcal M}_1\) containing \(x,y\), where \({\mathcal M}_1\) is the set of all maximal cliques of size 3 in \(\Gamma^*\). \((\text{M}_4)\) Let \(M\in {\mathcal M}_1\cup {\mathcal M}_2\), where \({\mathcal M}_2\) is the set of all maximal cliques of size \(n-1\) in \(\Gamma^*\) and let \(y\in \Gamma^*\) with \(M\cap R'_{(2,2)}(y)\neq \varnothing\), where \(R_{(2,2)}'(y)=\{z\in \Gamma^*\mid d(y,z)=2\) and \(| \Gamma^*(y,z)| =8\}\). Then \(e(y,M)\neq 1\). Theorem 1.4. Let \({\mathcal X}=(X,\{R_\lambda\}_{\lambda\in \Lambda^e(n)})\) be an association scheme having the same set of parameters as \(\widetilde{\mathcal X}(A_n)\), and let \(\Gamma\) be the relation graph \((X,R_{(3)})\). In addition, assume that \(\Gamma\) satisfies the conditions \((\text{M}_1)-(\text{M}_4)\). Then \(\mathcal X\) is isomorphic to \(\widetilde{\mathcal X}(A_n)\).