Namespaces
Variants
Actions

Difference between revisions of "Association scheme"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
(TeX done)
 
(4 intermediate revisions by the same user not shown)
Line 3: Line 3:
 
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).
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a1203001.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a1203002.png" /> classes is a finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a1203003.png" /> together with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a1203004.png" /> relations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a1203005.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a1203006.png" /> such that:
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a1203007.png" /> is a partition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a1203008.png" />;
+
i) $\{R_0,\ldots,R_d\}$ is a partition of $X \times X$;
  
ii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a1203009.png" />;
+
ii) $R_0 = \{(x,x) : x \in X\}$;
  
iii) For each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030010.png" /> there is a unique <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030011.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030012.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030013.png" />; that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030014.png" />;
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030015.png" />, the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030016.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030017.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030019.png" /> depends only on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030022.png" />;
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030023.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030024.png" />.
+
v) $p_{ij}^k = p_{ji}^k$ for all $i,j,k \in \{0,\ldots,d\}$.
  
The numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030025.png" /> are called the intersection numbers of the association scheme. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030026.png" />, put <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030027.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030028.png" />. Note that for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030029.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030031.png" /> is a simple [[Graph|graph]] which is regular of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030032.png" />. Indeed, a pair of complementary strongly regular graphs is equivalent to an association scheme with two classes.
+
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 [[Graph complement|complementary]] strongly regular graphs is equivalent to an association scheme with two classes.
  
The Bose–Mesner algebra is the matrix algebra generated by the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030033.png" /> adjacency matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030034.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030035.png" />, where
+
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} \ .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030036.png" /></td> </tr></table>
+
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 matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030037.png" /> sum to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030038.png" /> (the matrix whose every entry is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030039.png" />), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030040.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030041.png" />, for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030042.png" />. The matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030043.png" /> are linearly independent and generate a commutative <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030044.png" />-dimensional semi-simple algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030045.png" /> with a unique basis of minimal idempotents <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030046.png" />. The interplay between the two bases for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030047.png" /> 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
+
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 \ .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030048.png" /></td> </tr></table>
+
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.
 
 
Then the Krein parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030049.png" /> are all non-negative.
 
 
 
The matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030050.png" /> is a minimal idempotent, and one may take <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030051.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030052.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030053.png" /> be the matrices relating the two bases for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030054.png" />:
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030055.png" /></td> </tr></table>
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030056.png" /></td> </tr></table>
 
 
 
It follows that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030057.png" />, which implies that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030058.png" /> are eigenvalues of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030059.png" />, and the columns of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030060.png" /> are the corresponding eigenvectors. Thus, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030061.png" /> is the multiplicity of the eigenvalue <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030062.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030063.png" />. The fact that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030064.png" /> must all be integers is known as the rationality condition for an association scheme.
 
  
 
==Delsarte's linear programming bound.==
 
==Delsarte's linear programming bound.==
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030065.png" /> be a non-empty subset of the underlying set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030066.png" /> for a symmetric association scheme. Define the inner distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030067.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030068.png" /> by
+
Let $Y$ be a non-empty subset of the underlying set $X$ for a symmetric association scheme. Define the ''inner distribution'' $a$ of $Y$ by
 +
$$
 +
a_i = \frac{ |(Y\times Y)\cap R_i| }{ |R_i| } \ .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030069.png" /></td> </tr></table>
+
So, $a_i$ is the average number of points in $Y$ in relation $R_i$ with a fixed point of $Y$. Then Delsarte's linear programming bound says that $aQ \ge 0$. 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.
 
 
So, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030070.png" /> is the average number of points in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030071.png" /> in relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030072.png" /> with a fixed point of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030073.png" />. Then Delsarte's linear programming bound says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030074.png" />. 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.==
 
==Examples.==
Two of the most studied association schemes are the Johnson and Hamming schemes. The Johnson scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030075.png" /> has for its set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030076.png" /> the set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030077.png" />-subsets of a set of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030078.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030079.png" />. The Hamming scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030080.png" /> has the set of all words of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030081.png" /> over an alphabet of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030082.png" /> symbols as its set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030083.png" />. The relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030084.png" /> consists of all pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030085.png" /> for which the [[Hamming distance]] (cf. also [[Error-correcting code]]) between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030086.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030087.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030088.png" />.
+
Two of the most studied association schemes are the Johnson and Hamming schemes. The Johnson scheme $J(v,k)$ has for its set $X$ the set of all $k$-subsets of a set of size $v$. Then $R_i = \{ (x,y) \in X : |x \cap y| = k-i \}$. The Hamming scheme $H(n,q)$ has the set of all words of length $n$ over an alphabet of $q$ symbols as its set $X$. The relation $R_i$ consists of all pairs $(x,y)$ for which the [[Hamming distance]] (cf. also [[Error-correcting code]]) between $x$ and $y$ is $i$.
  
The finite generalized <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030090.png" />-gons with parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030091.png" /> introduced by J. Tits (see [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030092.png" />. The Krein conditions force <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030093.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030094.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030095.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030096.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030097.png" />. For a different type of application of the theory of association schemes to finite generalized <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a12030099.png" />-gons (i.e., generalized quadrangles, cf. also [[Quadrangle|Quadrangle]]; [[Quadrangle, complete|Quadrangle, complete]]), see [[#References|[a13]]].
+
The finite generalized $n$-gons with parameters $(s,t)$ introduced by J. Tits (see [[#References|[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 $n \in \{2,3,4,6,8\}$. The Krein conditions force $t \le s^2$ for $n=4$ or $n=8$, and $s \le t^3$ for $n=6$. For a different type of application of the theory of association schemes to finite generalized $4$-gons (i.e., generalized quadrangles, cf. also [[Quadrangle]]; [[Quadrangle, complete]]), see [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300100.png" /> with vertex set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300101.png" /> of diameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300102.png" />. Define <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300103.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300104.png" /> whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300105.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300106.png" /> are at distance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300107.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300108.png" />. When this defines an association scheme, the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300109.png" /> 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 [[#References|[a6]]]. A more modest introduction to the subject is [[#References|[a2]]]. See [[#References|[a5]]] for a table of strongly regular graphs with at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300110.png" /> vertices. For many applications to coding theory see [[#References|[a8]]], [[#References|[a14]]], [[#References|[a7]]].
+
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 $G$ with vertex set $X$ of diameter $d$. Define $R_i \subset X \times X$ by $(x,y) \in R_i$ whenever $x$ and $y$ are at distance $i$ in $G$. When this defines an association scheme, the graph $G$ 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 [[#References|[a6]]]. A more modest introduction to the subject is [[#References|[a2]]]. See [[#References|[a5]]] for a table of strongly regular graphs with at most $280$ vertices. For many applications to coding theory see [[#References|[a8]]], [[#References|[a14]]], [[#References|[a7]]].
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300111.png" /> be a permutation group acting on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300112.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300113.png" /> has a natural action on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300114.png" /> whose orbits are known as orbitals. If for each pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300115.png" /> of distinct elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300116.png" /> there is an element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300117.png" /> interchanging <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300118.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300119.png" />, 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 [[#References|[a18]]], for example) have their analogues for the Bose–Mesner algebra. With no special hypotheses on the permutation group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120300/a120300120.png" /> a coherent configuration is obtained, a natural motivation for the work of Higman [[#References|[a10]]], [[#References|[a11]]], [[#References|[a12]]].
+
Let $\mathcal{G}$ be a permutation group acting on a set $X$. Then $\mathcal{G}$ has a natural action on $X \times X$ whose orbits are known as orbitals. If for each pair $\{x,y\}$ of distinct elements of $X$ there is an element of $\mathcal{G}$ interchanging $x$ and $y$, 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 [[#References|[a18]]], for example) have their analogues for the Bose–Mesner algebra. With no special hypotheses on the permutation group $\mathcal{G}$ a coherent configuration is obtained, a natural motivation for the work of Higman [[#References|[a10]]], [[#References|[a11]]], [[#References|[a12]]].
  
 
P. Terwilliger (see [[#References|[a16]]] and its references) has pushed the theory of association schemes much further, and in [[#References|[a17]]] has extended the Bose–Mesner algebra to what is now sometimes called the Terwilliger algebra.
 
P. Terwilliger (see [[#References|[a16]]] and its references) has pushed the theory of association schemes much further, and in [[#References|[a17]]] has extended the Bose–Mesner algebra to what is now sometimes called the Terwilliger algebra.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  E. Bannai,  T. Ito,  "Algebraic combinatorics I: association schemes" , ''Lecture Notes'' , '''58''' , Benjamin-Cummings  (1984)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  N.L. Biggs,  "Algebraic graph theory" , ''Tracts in Math.'' , '''67''' , Cambridge Univ. Press  (1974)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  A.E. Brouwer,  A.M. Cohen,  A. Neumaier,  "Distance-regular graphs" , ''Ergebn. Math. (3)'' , '''18''' , Springer  (1989)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  P.J. Cameron,  J.H. van Lint,  "Designs, graphs, codes and their links" , ''London Math. Soc. Student Texts'' , '''22''' , Cambridge Univ. Press  (1991)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  Ph. Delsarte,  "An algebraic approach to the association schemes of coding theory"  ''Philips Research Reports Suppl.'' , '''10'''  (1973)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  C.D. Godsil,  "Algebraic combinatorics" , Chapman&amp;Hall  (1993)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  D.G. Higman,  "Coherent configurations, Part I: Ordinary representation theory"  ''Geom. Dedicata'' , '''4'''  (1975)  pp. 1–32</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  D.G. Higman,  "Coherent configurations, Part II: Weights"  ''Geom. Dedicata'' , '''5'''  (1976)  pp. 413–424</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  S. Hobart,  S.E. Payne,  "Reconstructing a generalized quadrangle from its distance two association scheme"  ''J. Algebraic Combin.'' , '''2'''  (1993)  pp. 261–266</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  F.J. MacWilliams,  N.J.A. Sloane,  "The theory of error–correcting codes" , North-Holland  (1977)</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  S.E. Payne,  J.A. Thas,  "Finite generalized quadrangles" , Pitman  (1984)</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  P. Terwilliger,  "The subconstituent algebra of an association scheme (part III)"  ''J. Algebraic Combin.'' , '''2'''  (1993)  pp. 177–103</TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top">  P. Terwilliger,  "Algebraic graph theory"  ''Notes, January''  (1994)</TD></TR><TR><TD valign="top">[a18]</TD> <TD valign="top">  H. Wielandt,  "Finite permutation groups" , Acad. Press  (1964)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  E. Bannai,  T. Ito,  "Algebraic combinatorics I: association schemes" , ''Lecture Notes'' , '''58''' , Benjamin-Cummings  (1984)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  N.L. Biggs,  "Algebraic graph theory" , ''Tracts in Math.'' , '''67''' , Cambridge Univ. Press  (1974)</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  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</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  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</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  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</TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top">  A.E. Brouwer,  A.M. Cohen,  A. Neumaier,  "Distance-regular graphs" , ''Ergebn. Math. (3)'' , '''18''' , Springer  (1989)</TD></TR>
 +
<TR><TD valign="top">[a7]</TD> <TD valign="top">  P.J. Cameron,  J.H. van Lint,  "Designs, graphs, codes and their links" , ''London Math. Soc. Student Texts'' , '''22''' , Cambridge Univ. Press  (1991)</TD></TR>
 +
<TR><TD valign="top">[a8]</TD> <TD valign="top">  Ph. Delsarte,  "An algebraic approach to the association schemes of coding theory"  ''Philips Research Reports Suppl.'' , '''10'''  (1973)</TD></TR>
 +
<TR><TD valign="top">[a9]</TD> <TD valign="top">  C.D. Godsil,  "Algebraic combinatorics" , Chapman&amp;Hall  (1993)</TD></TR>
 +
<TR><TD valign="top">[a10]</TD> <TD valign="top">  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</TD></TR>
 +
<TR><TD valign="top">[a11]</TD> <TD valign="top">  D.G. Higman,  "Coherent configurations, Part I: Ordinary representation theory"  ''Geom. Dedicata'' , '''4'''  (1975)  pp. 1–32</TD></TR>
 +
<TR><TD valign="top">[a12]</TD> <TD valign="top">  D.G. Higman,  "Coherent configurations, Part II: Weights"  ''Geom. Dedicata'' , '''5'''  (1976)  pp. 413–424</TD></TR>
 +
<TR><TD valign="top">[a13]</TD> <TD valign="top">  S. Hobart,  S.E. Payne,  "Reconstructing a generalized quadrangle from its distance two association scheme"  ''J. Algebraic Combin.'' , '''2'''  (1993)  pp. 261–266</TD></TR>
 +
<TR><TD valign="top">[a14]</TD> <TD valign="top">  F.J. MacWilliams,  N.J.A. Sloane,  "The theory of error–correcting codes" , North-Holland  (1977)</TD></TR>
 +
<TR><TD valign="top">[a15]</TD> <TD valign="top">  S.E. Payne,  J.A. Thas,  "Finite generalized quadrangles" , Pitman  (1984)</TD></TR>
 +
<TR><TD valign="top">[a16]</TD> <TD valign="top">  P. Terwilliger,  "The subconstituent algebra of an association scheme (part III)"  ''J. Algebraic Combin.'' , '''2'''  (1993)  pp. 177–103</TD></TR>
 +
<TR><TD valign="top">[a17]</TD> <TD valign="top">  P. Terwilliger,  "Algebraic graph theory"  ''Notes, January''  (1994)</TD></TR>
 +
<TR><TD valign="top">[a18]</TD> <TD valign="top">  H. Wielandt,  "Finite permutation groups" , Acad. Press  (1964)</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Latest revision as of 21:25, 12 February 2018

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 $Y$ be a non-empty subset of the underlying set $X$ for a symmetric association scheme. Define the inner distribution $a$ of $Y$ by $$ a_i = \frac{ |(Y\times Y)\cap R_i| }{ |R_i| } \ . $$

So, $a_i$ is the average number of points in $Y$ in relation $R_i$ with a fixed point of $Y$. Then Delsarte's linear programming bound says that $aQ \ge 0$. 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 $J(v,k)$ has for its set $X$ the set of all $k$-subsets of a set of size $v$. Then $R_i = \{ (x,y) \in X : |x \cap y| = k-i \}$. The Hamming scheme $H(n,q)$ has the set of all words of length $n$ over an alphabet of $q$ symbols as its set $X$. The relation $R_i$ consists of all pairs $(x,y)$ for which the Hamming distance (cf. also Error-correcting code) between $x$ and $y$ is $i$.

The finite generalized $n$-gons with parameters $(s,t)$ 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 $n \in \{2,3,4,6,8\}$. The Krein conditions force $t \le s^2$ for $n=4$ or $n=8$, and $s \le t^3$ for $n=6$. For a different type of application of the theory of association schemes to finite generalized $4$-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 $G$ with vertex set $X$ of diameter $d$. Define $R_i \subset X \times X$ by $(x,y) \in R_i$ whenever $x$ and $y$ are at distance $i$ in $G$. When this defines an association scheme, the graph $G$ 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 $280$ vertices. For many applications to coding theory see [a8], [a14], [a7].

Let $\mathcal{G}$ be a permutation group acting on a set $X$. Then $\mathcal{G}$ has a natural action on $X \times X$ whose orbits are known as orbitals. If for each pair $\{x,y\}$ of distinct elements of $X$ there is an element of $\mathcal{G}$ interchanging $x$ and $y$, 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 $\mathcal{G}$ 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)
How to Cite This Entry:
Association scheme. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Association_scheme&oldid=42808
This article was adapted from an original article by Stanley Payne (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article