Philippe Delsarte (An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl., 10:vi+97, 1973) generalised the “MacWilliams transform” of coding theory to the theory of association schemes, and there have been numerous powerful applications of this object, particulary in finding the maximum size of a clique in some particular kinds of graphs. These graphs are regular and they are in fact a union of graphs from some association scheme. Let be the maximum size of a clique of a graph .
Theorem (Delsarte): If is the graph of an association scheme with valency , and if is a negative eigenvalue of , then
I will give a proof I’ve seen in one of Chris Godsil’s notes as it bypasses the usual theory on inner distribution vectors and the MacWilliams transform.
Proof: Suppose we have an association scheme with primitive idempotents and suppose is a graph for one of the relations of , of order . Let be a clique of and let be an eigenvalue of with multiplicity . Let us denote by the primitive idempotent whose rowspace is the eigenspace corresponding to . Then the submatrix of with rows and columns indexed by the vertices of has the form
Since is positive semidefinite, the eigenvalues of are non-negative. The constant row-sum value of is an eigenvalue, and so is an eigenvalue and thus is non-negative. This implies that
Since is the Hadamard product we have . Let be the adjacency matrix for . Since and , we have
. Therefore . Hence, if we consider all cliques and the least eigenvalue , we have
This bound doesn’t hold for all regular graphs, as we shall see.
Consider a generalised quadrangle of order and its collinearity graph . Then is regular of valency and a maximal clique of is simply the set of points incident with some line. So . The eigenvalues of are , and . Now is strongy regular and so is the graph of an association scheme, and Delsarte’s bound applies and is tight:
Now consider what we get when we remove a line of . If , then the biggest clique of is still the set of points of a line of the original generalised quadrangle. The valency of is . So if Delsarte’s bound applies, then the least negative eigenvalue of satisfies , and hence,
However, by the theory of interlacing eigenvalues, we must have ; a contradiction.
For what families of regular graphs does this bound hold?