Glossary

Last modified: May 11, 2007

A distance-regular graph is a graph with the following property. Let G have diameter d. For any vertices x and y of G and any integers i, j between 0 and d (inclusive), the number of vertices z at distance i from x and at distance j from y depends only on i, j and k := dist(x,y) and not on the choice of x and y themselves.

This is a natural generalisation of the concept of a distance transitive graph. A graph is distance transitive if its group of automorphisms is transitive on pairs of vertices at distance i for each i from 0 to d, the diameter of G.

A further generalisation is afforded in the notion of an association scheme. Let X be a finite set of size n and let
A = {R₀, R₁, . . ., R_d} be a set of symmetric relations on X. Call elements x, y of X "i-related" if the ordered pair (x,y) belongs to R_i. Then A is an association scheme if the following conditions are satisfied:
(i) R₀ is the identity relation;
(ii) the relations R_i are pairwise disjoint: any x and y from X are i-related for at most one index i;
(iii) the union of the R_i forms the complete relation X x X: any x and y from X are i-related for at least one index i;
(iv) For any two elements x and y of X (not necessarily distinct) and any two integers i and j, 0<=i,j<=d, the number of elements z of X which are i-related to x and j-related to y does not depend on the choice of x and y, but only on i, j and that k for which x and y are k-related.

If we replace each relation R_i by its zero-one adjacency matrix A_i, we get an alternative definition. An association scheme is a collection of d+1 symmetric zero-one matrices A = {A₀, A₁, . . . , A_d} satisfying:
(I) A₀ is the identity matrix I;
(II/III) the sum of the A_i is the all-ones matrix J;
(IV) the linear space spanned by {A₀, A₁, . . . , A_d} is closed under matrix multiplication. This algebra of matrices is called the Bose-Mesner algebra of the scheme.

What I have just given is actually the definition of a symmetric association scheme. Many sources will not require symmety, but will still ensure that the set A is closed under the transpose operation (hence the linear algebra in (IV) above is closed under the conjugate transpose) and most will stipulate that this algebra is commutative by requiring
p_i,j^k = p_j,i^k
where the intersection numbers p_i,j^k are given by the equations
A_i A_j p_i,j⁰ A₀ + p_i,j¹ A₁ + . . . + p_i,j^d A_d
implied by (iv) and (IV) above.

An association scheme A on vertex set X with Bose-Mesner algebra M is cometric (or Q-polynomial) if there is an ordering of the primitive idempotents E₀=J, E₁, . . . , E_d such that each E_j can be expressed as a polynomial of degree j --- applied entrywise --- in E₁. Equivalently, if we define the Krein parameters q_i,j^k via the equations
E_i o E_j = (1/|X|) ( q_i,j⁰ E₀ + q_i,j¹ E₁ + . . . + q_i,j^d E_d
where the circle o denotes entrywise product, then the scheme is cometric with respect to this ordering of idempotents if and only if

i+j > k implies q_i,j^k = 0
i+j = k ≤ d implies q_i,j^k > 0

A cometric association scheme A is Q-bipartite if

q_i,j^k = 0 unless i+j+k is even

A cometric association scheme A is Q-antipodal if

q_i,j^k = q_d-i,j^d-k for i < d/2

I now describe two fundamental examples of association schemes which happen also to be cometric distance-regular graphs.

The Hamming scheme H(n,q) has vertex set X equal to the set of all strings of length n over an alphabet with q symbols. Two strings x and y are defined to be i-related if they differ in i coordinate places. This is the Hamming metric. So R_i can also be defined as the relation "x and y are at distance i in the graph R₁". Often,R₁ is referred to as the Hamming graph. For q=2, we get the n-cube. Subsets of vertices of the Hamming scheme are codes and orthogonal arrays.

The Johnson scheme J(v,k) has vertex set X equal to the set of all k-subsets of a fixed v-set V. Two k-sets x and y are defined to be i-related if their intersection has k-i elements. This defines a metric. So R_i is the distance-i relation of R₁, a distance-regular graph. Often, R₁ is referred to as the Johnson graph.

This is an excerpt from a larger glossary.