Association Scheme - Examples

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 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 qn 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 1st associates, x and z are 1st associates and y and z are 2nd 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, with a class R_g for each group element, as follows: for each let 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.

• A specific 3-class association scheme:

Let A(3) be the following association scheme with three associate classes on the set X = {1,2,3,4,5,6}. The (i,j) entry is s if elements i and j are in relation R_s.