Association scheme

In mathematics, Association Schemes are constructs 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\times 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\times 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\leq i,j,l\leq k$ and for any $(x,y)\in R_{l}$ there are exactly $p_{ij}^{l}$ elements $z\in X$ such that $(x,z)\in R_{i}$ and $(z,y)\in R_{j}$

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-subsets A,B of S are said to be i^th associates when $|A\bigcap B|=k-i$.

• The Hamming Scheme, denoted H(n,q) is defined as follows. The points of H(n,q) are the qⁿ vectors of length n over a set of size q. Two n-tuples x,y are said to be i^th associates if the 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, is an association scheme, by defining two vertices to be i^th associates if their distance is i.

References

A Course in Combinatorics ISBN 0-521-00601-5