3
$\begingroup$

Suppose $X$ and $Y$ are two $n$-circulants (Cayley graphs for $\mathbb{Z}_n$) with adjacency matrices $A_X$ and $A_Y$. Since they are circulants, both $X$ and $Y$ lie in some symmetric association schemes (details below). Let $\mathcal{C}_X$ and $\mathcal{C}_Y$ be the smallest association schemes containing $A_X$ and $A_Y$ respectively. Suppose that $\phi: \mathcal{C}_X \to \mathcal{C}_Y$ is an isomorphism of association schemes (bijective linear map that preserves matrix multiplication, entrywise multiplication, and transposition) that also satisfies $\phi(A_X) = A_Y$. Under these conditions, is it possible for $X$ and $Y$ to be NOT isomorphic? By the results of this paper, it seems that this cannot happen if one of the graphs (and thus also the other) is distance regular.

If I understand correctly, the condition imposed on $X$ and $Y$ is equivalent to the Weisfeiler-Lehman algorithm NOT being able to distinguish them.

Details on association schemes:

A symmetric association scheme $\mathcal{C}$ is a matrix subalgebra of the real $n \times n$ matrices that contains identity and the all ones matrix, is closed under entrywise mutliplication and transposition, and contains only symmetric matrices. Note that the last condition also implies that all matrices in $\mathcal{C}$ commute with each other. Since it is closed under entrywise multiplication, any symmetric association scheme has an orthogonal basis of 01-matrices $A_0, \ldots, A_d$ that sum up to the all ones matrix. One of these is necessarily the identity matrix (so WLOG we let $A_0 = I$) and thus the other $A_i$ are 01 symmetric matrices with 0 on the diagonal. We can think of these as adjacency matrices of graphs, and we say that a graph lies in $\mathcal{C}$ if its adjacency matrix is the sum of some of the $A_i$. It is easy to see that the intersection of two association schemes is an association scheme, and thus if a graph lies in an association scheme, there is some unique minimal association scheme that contains it.

For a given $n \in \mathbb{N}$, let $A_s$ be the $n \times n$ matrix whose $ij$-entry is 1 if $i - j \equiv \pm s \text{ mod } n$, and is 0 elsewhere. It is not difficult to see that these $A_s$ matrices are the 01-basis of a symmetric association scheme, and that any $n$-circulant lies in this scheme. Thus any circulant graph lies in a symmetric association scheme.

$\endgroup$
  • $\begingroup$ If $\phi$ is an isomorphism from $\mathcal{A}_X$ to $\mathcal{A}_Y$, won't we have $\phi(\mathcal{A}_X)=\mathcal{A}_Y$? $\endgroup$ – Chris Godsil Aug 15 '16 at 15:35
  • $\begingroup$ @ChrisGodsil Yes, that's correct. $\endgroup$ – David Roberson Aug 15 '16 at 16:21
  • $\begingroup$ I think I'm missing something: doesn't the cycle $C_7$ and its complement provide a counterexample? $\endgroup$ – Chris Godsil Aug 15 '16 at 18:02
  • $\begingroup$ @ChrisGodsil I think you are missing the $\phi(A_X) = A_Y$ in that example. Any map $\phi$ that satisfies the conditions must be sum-preserving, i.e., the sum of the entries of $M$ and $\phi(M)$ are the same. Since $C_7$ and its complement do not have the same degree, no such function can map the adjacency matrix of $C_7$ to that of its complement. The $\phi(A_X) = A_Y$ condition is important exactly for this reason, since without it any circulant and its complement would be a counterexample (as your example shows). $\endgroup$ – David Roberson Aug 15 '16 at 22:32
  • $\begingroup$ @ChrisGodsil I realize now that your confusion is most likely due to my poor choice of notation. The adjacency matrix of $X$ is $A_X$, the minimal association scheme containing $X$ is $\mathcal{A}_X$. I've gone back and changed the latter to $\mathcal{C}_X$ (and similarly for $Y$). $\endgroup$ – David Roberson Aug 16 '16 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.