Association scheme

In mathematics, association schemes are structures that appear in many different forms in the fields of combinatorics and statistics.

Definition

Recall that a binary relation $R$ on a set $X$ can be thought of as subset of $X\; imes\; X$.

A "k-class Association Scheme" is a set of points, "X", along with "k+1" binary relations $R\_0,R\_1,ldots,R\_k$which partition $X\; imes\; X$ and $R\_0\; =\; \{(x,x)\; |\; x\; in\; X\}$ (i.e. $R\_0$ is the identity relation), such that the following holds:

There exist $(k+1)^3$ non-negative integers $p\_\{ij\}^l$ with $0\; le\; i,j,l\; le\; k$ and for any $(x,y)\; in\; R\_l$ thereare exactly $p\_\{ij\}^l$ elements $z\; in\; X$ such that $(x,z)\; in\; R\_i$ and $(z,y)\; in\; R\_j$

An association scheme is "commutative" if $p\_\{ij\}^l=p\_\{ji\}^l$ for all $i$, $j$ and $l$. Most authorsassume this property.

A "symmetric association scheme" is one in which each relation $R\_i$ is a symmetric relation. Every symmetric association scheme is commutative.

Terminology

*If $(x,y)\; in\; R\_i$ we say that $x$ and $y$ are "i"^th associates.
*The numbers $p\_\{ij\}^l$ are called the parameters of the scheme.

Basic Facts

*$p\_\{00\}^0\; =\; 1$, i.e. if $(x,y)\; in\; R\_0$ then $x\; =\; y$ and the only $z$ such that $(x,z)\; in\; R\_0$ is $z=x$
*$sum\_\{i=0\}^\{k\}\; p\_\{ii\}^0\; =\; |X|$, this is because the $R\_i$ partition $X$.

Examples

*The "Johnson scheme", denoted "J"("v,k"), is defined as follows. Let "S" be a set with "v" elements. The points of the scheme "J(v,k)" are the $\{v\; choose\; k\}$ subsets of S with "k" elements. Two "k"-element subsets "A", "B" of "S" are "i" ^th associates when their intersection has size "k − i".

*The "Hamming scheme", denoted "H"("n,q"), is defined as follows. The points of "H(n,q)" are the "qⁿ" ordered "n"-tuples over a set of size "q". Two "n"-tuples "x, y" are said to be "i" ^th associates if they disagree in exactly "i" coordinates. E.g., if "x" = (1,0,1,1), "y" = (1,1,1,1), "z" = (0,0,1,1), then "x" and "y" are 1^st associates, "x" and "z" are 1^st associates and "y" and "z" are 2^nd associates in "H(4,2)".

*A distance-regular graph, "G", forms an association scheme by defining two vertices to be "i" ^th associates if their distance is "i".

*A finite group $G$ yields an association scheme on $X=G$, with a class "R"_"g" for each group element, as follows: for each $g\; in\; G$ let $R\_g=\{(x,y)\; |\; x=g*y\}$ where $*$ is the group operation. The class of the group identity is "R"₀. This association scheme is commutative if and only if $G$ is abelian.

References

* Bailey, R.A. (2004), "Association Schemes: Designed Experiments, Algebra and Combinatorics". Cambridge, Eng.: Cambridge University Press. ISBN 0-521-82446-X
* Delsarte, P. (1973), "An Algebraic Approach to the Association Schemes of Coding Theory". Philips Research Reports, Supplement No. 10.
* van Lint, J.H., and Wilson, R.M. (1992), "A Course in Combinatorics". Cambridge, Eng.: Cambridge University Press. ISBN 0-521-00601-5