Separability number and Schurity number of coherent configurations

Sergei Evdokimov ; Ilia Ponomarenko

The electronic journal of combinatorics, Tome 7 (2000)

Résumé

To each coherent configuration (scheme) ${\cal C}$ and positive integer $m$ we associate a natural scheme $\widehat{\cal C}^{(m)}$ on the $m$-fold Cartesian product of the point set of ${\cal C}$ having the same automorphism group as ${\cal C}$. Using this construction we define and study two positive integers: the separability number $s({\cal C})$ and the Schurity number $t({\cal C})$ of ${\cal C}$. It turns out that $s({\cal C})\le m$ iff ${\cal C}$ is uniquely determined up to isomorphism by the intersection numbers of the scheme $\widehat{\cal C}^{(m)}$. Similarly, $t({\cal C})\le m$ iff the diagonal subscheme of $\widehat{\cal C}^{(m)}$ is an orbital one. In particular, if ${\cal C}$ is the scheme of a distance-regular graph $\Gamma$, then $s({\cal C})=1$ iff $\Gamma$ is uniquely determined by its parameters whereas $t({\cal C})=1$ iff $\Gamma$ is distance-transitive. We show that if ${\cal C}$ is a Johnson, Hamming or Grassmann scheme, then $s({\cal C})\le 2$ and $t({\cal C})=1$. Moreover, we find the exact values of $s({\cal C})$ and $t({\cal C})$ for the scheme ${\cal C}$ associated with any distance-regular graph having the same parameters as some Johnson or Hamming graph. In particular, $s({\cal C})=t({\cal C})=2$ if ${\cal C}$ is the scheme of a Doob graph. In addition, we prove that $s({\cal C})\le 2$ and $t({\cal C})\le 2$ for any imprimitive 3/2-homogeneous scheme. Finally, we show that $s({\cal C})\le 4$, whenever ${\cal C}$ is a cyclotomic scheme on a prime number of points.

Détail

DOI : 10.37236/1509

Classification : 05E30, 05C12
Mots-clés : coherent configuration, separability number, Schurity number, distance-regular graph, Grassmann scheme, Hamming graph, cyclotomic scheme