Characterizations of Amorphic Schemes and Fusions of Pairs

NEW

Problem: For a finite symmetric association scheme $\mathcal R=\{A_0=I,A_1,\dots,A_d\}$, define the fusing-relations graph $\Gamma_A(\mathcal R)$ on $[d]$ by joining $i,j$ iff the fusion replacing $A_i,A_j$ by $A_i+A_j$ is an association scheme. Dually define $\Gamma_E(\mathcal R)$ on nontrivial primitive idempotents $E_1,\dots,E_d$ by joining $r,s$ iff fusing $E_r,E_s$ gives a fusion scheme.

The reconstructed question is: must every connected component of $\Gamma_A(\mathcal R)$ and of $\Gamma_E(\mathcal R)$ be either a path or a clique? This is supported by the paper’s final remark referring to “the fusing-relations graph and fusing-idempotents graph” and asking about “the connected components of these graphs.”

Result: Yes.

Let $P=(P_{ri})$ be the first eigenmatrix, $k_i=P_{0i}$, and write $p_r$ for row $r$. By the Bannai-Muzychuk criterion, if relation pair $\{i,j\}$ fuses and corresponds to idempotent pair $\{r,s\}$, then

for some $\alpha\ne0$, after orienting the pairs. Conversely, such a row difference implies that $\{i,j\}$ fuses.

Use row orthogonality

If $\{i,j\}\leftrightarrow\{r,s\}$, then for every $t\notin\{r,s\}$,

so $P_{ti}/k_i=P_{tj}/k_j$. Hence two relation-edges sharing a vertex must correspond to two idempotent-edges sharing a vertex; otherwise this equality would force the relevant row difference to vanish. The same argument with the second eigenmatrix $Q$ gives the converse incidence preservation.

Now let $C$ be a connected component of $\Gamma_A$.

If some vertex $x\in C$ has degree at least $3$, take three edges $xy,xz,xw$. Their corresponding idempotent-edges are pairwise incident. They cannot form a triangle, since then one row difference would be a linear combination of two others and would have support in three relation-coordinates, not exactly $\{x,w\}$. Thus all edges incident with $x$ correspond to row-edges sharing a common row $r$. Write

for each neighbor $y$ of $x$. For distinct neighbors $y,z$,

while the left side also equals $\alpha_y\alpha_z/k_x$. Since $x$ has at least three neighbors, all $\alpha_y$ are equal. Therefore

so $y,z$ fuse. Thus the neighbors of $x$ form a clique. Propagating along paths from $x$, every vertex of $C$ is adjacent to $x$, and then all vertices of $C$ are mutually adjacent. Hence $C$ is a clique.

If no vertex has degree at least $3$, then a connected component is either a path or a cycle. A $3$-cycle is a clique. For a cycle $1,2,\dots,n,1$ with $n\ge4$, incidence preservation gives corresponding idempotent vertices $r_1,\dots,r_n$ such that

Summing around the cycle gives $0=\sum_i\alpha_i(e_i-e_{i+1})$, hence all $\alpha_i$ are equal. Then for any $a,b$,

so every pair $a,b$ fuses. Thus the cycle component is actually a clique.

Therefore every connected component of $\Gamma_A(\mathcal R)$ is a path or a clique. Applying the same proof to $Q$, with relations and idempotents interchanged, gives the same conclusion for $\Gamma_E(\mathcal R)$.

Verification audit: the proof uses only the standard hypotheses of a finite symmetric association scheme, the Bannai-Muzychuk fusion criterion, and eigenmatrix orthogonality. Singleton components count as both $P_1$ and $K_1$, and $K_2=P_2$, so all degenerate cases are covered.

Citation: Problem source: E. R. van Dam, J. H. Koolen, Y. Xiong, “Characterizations of amorphic schemes and fusions of pairs,” arXiv:2404.00567v3, Final remarks and problems. Standard tool used: Bannai-Muzychuk fusion criterion.