Association scheme

Association schemes were introduced by R.C. Bose and T. Shimamoto [a4], studied further via the Bose–Mesner algebra introduced in [a3], generalized and given a most important impetus by P. Delsarte [a8], and generalized further by D.G. Higman [a10], [a11], [a12] to the theory of coherent configurations. The first text devoted to the theory is [a1]. A recent text that develops the theory both quite generally and quite extensively is [a9].

Association schemes provide the appropriate setting for treating certain problems from several different areas of algebraic combinatorics, for example, coding theory, design theory, algebraic graph theory, finite group theory, and finite geometry. The following definition is equivalent to that of Delsarte (1973).

An association scheme $\mathcal{A}$ with $d$ classes is a finite set $X$ together with $d+1$ relations $R_i$ on $X$ such that:

i) $\{R_0,\ldots,R_d\}$ is a partition of $X \times X$;

ii) $R_0 = \{(x,x) : x \in X\}$;

iii) For each $R_i$ in $\mathcal{A}$ there is a unique $R_j$ in $\mathcal{A}$ for which $(x,y) \in R_i$ if and only if $(y,x) \in R_j$; that is, $R_j = R_i^\top$;

iv) for any $(x,y) \in R_k$, the number $p_{ij}^k$ of $z$ with $(x,z) \in R_i$ and $(z,y) \in R_j$ depends only on $i,j,k$;

v) $p_{ij}^k = p_{ji}^k$ for all $i,j,k \in \{0,\ldots,d\}$.

The numbers $p_{ij}^k$ are called the intersection numbers of the association scheme. For $0 \le i \le d$, put $n_i = p_{ii}^0$, and $n = \sum_i n_i = |X|$. Note that for each $i \in \{1,\ldots,d\}$ for which $R_i^\top = R_i$, $(X,R_i)$ is a simple graph which is regular of degree $n_i$. Indeed, a pair of complementary strongly regular graphs is equivalent to an association scheme with two classes.

The Bose–Mesner algebra is the matrix algebra generated by the $n \times n$ adjacency matrices $A_i$ of $R_i$, where $$ (A_i)_{xy} = \begin{cases} 1 & \text{if}\,(x,y) \in R_i \\ 0 &\text{otherwise}\end{cases} \ . $$

The matrices $A_i$ sum to $J$ (the matrix whose every entry is $1$), $A_0 = I$, and $A_i A_j = \sum_k p_{ij}^k A_k$, for all $i,j \in \{0,\ldots,d\}$. The matrices $a_i$ are linearly independent and generate a commutative $(d+1)$-dimensional semi-simple algebra $\mathcal{A}$ with a unique basis of minimal idempotents $E_0,\ldots,E_d$. The interplay between the two bases for $\mathcal{A}$ leads to useful restrictions on the various parameters, for example the so-called Krein conditions (discovered by L.L. Scott Jr., 1973). These restrictions are given as follows: Write $$ E_i \circ E_j = \frac{1}{n} \sum_k q_{ij}^k E_k \ . $$ Then the Krein parameters $q_{ij}^k$ are all non-negative.

The matrix $(1/n)J$ is a minimal idempotent, and one may take $E_0 = (1/n)J$. Let $P$ and $(1/n)Q$ be the matrices relating the two bases for $\mathcal{A}$: $$ A_j = \sum_{i=0}^d P_{ij}E)i \ ; $$ $$ E_j = \frac{1}{n} \sum_{i=0}^d Q_{ij} A_i \ . $$

It follows that $A_j E_i = P_{ij} E_j$, which implies that the $P_{ij}$ are eigenvalues of $A_j$, and the columns of $E_i$ are the corresponding eigenvectors. Thus, $\mu_i = \mathrm{rank}(E_i)$ is the multiplicity of the eigenvalue $P_{ij}$ of $A_j$. The fact that the $\mu_i$ must all be integers is known as the rationality condition for an association scheme.

Delsarte's linear programming bound.

Let be a non-empty subset of the underlying set for a symmetric association scheme. Define the inner distribution of by

So, is the average number of points in in relation with a fixed point of . Then Delsarte's linear programming bound says that . This set of inequalities has been used to obtain upper bounds on the size of cliques and lower bounds on the size of designs in various structures.

Examples.

Two of the most studied association schemes are the Johnson and Hamming schemes. The Johnson scheme has for its set the set of all -subsets of a set of size . Then . The Hamming scheme has the set of all words of length over an alphabet of symbols as its set . The relation consists of all pairs for which the Hamming distance (cf. also Error-correcting code) between and is .

The finite generalized -gons with parameters introduced by J. Tits (see [a15]) provide examples of strongly regular graphs to which the theory of association schemes may be applied. The rationality conditions can be used to show that . The Krein conditions force for or , and for . For a different type of application of the theory of association schemes to finite generalized -gons (i.e., generalized quadrangles, cf. also Quadrangle; Quadrangle, complete), see [a13].

An association scheme with just two classes is equivalent to a pair of complementary strongly regular graphs. The theory of strongly regular graphs is subsumed in the theory of distance-regular graphs. Start with a connected simple graph with vertex set of diameter . Define by whenever and are at distance in . When this defines an association scheme, the graph is called distance-regular. Many of the association schemes that arise in combinatorics are of this type. The major reference for distance-regular graphs is [a6]. A more modest introduction to the subject is [a2]. See [a5] for a table of strongly regular graphs with at most vertices. For many applications to coding theory see [a8], [a14], [a7].

Let be a permutation group acting on a set . Then has a natural action on whose orbits are known as orbitals. If for each pair of distinct elements of there is an element of interchanging and , then the orbitals form an association scheme. The Bose–Mesner algebra in this case is known as the centralizer algebra, and the standard results (as given in [a18], for example) have their analogues for the Bose–Mesner algebra. With no special hypotheses on the permutation group a coherent configuration is obtained, a natural motivation for the work of Higman [a10], [a11], [a12].

P. Terwilliger (see [a16] and its references) has pushed the theory of association schemes much further, and in [a17] has extended the Bose–Mesner algebra to what is now sometimes called the Terwilliger algebra.

References

[a1]	E. Bannai, T. Ito, "Algebraic combinatorics I: association schemes" , Lecture Notes , 58 , Benjamin-Cummings (1984)
[a2]	N.L. Biggs, "Algebraic graph theory" , Tracts in Math. , 67 , Cambridge Univ. Press (1974)
[a3]	R.C. Bose, D.M. Mesner, "On linear associative algebras corresponding to association schemes of partially balanced designs" Ann. Math. Stat. , 30 (1959) pp. 21–38
[a4]	R.C. Bose, T. Shimamoto, "Classification and analysis of partially balanced incomplete block designs with two associate classes" J. Amer. Statist. Assoc. , 47 (1952) pp. 151–184
[a5]	A.E. Brouwer, "Strongly regular graphs" C.J. Colbourn (ed.) J.H. Dinitz (ed.) , The CRC Handbook of Combinatorial Designs , CRC (1996) pp. Part VI, Chapt. 5
[a6]	A.E. Brouwer, A.M. Cohen, A. Neumaier, "Distance-regular graphs" , Ergebn. Math. (3) , 18 , Springer (1989)
[a7]	P.J. Cameron, J.H. van Lint, "Designs, graphs, codes and their links" , London Math. Soc. Student Texts , 22 , Cambridge Univ. Press (1991)
[a8]	Ph. Delsarte, "An algebraic approach to the association schemes of coding theory" Philips Research Reports Suppl. , 10 (1973)
[a9]	C.D. Godsil, "Algebraic combinatorics" , Chapman&Hall (1993)
[a10]	D.G. Higman, "Invariant relations, coherent configurations and generalized polygons" M. Hall Jr. (ed.) J.H. van Lint (ed.) , Combinatorics , Math. Centre Tracts , 57 , Reidel (1975) pp. 347–363
[a11]	D.G. Higman, "Coherent configurations, Part I: Ordinary representation theory" Geom. Dedicata , 4 (1975) pp. 1–32
[a12]	D.G. Higman, "Coherent configurations, Part II: Weights" Geom. Dedicata , 5 (1976) pp. 413–424
[a13]	S. Hobart, S.E. Payne, "Reconstructing a generalized quadrangle from its distance two association scheme" J. Algebraic Combin. , 2 (1993) pp. 261–266
[a14]	F.J. MacWilliams, N.J.A. Sloane, "The theory of error–correcting codes" , North-Holland (1977)
[a15]	S.E. Payne, J.A. Thas, "Finite generalized quadrangles" , Pitman (1984)
[a16]	P. Terwilliger, "The subconstituent algebra of an association scheme (part III)" J. Algebraic Combin. , 2 (1993) pp. 177–103
[a17]	P. Terwilliger, "Algebraic graph theory" Notes, January (1994)
[a18]	H. Wielandt, "Finite permutation groups" , Acad. Press (1964)