5
$\begingroup$

The adjacency algebra of a graph is the algebra consisting of all polynomials in the adjacency matrix of the graph. An association scheme is a commutative matrix algebra containing the identity and all ones matrices and which is closed under entrywise product and transposition. An association scheme is symmetric if it contains only symmetric matrices. It is not difficult to see that since an association scheme is closed under entrywise product, it must have an orthogonal (with respect to the Hilbert-Schmidt inner product) basis of 01 matrices. These matrices can be viewed as the adjacency matrices of some (di)graphs and these are often called the classes of the scheme.

From here it is easy to see that the adjacency algebra of a graph is a (necessarily symmetric) association scheme if and only if it is closed under entrywise product and contains the all ones matrix (the latter of which is equivalent to the graph being connected and regular).

I am interested mostly in sufficient conditions on a graph for its adjacency algebra to be a symmetric association scheme. This is a little open ended, so maybe I should ask something more specific like the following:

If $G$ is a connected graph that is a single class in an association scheme, then is it true that the adjacency algebra of $G$ is an association scheme?

Two obvious necessary conditions on $G$ are that it must be connected and be the union of classes in a symmetric association scheme, but those are not sufficient. On the other hand it is sufficient for $G$ to be distance regular, but I was hoping for something a bit more general than that.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

I am not sure is this is a useful answer, but it is correct: if the graph is connected and regular, its adjacency algebra is an association scheme if and only if it is closed under Schur product. Note that that it's enough to check that the Schur product of any basis elements is a linear combination of the basis elements. (And there is a basis consisting of powers of the adjacency matrix)>

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ There is also a basis of the adjacency algebra consisting of the projections onto the eigenspaces of the graph. If the graph is a union of classes in an association scheme $\mathcal{C}$, (which it must be for its adjacency algebra to be an association scheme), then each of these projections are sums of some subset of the idempotents of the scheme $\mathcal{C}$. I thought that maybe I could use this to prove that if $G$ is a single connected class in an association scheme, then its adjacency algebra is an association scheme, but I wasn't able to. Do you know of any counterexample to this? $\endgroup$
    – David Roberson
    Commented Aug 19, 2016 at 18:40
  • $\begingroup$ A distance regular graph has an adjacency algebra which is an association scheme. I presume there are graphs with this property that are not distance regular? $\endgroup$
    – Ken W. Smith
    Commented Aug 20, 2016 at 12:46
  • 1
    $\begingroup$ @KenW.Smith Yes, there are other examples. If $G$ is a single class in an association scheme $\mathcal{C}$ with $d$ classes (so $d+1$ basis matrices counting the identity), and $G$ has $d+1$ distinct eigenvalues, then the adjacency algebra of $G$ will be equal to $\mathcal{C}$. This is because the adjacency algebra is contained in $\mathcal{C}$ which has dimension $d+1$ as a vector space, and since $G$ has $d+1$ distinct eigenvalues, its adjacency algebra will also have dimension $d+1$ so it must coincide with $\mathcal{C}$. $\endgroup$
    – David Roberson
    Commented Aug 20, 2016 at 14:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .