ASSOCIATION SCHEME

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

Contents

Definition

Terminology

Basic Facts

Examples

References

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$ there
are 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 authors
assume 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