A first course in association schemes

A First Course in Association Schemes === - by John Bamberg and Jacob Smith. The first year this course was run, it was a reading course for one student, Jacob Smith. His task was to write a set of notes on a specific list of topics, in each week of the unit. These notes are built upon his notes, and there are many new additions to the syllabus that have been developed over the second year of the course. Graphs --- First we need some basic jargon from graph theory. A *graph* $\Gamma$ is a mathematical structure which consists of a set of vertices $\mathrm{V}(\Gamma)$ and a set of edges $\mathrm{E}(\Gamma) \subseteq \mathrm{V}(\Gamma) \times \mathrm{V}(\Gamma)$, where edges are unordered pairs. Two vertices $v, w \in \mathrm{V}(\Gamma)$ are said to be *adjacent* if $(v, w) \in \mathrm{E}(\Gamma)$. This is denoted by $v \sim w$. A *finite graph* is a graph whose vertex set is finite. A *loop* is an edge of the form $(v, v)$ for some vertex $v$. A *simple graph* is a graph $\Gamma$ which contains no loops. The *order* of a graph $\Gamma$, denoted $|\Gamma$|, is the number of vertices in the graph (the cardinality of $\mathrm{V}(\Gamma)$). The *degree* of a vertex is the number of vertices adjacent to it, and the *neighbourhood* of a vertex is the set of all vertices adjacent to it. The adjacency matrix $A$ of a finite graph $\Gamma$ has its rows and columns indexed by the vertices of $\Gamma$, and the entry $A_{i, j}$ is equal to $1$ if the $i$th and $j$th vertices of $\Gamma$ are adjacent, or $0$ if they are not adjacent. Adjacency matrices are symmetric since $v \sim w$ if and only if $w \sim v$, for any two vertices $v$ and $w$. A *$k$-regular graph*, where $k$ is a non-negative integer, is a graph in which every very vertex has degree $k$. From the point of view of the adjacency matrix, a graph is $k$-regular if and only if every row of its adjacency matrix sums to $k$. The *complement* $\bar \Gamma$ of a graph $\Gamma$ is the graph which has the same vertex set $\mathrm{V}(\bar \Gamma) = \mathrm{V}(\Gamma)$, but which has edge set $\mathrm{E}(\bar \Gamma) = \{(v_1, v_2) \in V(\bar \Gamma) \times \mathrm{V}(\bar \Gamma) \mid (v_1, v_2) \notin \mathrm{E}(\Gamma), v_1 \neq v_2\}$. This means that any two distinct vertices are adjacent in $\bar \Gamma$ if and only if they are not adjacent in $\Gamma$. If $\Gamma$ has $n$ vertices and its adjacency matrix is $A_\Gamma$, and if $J$ denotes the $n \times n$ matrix in which every entry is $1$, then the adjacency matrix $A_{\bar \Gamma}$ of $\bar \Gamma$ is equal to $J - A - I$. ### Walks in graphs Given a graph $\Gamma$, a *walk* is a sequence (finite or infinite) of vertices $\{v_1, v_2,\ldots\}$ where $v_i \sim v_{i+1}$ for all $i$. In other words, any two consecutive vertices in the walk are adjacent in $\Gamma$. A walk may contain the same vertex multiple times. A walk of length $n$, or *$n$-walk*, is a walk which is a sequence of $n + 1$ vertices. A *closed walk* is a finite walk which begins and ends at the same vertex. A *cycle* is a set of vertices which comprise a closed walk $\{v_1, v_2,\ldots, v_n\}$ such that $v_i \neq v_i+2$ for all $i$. Two vertices are said to be *connected* in a graph if there exists a walk containing both vertices. A *connected component* of a graph $\Gamma$ is a non-empty subset $S$ of $\mathrm{V}(\Gamma)$ such that any two elements of $S$ are connected, but such that no elements of $S$ are connected to any vertices outside $S$. A graph is said to be *connected* if it has exactly one connected component (or equivalently, if every vertex in the graph is connected to every other vertex). A *path* is a connected graph in which all vertices have degree 2, except for two vertices which have degree 1. This can be thought of as a sequence of vertices in which consecutive vertices are adjacent. An *isomorphism* $\varphi$ from a graph $\Gamma_1$ to a graph $\Gamma_2$ is a one-to-one mapping $\mathrm{V}(\Gamma_1) \rightarrow \mathrm{V}(\Gamma_2)$ that preserves adjacency. This means that for any $v, w \in \Gamma_1$, we have $\varphi(v) \sim_2 \varphi(w)$ if and only if $v \sim_1 w$, where $\sim_1$ and $\sim_2$ indicate adjacency in $\Gamma_1$ and $\Gamma_2$ respectively. Two graphs are said to be *isomorphic* if there is an isomorphism from one to the other. A *permutation matrix* is a square matrix in which every entry is either $0$ or $1$, and every row and column contains exactly one $1$. If $\Gamma_1$ and $\Gamma_2$ are graphs of equal order with adjacency matrices $A_1$ and $A_2$ respectively, and $P$ is a permutation matrix satisfying $P^\top A_1 P = A_2$, then there is an isomorphism from $\Gamma_1$ to $\Gamma_2$ which maps the $i$th vertex of $\Gamma_1$ to the $j$th vertex of $\Gamma_2$, where the $1$ entry in the $i$th row of $P$ is located in the $j$th position. The converse is also true, and so we can interpret isomorphism of graphs in an algebraic way, via congruence of adjacency matrices. ### Eigenvalues of graphs :::info The vertex-sum game > to be completed ::: > Petersen graph examples The *eigenvalues* and *eigenvectors* of a graph $\Gamma$ are the eigenvalues and eigenvectors of its adjacency matrix $A$. Specifically, if $n = |\Gamma|$, then the vector $v = (v_1, v_2,\ldots, v_n) \in \mathbb{R}^n$ is an eigenvector of $A$ (and hence of $\Gamma$) if $vA = \lambda v$ for some $\lambda \in \mathbb{R}$. Then $\lambda$ is said to be the eigenvalue of $A$ (and of $\Gamma$) corresponding to the eigenvector $v$. The *spectrum* of a graph its set of eigenvalues. The largest eigenvalue is known as the *spectral radius* of the graph. > Example: complete graph ### Theorem If $\Gamma$ is a $k$-regular graph with $n$ vertices, then the all-ones vector $j$ (that is, the $n$-dimensional vector $j$ in which each of the $n$ components is equal to $1$) is an eigenvector of $\Gamma$, with corresponding eigenvalue $k$. #### Proof If $A$ denotes the adjacency matrix of $\Gamma$, then for each index $i \in \left\{1, 2, \ldots, n \right\}$, we have $$\left(Aj \right)_i = \sum_{l=1}^n A_{il} = \mathrm{deg}\left(i \right) = k.$$ Hence $Aj = kj$, so $j$ is an eigenvector of $\Gamma$ with corresponding eigenvalue $k$. $\square$ - Cospectral graphs ### Theorem If $v$ and $w$ are eigenvectors of a real, symmetric matrix $M$ that correspond to different eigenvalues, then $v$ and $w$ are orthogonal (that is, $v \cdot w = 0$). #### Proof Denote by $\lambda_v$ and $\lambda_w$ the eigenvalues of $M$ corresponding to $v$ and $w$, respectively. Since $M$ is symmetric, we know $M = M^T$. Using this, we have $$\lambda_v \left(v \cdot w \right) = \left(\lambda_v v \right) \cdot w = \left(Mv \right) \cdot w = v \cdot \left(M^T w \right) = v \cdot \left(Mw \right) = v \cdot \left(\lambda_w w \right) = \lambda_w \left(v \cdot w \right),$$ and since $\lambda_v \neq \lambda_w$, we conclude that $v \cdot w = 0$. $\square$ ### Theorem The eigenvalues of any real symmetric matrix are real. #### Proof Suppose $M$ is a real symmetric matrix and let $v$ be an eigenvector of $M$ with eigenvalue $\lambda\in\mathbb{C}$. Consider $\lambda \|v\|^2$. We have $$\lambda\|v\|^2=\lambda(vv^*)=(\lambda v)v^*=(vM)v^*=vM\overline{v}^\top=v\overline{(vM^\top)}^\top=v\overline{(vM)}^\top=v\overline{(\lambda v)}^\top=\overline{\lambda}(vv^*)=\overline{\lambda}\|v\|^2.$$ Since $v$ is nonzero, it follows that $\lambda=\overline{\lambda}$. $\square$ ### Theorem All the eigenvalues of a graph $\Gamma$ have magnitude less than or equal to the maximum degree of $\Gamma$. #### Proof Let $A$ be the adjacency matrix of $\Gamma$, let $n$ be the number of vertices in $\Gamma$, let $\Delta$ be the maximum degree of $\Gamma$, and let $\lambda$ be an eigenvalue of $\Gamma$ with eigenvector $v$. Let $j \in \left\{1, 2, \ldots, n \right\}$ such that $|v_j|\ge |v_i|$ for all $i$. Then from $\lambda v = Av$, we have $$\lambda v_j = \sum_{i=1}^n A_{ji} v_i = \sum_{i \sim j} v_i$$ and so $$|\lambda v_j|=|\sum_{i\sim j} v_i|\leqslant \sum_{i \sim j} |v_i| \leqslant \sum_{i \sim j} |v_j|= \mathrm{deg}{\left(j \right)} |v_j| \leqslant \Delta |v_j|$$ where $\mathrm{deg}{\left(j \right)}$ denotes the degree of the $j$th vertex. Hence $|\lambda| \leqslant \Delta$ as required. $\square$  ### Theorem Let $\bar \Gamma$ be the complement of a $k$-regular graph $\Gamma$ with $n$ vertices. Then the eigenvalues of $\bar \Gamma$ are $\left(n-k-1 \right)$, and $\left(-\lambda - 1 \right)$ for each eigenvalue $\lambda$ of $\Gamma$ other than $k$. #### Proof Recall that the adjacency matrix of $\bar \Gamma$ is $J-A-I$, where $A$ is the adjacency matrix of $\Gamma$, and $J$ is the $n \times n$ matrix in which every entry is a $1$. Let $j$ be the all-ones vector as defined in the proof of the previous theorem. Now, using the fact that $Aj = kj$ from the previous theorem, we have $$\left(J-A-I \right) j = Jj - Aj - Ij = nj - kj - j = \left(n-k-1 \right) j,$$ so $\left(n-k-1 \right)$ is an eigenvalue of $\bar \Gamma$. Now suppose that $v$ is an eigenvector of $\Gamma$ corresponding to an eigenvalue $\lambda \neq n-k-1$. Then $v$ and $j$ are eigenvectors of $\Gamma$ that correspond to different eigenvalues, hence $j \cdot v = 0$. Using this, we have $$\left(J-A-I \right) v = Jv - Av - Iv = \left(j \cdot v \right) j - \lambda v - v = \left(-\lambda - 1 \right) v,$$ so $\left(-\lambda - 1 \right)$ is an eigenvalue of $\bar \Gamma$. $\square$ ### Powers of the adjacency matrix If a graph $\Gamma$ has order $n$ and adjacency matrix $A$, then the $(i, j)$-entry of $A^2$ is equal to the number of indices $k \in \{1, 2,\ldots, n\}$ such that $A_{i, k} = A_{k, j} = 1$. This in turn is the number of vertices that are adjacent to both the $i$th and $j$th vertices. Hence the $(i, j)$-entry of $A^2$ is equal to the number of $2$-walks beginning at the $i$th vertex and ending at the $j$th vertex. In particular, the number of closed walks of length $2$ can be found by summing the diagonal entries of $A^2$, hence it is equal to $\mathrm{tr}(A^2)$. As each edge permits exactly two closed walks, the number of edges of a graph can be found using the rule $|\mathrm{E}(\Gamma)| = \frac{1}{2} \mathrm{tr}(A^2)$. In general, the number of $r$-walks beginning and ending at the $i$th and $j$th vertices respectively is equal to the $(i, j)$-entry of $A^r$, and the number of closed walks of length $r$ is equal to $\mathrm{tr}(A^r)$. Since the trace of a matrix is equal to the sum of its eigenvalues, and $\lambda^r$ is an eigenvalue of $A^r$ if and only if $\lambda$ is an eigenvalue of $A$, it follows that $\mathrm{tr}(A^r) = \sum_\lambda \lambda^r$, where the sum runs over all the eigenvalues $\lambda$ of $A$. An immediate consequence of this is that co-spectral graphs have the same number of closed walks. ### Bipartite graphs A $bipartite$ graph is a graph $\Gamma$ whose vertex set $\mathrm{V}(\Gamma)$ can be partitioned into two subsets $V_1$ and $V_2$ such that no two edges in $V_1$ are adjacent, and no two edges in $V_2$ are adjacent. Equivalently, a graph is bipartite if it has no odd cycles. Equivalently, a graph is bipartite if it has a proper 2-colouring of its vertices. Equivalently, its adjacency matrix takes the form $$A = \left[ \begin{array}{c|c} 0 & X \\ \hline X^T & 0 \end{array} \right]$$ for some matrix $X$. #### Theorem If $\lambda$ is an eigenvalue of a bipartite graph $\Gamma$, then $-\lambda$ is also an eigenvalue of $\Gamma$. :::spoiler Proof Let $A$ be the adjacency matrix of $\Gamma$, and let $v$ be an eigenvector of $\Gamma$ corresponding to the eigenvalue $\lambda$. Then the equation $Av = \lambda v$ can be expressed as $$\left[ \begin{array}{c|c} 0 & X \\ \hline X^T & 0 \end{array} \right] \left[ \begin{array}{c} v_1 \\ \hline v_2 \end{array} \right] = \lambda \left[ \begin{array}{c} v_1 \\ \hline v_2 \end{array} \right]$$ if we write $A = \left[ \begin{array}{c|c} 0 & X \\ \hline X^T & 0 \end{array} \right]$ and $v = \left[ \begin{array}{c} v_1 \\ \hline v_2 \end{array} \right]$. Now observe that $$\left[ \begin{array}{c|c} 0 & X \\ \hline X^T & 0 \end{array} \right] \left[ \begin{array}{c} v_1 \\ \hline -v_2 \end{array} \right] = \lambda \left[ \begin{array}{c} -v_1 \\ \hline v_2 \end{array} \right] = -\lambda \left[ \begin{array}{c} v_1 \\ \hline -v_2 \end{array} \right],$$ so $-\lambda$ is an eigenvalue of $A$, and hence of $\Gamma$, as required. $\square$ ::: ### Perron-Frobenius theorem > Add more here If the largest eigenvalue of a strongly connected directed graph is non-zero and real, then there is a positive eigenvector for it, which is unique up to scaling. #### Theorem (Coulson & Rushbrooke, 1940) (a) A graph $\Gamma$ is bipartite if and only if its spectrum is symmetric about 0. (b) If $\Gamma$ is connected, then $\Gamma$ is bipartite if and only if $\lambda_{\mathrm{min}} = -\lambda_{\mathrm{max}}$, where $\lambda_{\mathrm{min}}$ and $\lambda_{\mathrm{max}}$ are the minimum and maximum eigenvalues of $\Gamma$, respectively. Proof: to be completed. ### Strongly regular graphs A $k$-regular graph is called *strongly regular* if it is not a complete graph and there exist integers $\lambda$ and $\mu$ such that: - any two adjacent vertices share exactly $\lambda$ neighbours, and - any two non-adjacent vertices share exactly $\mu$ neighbours. The parameters of a strongly regular graph are the integers $\left(n, k, \lambda, \mu \right)$ where $n$ is the number of vertices in the graph, $k$ is the degree of each vertex, and $\lambda$ and $\mu$ are the integers satisfying the above properties. #### Theorem If $\Gamma$ is a strongly regular graph with parameters $\left(n, k, \lambda, \mu \right)$, then the complement graph $\bar \Gamma$ is a strongly regular graph with parameters $\left(n, n-k-1, n - 2k + \mu - 2, n - 2k + \lambda \right)$. :::spoiler Proof By definition, $\bar \Gamma$ has $n$ vertices. Since any given vertex $v \in \Gamma$ is adjacent to exactly $k$ other vertices, there must be exactly $n-k-1$ vertices that are not equal to or adjacent to $v$. Therefore every vertex has exactly $n-k-1$ neighbours in the complement graph $\bar \Gamma$. Now let us determine the fourth parameter of $\bar \Gamma$. To do this, we must count the number of neighbours (in $\bar \Gamma$) common to two arbitrarily chosen vertices $v_1$ and $v_2$ that are not adjacent in $\bar \Gamma$. This is equivalent to counting the number of vertices, other than $v_1$ and $v_2$, that are not adjacent to either $v_1$ or $v_2$ in the original graph $\Gamma$. Since $v_1$ and $v_2$ are adjacent in $\Gamma$, the vertex $v_1$ has $\left(k-1 \right)$ neighbours in $\Gamma$ that are not equal to $v_1$ or $v_2$. The vertex $v_2$ also has $\left(k-1 \right)$ such neighbours. Using the fact that $v_1$ and $v_2$ share $\lambda$ common neighbours in $\Gamma$, the total number of vertices (other than $v_1$ and $v_2$) that are adjacent to either $v_1$ or $v_2$ is equal to $\left(k-1 \right) + \left(k-1 \right) - \lambda$ by the inclusion–exclusion principle. To obtain the number of vertices (other than $v_1$ and $v_2$) that are not adjacent in $\Gamma$ to either $v_1$ or $v_2$, we simply subtract this expression from $\left(n-2 \right)$. This yields a value of $n - 2k + \lambda$ for the fourth parameter of $\bar \Gamma$. The third parameter of $\bar \Gamma$ can be determined similarly. $\square$ ::: #### Theorem (Fesability condition) If a strongly regular graph has parameters $\left(v, k, \lambda, \mu \right)$, then $k(k - \lambda - 1) = \mu \left(v - k - 1 \right)$. :::spoiler Proof We use a simple counting argument. Fix a vertex $x$. We will count the pairs of vertices $(u,v)$ two ways, where $u\sim x$, $w\not\sim x$, and $u\sim w$. So $$\sum_{u\sim x}|\{w:w\sim u\text{ and }w\not\sim x\}|=\sum_{w\not\sim x}|\{u:u\sim w\text{ and }u\sim x\}|.$$ The left-hand side is $k(k-\lambda-1)$ and the right-hand side is $\mu(v-k-1)$.$\square$ ::: --- Let $\Gamma$ be a strongly regular graph with parameters $\left(v, k, \lambda, \mu \right)$. We can encode the property of being strongly regular into an equation involving matrices, since it really is just a property about 2-walks in the graph: $$A^2=kI+\lambda A+\mu(J-I-A).$$ Now suppose $\theta$ is an eigenvalue of $A$, with $\theta\ne k$. Let $v$ be an eigenvector for $\theta$. Then $v$ is orthogonal to $j$ since $j$ has eigenvalue $k$ (not equal to $\theta$). So $vJ=0$. Hence $$\theta^2v=kv+\lambda \theta v+\mu(-v-\theta v)$$ and we can solve a quadratice equation for $\theta$. So $\Gamma$ has exactly three eigenvalues: specifically $k$, $\theta = \frac{\lambda - \mu + \sqrt{\left(\lambda - \mu \right)^2 + 4 \left(k - \mu \right)}}{2}$ and $\tau = \frac{\lambda - \mu - \sqrt{\left(\lambda - \mu \right)^2 + 4 \left(k - \mu \right)}}{2}$. Their multiplicites are given by $m_\theta = -\frac{\left(n - 1 \right) \tau + k}{\theta - \tau}$ and $m_\tau = \frac{\left(n - 1 \right) \theta + k}{\theta - \tau}$, respectively. > Fill in details on multiplicities #### Theorem If $\Gamma$ is a connected regular graph, then $\Gamma$ is strongly regular if and only if it has precisely 3 distinct eigenvalues. ### Some example of strongly regular graphs - Latin square graphs - Line graphs of $K_n$ - Paley graphs ### The Schur product Given two matrices $M$ and $N$ with the same dimensions, the *Schur product* of $M$ and $N$, denoted by $M \circ N$, is the matrix resulting from entry-wise multiplication of $M$ and $N$. That is to say, the $\left(i, j \right)$-entry of $M \circ N$ is equal to the product of $M_{i, j}$ and $N_{i, j}$. #### Example Suppose $A = \begin{bmatrix} -8 & 8 \\ 7 & -5 \end{bmatrix}$ and $B = \begin{bmatrix} -4 & -5 \\ 9 & 9 \end{bmatrix}$. Then the Schur product of $A$ and $B$ is given by $A \circ B = \begin{bmatrix} 32 & -40 \\ 63 & -45 \end{bmatrix}$. The *Schur product theorem* asserts that if $M$ and $N$ are positive semi-definite matrices, then $M \circ N$ is also positive semi-definite. ### The Bose-Mesner algrebra for strongly regular graphs Suppose $\Gamma$ is a strongly regular graph with parameters $\left(n, k, \lambda, \mu \right)$ and eigenvalues $k$, $\lambda$ and $\mu$. The *Bose-Mesner Algebra* $\mathfrak{A}$ of $\Gamma$ is the algebra consisting of all linear combinations of $A$, $I$ and $J$, where $I$ is the $n \times n$ identity matrix, $J$ is the $n \times n$ matrix in which every entry is $1$, and $A$ is the adjacency matrix of $\Gamma$. Consider the basis $\left\{E_0, E_1, E_2 \right\}$ of $\mathfrak{A}$, where $E_0 = \frac{1}{n} J$, $E_1 = \frac{1}{\theta - \tau} \left(A - \tau I - \frac{k - \tau}{n} J \right)$, $E_2 = - \frac{1}{\theta - \tau} \left(A - \theta I - \frac{k - \theta}{n} J \right)$. Given any $i, j \in \left\{0, 1, 2 \right\}$, we can express the Schur product of $E_i$ and $E_j$ in this basis as $E_i \circ E_j = \sum_{k=0}^2 q_{i, j}^k E_k$ for some constants $q_{i, j}^0, q_{i, j}^1, q_{i, j}^2$. The Krein conditions can be proven using the fact that these constants must be real and non-negative. ### Krein conditions The *Krein conditions* are additional feasibility constraints. They assert that for any strongly regular graph with parameters $\left(n, k, \lambda, \mu \right)$, the following inequalities hold. $$\left(\theta + 1 \right) \left(k + \theta + 2 \theta \tau \right) \leqslant \left(k + \lambda \right) \left(\tau + 1 \right)^2,$$ $$\left(\tau + 1 \right) \left(k + \tau + 2 \theta \tau \right) \leqslant \left(k + \tau \right) \left(\theta + 1 \right)^2.$$ #### Theorem (Cameron, Goethals, Seidel 1977) If $\Gamma$ is an srg with $q_{11}^1=0$ or $q_{22}^2=0$, then for each vertex $x$, the induced subgraphs on $\Gamma_1(x)$ and $\Gamma_2(x)$ are srgs, complete, or empty. Example: Gewirtz graph ### Ratio bounds for cliques and cocliques A *clique* of a graph is a subset $S$ of the vertices such that any two distinct vertices in $S$ are adjacent. A *coclique* is a subset $S$ of the vertices such that any two distinct vertices in $S$ are not adjacent. Suppose $\Gamma$ is a strongly regular graph with parameters $\left(v, k, \lambda, \mu \right)$, and let $\tau$ be the smallest eigenvalue of $\Gamma$. Then the following theorems impose bounds on the sizes of cliques and cocliques. The *ratio bound for cliques* asserts that the size of any clique of $\Gamma$ is at most $1 - \frac{k}{\tau}$, and the *ratio bound for cocliques* asserts that the size of any coclique of $\Gamma$ is at most $\frac{v}{1 - \frac{k}{\tau}}$. It follows immediately from these bounds that if a clique and coclique have sizes $a$ and $b$ respectively, then $ab \leqslant n$. > Add more details here Clique-coclique theorem Designs --- An *incidence structure* is a 3-tuple $\left(\mathcal{P}, \mathcal{B}, \bf{I} \right)$ where $\mathcal{P}$ and $\mathcal{B}$ are sets, and $\bf{I}$ is a relation between them. The elements of $\mathcal{P}$ are known as *points*, the elements of $\mathcal{B}$ are known as *blocks*, and the elements of $\bf{I}$ (when considered as a subset of $\mathcal{P} \times \mathcal{B}$) are known as *flags*. If $p \sim B$ (that is, if $\left(p, B \right) \in \bf{I}$) for some point $p$ and block $B$, then $p$ and $B$ are said to be *incident*. Typically, blocks are considered as subsets of $\mathcal{P}$ that contain precisely the points with which they are incident. In other words, if $B \in \mathcal{B}$ and $p \in \mathcal{P}$, then $p \in B$ if and only if $p \sim B$. Of course, it is possible that two blocks are associated with the same subset of $\mathcal{P}$, since they may be incident on the same points. The number of points and the number of blocks in an incidence structure are denoted by $v$ and $b$, respectively. The *complement* of an incidence structure $\left(\mathcal{P}, \mathcal{B}, \bf{I} \right)$ is the incidence structure $\left(\mathcal{P}, \mathcal{B}, \bar{\bf{I}} \right)$, where $\bar{\bf{I}}$ denotes the complement of $\bf{I}$ in $\mathcal{P} \times \mathcal{B}$. Hence a point $p$ and a block $B$ are incident in the complement of $\left(\mathcal{P}, \mathcal{B}, \bf{I} \right)$ if and only if they are not incident in $\left(\mathcal{P}, \mathcal{B}, \bf{I} \right)$. The *incidence matrix* $N$ of an incidence structure whose points and blocks are ordered is a $v \times b$ matrix whose $(i,j)$-entry is a $1$ if the $i$th point is incident on the $j$th block, or $0$ otherwise. It is straightforward to see that $(i,j)$-entry of $N N^T$ is the number of blocks that contain both the $i$th and $j$th points, and that the $(i,j)$-entry of $N^T N$ is the number of points that are contained in both the $i$th and $j$th blocks. A *linear space* is an incidence structure in which every block contains at least two points, and any two points are incident on exactly one block. The blocks in a linear space are referred to as *lines*. ### Theorem Let $\left(\mathcal{P}, \mathcal{B}, \bf{I} \right)$ be a linear space. Then $b = 1$ or $b \geqslant v$. Also, if $b = v$, then any two lines intersect at exactly one point. #### Proof Observe that no two lines can intersect at more than one point, or their intersection points violate the condition that any two points lie on exactly one line. Let $\left| p\right|$ denote the number of lines incident on the point $p$, for any $p \in \mathcal{P}$. Similarly, let $\left| b\right|$ denote the number of points incident on the line $b$, for any $b \in \mathcal{B}$. Note that for any $p \in \mathcal{P}$ and $B \in \mathcal{B}$ such that $p \notin B$, we have $\left|p \right| \geqslant \left|B \right|$, since for each point $q$ in $B$ there is a line $B_q$ containing $p$ and $q$ (and the $B_q$ are distinct, since $B$ and $B_q$ can intersect only once (at $q$). Note also that if $\left|p \right| = \left|B \right|$, then every line containing $p$ is one of the $B_q$, and hence every line containing $p$ intersects $B$. Assume $1 < b \leqslant v$. Then $$1 = \frac{1}{v} \sum_{p \in \mathcal{P}} 1 = \frac{1}{v} \sum_{p \in \mathcal{P}} \frac{1}{b - \left|p \right|} \sum_{B \not\ni p} 1 = \sum_{p \in \mathcal{P}} \sum_{B \not\ni p} \frac{1}{vb - v \left|p \right|} \geqslant \sum_{p \in \mathcal{P}} \sum_{B \not\ni p} \frac{1}{vb - b \left|B \right|}\\ = \sum_{B \in \mathcal{B}} \sum_{p \notin \mathcal{P}} \frac{1}{vb - b \left|B \right|} = \frac{1}{b} \sum_{B \in \mathcal{B}} \frac{1}{v - \left|B \right|} \sum_{p \notin B} 1 = \frac{1}{b} \sum_{B \in \mathcal{B}} 1 = 1.$$ Hence we must have $v = b$, and also $\left|p \right| = \left|B \right|$ whenever $p \notin B$. Therefore if two lines $B$ and $B'$ do not intersect, then we can choose a point $p \in B'$, and then conclude that since $\left|p \right| = \left|B \right|$, every line containg $p$ intersects $B$. But then $B'$ intersects $B$, a contradiction. Therefore, if $1 < b \leqslant v$, then $b = v$ and any two lines intersect at exactly one point. This is sufficient to prove the theorem. $\square$ A *$t$-$(v, k, \lambda)$ design* (also called a *$t$-design*) is an incidence structure with $v$ points such that every block contains $k$ points, and any set of $t \leqslant k$ points is contained in exactly $\lambda \geqslant 1$ blocks. ### Theorem (*) For any $t$-$(v, k, \lambda)$ design, $$b = \lambda {v \choose t} / {k \choose t}.$$ #### Proof Let $n$ be the number of pairs $\left(B, T \right)$ such that $B$ is a block and $T$ is a set of $t$ points in $B$. For each block $B$, there are $k \choose t$ possible choices of $T$, hence $n = b {k \choose t}$. Also, there are $v \choose t$ sets of $t$ points, and for each of these there are $\lambda$ blocks that contain all of them. Hence $n = {v \choose t} \lambda$. It follows that $b {k \choose t} = {v \choose t} \lambda$, and the result follows. $\square$ ### Theorem (**) Let $\mathcal{D}$ be a $t$-$(v, k, \lambda)$ design, and let $i \in \mathbb{N}$ such that $i \leqslant t$. Then every set of $i$ points is contained in exactly $b_i$ blocks, where $$b_i = \lambda {v - i \choose t - i} / {k - i \choose t - i}.$$ #### Proof Let $I$ be a set of $i$ points, and let $n$ be the number of pairs $\left(B, T \right)$ such that $B$ is a block and $T$ is a set of $t$ points such that $I \subseteq T \subseteq B$. Let $b_i$ be the number of blocks containing all the points in $I$. For each of these blocks $B$, there are $k - i \choose t - i$ possible choices of $T$ (since $i$ of the points in $T$ are already known), hence $n = b_i {k - i \choose t - i}$. Also, there are $v - i \choose t - i$ sets of $t$ points that contain all the points in $I$, and for each of these there are $\lambda$ blocks that contain all of them. Hence $n = {v \choose t} \lambda$. It follows that $b_i {k - i \choose t - i} = {v - i \choose t - i} \lambda$, and the result follows. $\square$ ### Corollary Every $t$-design $\mathcal{D}$ is also an $i$-design for all positive integers $i \leqslant t$. #### Proof Let $i \in \mathbb{N}$ such that $i \leqslant t$. It follows from the previous theorem that every set of $i$ points is contained in the same number of blocks. This means that $\mathcal{D}$ is an $i$-design. $\square$ Since every $t$-design is also a $1$-design, it follows that the number of blocks containing a given point does not depend on the choice of point. This number is denoted by $r$. ### Theorem (***) If $\mathcal{D}$ is a $2$-design, then $$bk = vr$$ and $$\lambda \left(v - 1 \right) = r \left(k - 1 \right).$$ #### Proof The second equation follows immediately from Theorem (**), after inserting $t = 2$, $i = 1$ and $b_1 = r$. If we insert $t = 2$ into Theorem (*), then we find $$b = \lambda \frac{v \left(v-1 \right)}{2} / \frac{k \left(k-1 \right)}{2} = \frac{\lambda \left(v-1 \right)}{k-1} \frac{v}{k} = r \frac{v}{k}$$ having used the second equation in the final step. This rearranges to give the first equation. $\square$ In a $2$-design, the number of blocks that contain both the $i$th and $j$th points is $\lambda$ whenever $i \neq j$, or $r$ whenever $i = j$. Hence we have $$N N^T = \lambda J + \left(r - \lambda \right)I$$ if $N$ is the incidence matrix of a $2$-design, and $J$ is the $v \times v$ matrix whose entries are all $1$. ### Fisher's inequality If a $2$-$(v, k, \lambda)$ design has $v > k$, then $b \geqslant v$. #### Proof Since $v > k$, it follows from the second equation of Theorem (***) that $r > \lambda$. The eigenvalues of the matrix $J$ are $0$ and $v$. Since any eigenvector of $J$ is also an eigenvector of $I$, the eigenvalues of $N N^T = \lambda J + \left(r - \lambda \right)I$ must be $\left(r - \lambda \right)$ and $\lambda v + \left(r - \lambda \right)$. Neither of these eigenvalues are equal to $0$ since $r > \lambda$, so the matrix $N N^T$ is invertible and hence has full rank (rank $v$). Thus we have $$v = \mathrm{rank}(N N^T) \leqslant \mathrm{rank}(N) \leqslant b. \square$$ > Mention Keevash here > Do quasisymmetric designs Codes --- A *code* is a subset $C$ of a set $S^n$, where $S$ is a finite set known as an *alphabet* and $n$ is an integer known as the *length* of the code. The elements of a code $C \subseteq S^n$ are known as *codewords*, the elements of $S^n$ are known as words, and the elements of the alphabet $S$ are known as *symbols*. A *binary code* is a code with alphabet $S = \left\{0, 1 \right\}$, and a *ternary code* is a code with alphabet $S = \left\{0, 1, 2 \right\}$. The *distance* between two words $x, y \in S^n$ is defined by the function $$d(x, y) = \left| \left\{i \in \left\{1, 2, \ldots, n\right\} \mid x_i \neq y_i \right\} \right|.$$ It is clear that $d(x, y) = d(y, x)$, and that $d(x, y) > 0$ with equality if and only if $x = y$. The function $d$ also satisfies the triangle inequality, since if you modify $a$ coordinates of a word, and then modify $b$ coordinates of the newly obtained word, then you have changed at most $a + b$ coordinates in total from the original word. Hence $d$ satisfies the requirements of a metric. This means we can define the ball centred on the word $x \in S^n$ with radius $r \in \left\{0, 1, 2,\ldots \right\}$ as $$B_r(x) = \left\{y \in S^n : d(x, y) \leq r \right\}.$$ The *minimum distance* $d$ of a code $C$ is defined as the smallest possible distance between two distinct codewords. That is, $$d = \mathrm{min}\{d(x, y) \mid x, y \in C,\ x \neq y \}.$$ A *linear code* is a code $C$ whose alphabet is a finite field $F$, and where $C$ is a subspace of $S^n = F^n$. For a linear code, the *weight* of each word is its distance from the zero vector. This is denoted by the function $$w(x) = d(x, 0)$$ for all $x \in F^n$. ### Theorem The minimum distance $d$ of a linear code $C \subseteq F^n$ is the smallest weight of the codewords other than $0$. That is, $$d = w_\mathrm{min} = \mathrm{min} \{w(x) \mid x \in C \setminus \left\{0 \right\} \}.$$ #### Proof Let $x \neq 0$ be a codeword such that $w(x) = w_\mathrm{min}$. Then $d \leqslant d(x, 0) = w(x) = w_\mathrm{min}$. Let $x_1, x_2 \in C$ be distinct codewords such that $d(x_1, x_2) = d$. For each index $i \in \left\{1, 2, \ldots, n \right\}$, the $i$th coordinate of $x_1 - x_2$ is non-zero if and only if $x$ and $y$ differ in the $i$th coordinate. Hence $w_\mathrm{min} \leqslant w(x_1 - x_2) = d(x_1 - x_2, 0) = d(x_1, x_2) = d$. So $d = w_\mathrm{min}$ as required. $\square$ The *covering radius* $\rho(C)$ of a code $C$ is the maximum distance between a word and its closest codeword. More precisely, $$\rho(C) = \mathrm{max}\{\mathrm{min}\{d(x, y) \mid y \in C \} \mid x \in S^n \}.$$ A code is called a *perfect code* if there is some positive integer $e$ such that $$\left| \left\{y \in C \mid d(x, y) \leqslant e \right\} \right| = 1$$ for every word $x \in S^n$. In other words, a code is perfect if every word is within a distance $e$ of exactly one codeword for some positive integer $e$. ### Sphere packing theorem Let $C$ be a code of length $n$ with $q$ symbols and minimum distnace $d$. If $e$ is a positive integer such that $d > 2e$, then $$\left|C \right| \sum_{i=0}^e {n \choose i} \left(q-1 \right)^i \leqslant q^n.$$ #### Proof Let $x \in C$ be a codeword, and let $i \leqslant e$ be a positive integer. Consider the set $S_i$ of all words that are a distance of $i$ from $x$. There are $n \choose i$ combinations of coordinates in which a word in $S_i$ can differ from $x$, and for each of these combinations, there are $\left(q-1 \right)$ possible symbols in each of the $i$ coordinates which differ from $x$. Hence the number of words in $S_i$ is ${n \choose i} \left(q-1 \right)^i$, and it follows that $$\left|B_e(x) \right| = \sum_{i=0}^e {n \choose i} \left(q-1 \right)^i.$$ Since $d > 2e$, no two balls of radius $e$ that are centred on codewords can overlap. Hence the total number of words in all $C$ of these balls is given by $$\left|C \right| \sum_{i=0}^e {n \choose i} \left(q-1 \right)^i.$$ Clearly this value cannot exceed the total number of words $q^n$, hence the sphere packing theorem holds. $\square$ Suppose $C$ is a linear code of dimension $k$. A *generator matrix* is a $k \times n$ matrix $G$ whose rows span the set of codewords $C$. Since $C$ has dimension $k$, the rows of $G$ form a basis for $C$. Using elementary row operations, it is possible to find a generator matrix of the form $\left[I\ \mid\ P \right]$ where $I$ is the $k \times k$ identity matrix, and $P$ is a $k \times \left(n-k \right)$ matrix.  Association schemes --- If $k$ is a positive integer, then a *d-class association scheme* consists of a set $\Omega$ and a set of nonempty binary relations $R_0, R_1, \ldots, R_d$ on $\Omega$ (these can be viewed as subsets of $\Omega \times \Omega$), such that 1. the relations $R_0, R_1, \ldots, R_d$ are symmetric, meaning $\left(x, y \right) \in R_i \iff \left(y, x \right) \in R_i$ for all $i$, 2. the relations $R_0, R_1, \ldots, R_d$ form a partition of $\Omega \times \Omega$, 3. $R_0$ is the identity relation, meaning $\left\{\left(x, x \right) \mid x \in \Omega \right\}$, and 4. for all $i, j, k \in \left\{0, 1, \ldots, d \right\}$, there exists an integer $p^k_{ij}$ such that $$\left|\left\{z \in \Omega \mid \left(z, x\right) \in R_i, \left(z, y\right) \in R_j \right\}\right| = p^k_{ij}$$ for every pair of vertices $\left(x, y\right) \in R_k$. The elements of $\Omega$ are known as *vertices*, and two vertices $x, y \in \Omega$ are said to be *$i$th associates* if $\left(x, y\right) \in R_i$. The integers $p^k_{ij}$ are known as *parameters* or *intersection numbers*. > **Johnson scheme:** $J(v,k)$, with $k\leqslant v/2$. The vertices are the $k$-subsets of $\{1,\ldots,v\}$, and we define the relation $R_i$ as 'differs in $i$ elements`. > **Hamming scheme:** $H(n,q)$. The vertices are the $n$-tuples of elements from an *alphabet* $Q$ of size $q$. We defined the relation $R_i$ be 'differs in $i$ coordinates'. Since $R_0$ is the identity relation, the intersection number $p^0_{ij} = 0$ whenever $i \neq j$, and $p^0_{ii}$ denotes the number of $i$th-associates of any given vertex. This is also denoted by $n_i$. The integers $n_0, n_1, \ldots, n_d$ are known as the *degrees* of the association scheme. The only $0$th-associate of a vertex $x \in \Omega$ is itself, so $n_0 = 1$. Moreover, the degrees add to $\left|\Omega \right|$ since every vertex is an $i$th-associate of $x$ for exactly one $i \in \left\{0, 1, \ldots, d \right\}$. #### Theorem Suppose $\Gamma$ is a strongly regular graph with parameters $\left(n, k, \lambda, \mu \right)$. Then the vertex set $\mathrm{V}(\Gamma)$, relations $R_1 = \mathrm{E}(\Gamma)$ and $R_2 = \left\{\left(x, y \right) \in \mathrm{V}(\Gamma) \times \mathrm{V}(\Gamma) \mid x \neq y,\ \left(x, y \right) \notin \mathrm{E}(\Gamma) \right\}$, and the identity relation $R_0$, together form a $2$-class association scheme with $n_1 = k$, $n_2 = n - k - 1$, $p^1_{11} = \lambda$ and $p^2_{11} = \mu$. #### Proof The relations $R_0, R_1, R_2$ are symmetric since $\mathrm{E}(\Gamma)$ is symmetric. Every vertex has $k$ neighbours in $\Gamma$ and hence $k$ $1$st-associates. Similarly, for each vertex $x$ there are $\left(n - k - 1 \right)$ other vertices that are not adjacent to $x$, hence $x$ has $\left(n - k - 1 \right)$ $2$nd-associates. Suppose $(x, y) \in R_1$. Then $x$ and $y$ are adjacent in $\Gamma$. Hence there are $\lambda$ vertices adjacent to both $x$ and $y$, which means there are $\lambda$ vertices that are $1$st-associates with $x$ and $y$, so $p^1_{11} = \lambda$. Similarly, $p^2_{11} = \mu$, and the other intersection numbers can be calculated from the parameters of the graph. $\square$ If the orbitals of a transitive permutation group $G$ are symmetric, then they form an association scheme when considered as relations on $G$. ### Intersection matrices If a $d$-class association scheme has an arbitrarily-ordered vertex set $\Omega$ of size $N$, then the *association matrices* of the association scheme are the $N \times N$ matrices $A_0, A_1, \ldots, A_d$ where the $\left(x, y \right)$-entry of $A_i$ is $1$ if the $x$th and $y$th elements of $\Omega$ are $i$th-associates, and $0$ otherwise. Since any vertices $x, y \in \Omega$ are $i$th associates for exactly one $i \in \left\{0, 1, \ldots, d \right\}$, it follows that $\sum_{i=0}^d A_i = J$, where $J$ is the $N \times N$ matrix in which every entry is $1$. It is easy to see that the association matrix $A_i$ is the adjacency matrix of the graph with vertex set $\Omega$ and edge set $R_i$. The *intersection matrices* of an association scheme are the $\left(d+1 \right) \times \left(d+1 \right)$ matrices $L_0, L_1, \ldots, L_d$ such that the $\left(k, j \right)$-entry of $L_i$ is $p^k_{ij}$. ### The Bose-Mesner algebra Given a $d$-class association scheme, the *Bose-Mesner algebra* $\mathfrak{A}$ consists of the linear span over $\mathbb{R}$ of the association matrices, equipped with the usual addition and multiplication operations for matrices. While the natural basis for this algebra is the set of association matrices, there is also a basis of minimal idempotents $\left\{E_0, E_1, E_2, \ldots, E_d \right\}$ which sum to the identity matrix $I$, square to themselves, and such that $E_i E_j = 0$ whenever $i \neq j$. For example, if we let $n = \left|\Omega \right|$, then one of the minimal idempotents is $\frac{1}{n} J$. Conventionally it is taken to be $E_0$. It is an idempotent (that is, it squares to itself) since $$\left(\frac{1}{n} J \right) \left(\frac{1}{n} J \right) = \frac{1}{n^2} J^2 = \frac{1}{n^2} \left(nJ \right) = \frac{1}{n} J.$$ Since $\left\{E_0, E_1, E_2, \ldots, E_d \right\}$ is a basis for $\mathfrak{A}$, it is possible to express each of the association matrices $A_j$ as a linear combination of the minimal idempotents $E_i$. Define the $\left(d+1 \right) \times \left(d+1 \right)$ matrix $P$ such that $$A_j = \sum_{i=0}^d P_{ij} E_i.$$ Similarly, each $E_j$ can be expressed as a linear combination of the association matrices $A_i$, so we can define the $\left(d+1 \right) \times \left(d+1 \right)$ matrix $Q$ such that $$E_j = \frac{1}{n} \sum_{i=0}^d Q_{ij} A_i.$$ Note that there is a scale factor of $\frac{1}{n}$ used in the definition here. Now, given any association matrix $A_j$ and any minimal idempotent $E_i$, we see that $$A_j E_i = \sum_{l=0}^d P_{lj} E_l E_i = \sum_{l=0}^d P_{lj} \delta_{li} E_i = P_{ij} E_i$$ where $\delta_{ij}$ is equal to $1$ if $i = j$, and $0$ otherwise. It follow that $P_{ij}$ is an eigenvalue of the association matrix $A_j$, and each column of $E_i$ is an eigenvector with eigenvalue $P_{ij}$. Since $i$ was chosen arbitrarily, the eigenvalues of $A_j$ are given by each of the entries in the $j$th column of $P$. For this reason, $P$ is known as the *matrix of eigenvalues* of the association scheme. The matrix $Q$ is known as the *matrix of dual eigenvalues*. Given an association matrix $A_j$, the multiplicity of the eigenvalue $P_{ij}$ is denoted by $m_i$. Since the corresponding eigenspace is the columnspace of $E_i$, it follows that $m_i$ is the just rank of $E_i$, and hence it does not depend on the choice of $j$. The columns of $P$ satisfy the following orthogonality relation for any $i, j \in \left\{0, 1, 2, \ldots, d \right\}$: $$\sum_{l=0}^d m_l P_{li} P_{lj} = n n_i \delta_{ij}.$$ Similarly, the columns of $Q$ satisfy the following orthogonality relation for any $i, j \in \left\{0, 1, 2, \ldots, d \right\}$: $$\sum_{l=0}^d n_l Q_{li} Q_{lj} = n m_i \delta_{ij}.$$ _Theorem:_ The intersection algebra is isomorphic to the Bose-Mesner algebra. ### Krein parameters Given a $d$-class association scheme, we can also consider the Bose-Mesner algebra $\mathfrak{A}$ under matrix addition and the Schur product (instead of matrix addition and matrix multiplication). In this case, the association matrices $\left\{A_0, A_1, A_2, \ldots, A_d \right\}$ now form a basis of minimal idempotents. To see that they are idempotents, recall that every entry of each association matrix $A_i$ is either a $0$ or a one, so $A_i \circ A_i = A_i$ since $0^2 = 0$ and $1^2 = 1$. Also recall that two distinct association matrices cannot both contain a $1$ in the same entry, so $A_i \circ A_j = 0$ whenever $A_i \neq A_j$. Now, take two matrices $E_i$ and $E_j$ as defined in the previous section, and consider their Schur product. Multiplying by $n = \left|\Omega \right|$ and expressing the result in the basis $\left\{E_0, E_1, E_2, \ldots, E_d \right\}$, we have $$n E_i \circ E_j = \sum_{l=0}^d q^k_{ij} E_k,$$ where $q^k_{ij} \in \mathbb{R}$ for each $i, j, k \in \left\{0, 1, 2, \ldots, d \right\}$. The constants $q^k_{ij}$ are known as the *Krein parameters* of the association scheme. These Krein parameters are always greater than or equal to zero. Two $d$-class association schemes are said to be *dual* to each other if the intersection numbers $p^k_{ij}$ of the first are equal to the Krein parameters $q^k_{ij}$ of the second. If this is the case, then the intersection numbers of the second will also be equal to the Krein parameters of the first. An association scheme that is dual to itself is said to be *self-dual*. ### Metric and polynomial association schemes In some association schemes, such as the Hamming scheme, two points declared to be $i$th-associates if the distance between them is equal to $i$, using some distance metric. These association schemes must have $p^l_{ij} = 0$ whenever the integers $i, j, l$ violate the triangle inequality, and $p^l_{ij} > 0$ whenever $l = i+j$. Any association scheme for which these two properties hold is known as a *metric* association scheme. An association scheme is said to be *cometric* if these same two properties hold for the Krein parameters $q^l_{ij}$ rather than the intersection numbers $p^l_{ij}$. A *$P$-polynomial* association scheme is an association scheme such that, for all $i, j \in \left\{0, 1, 2, \ldots, k \right\}$, there exist constants $c_i \in \mathbb{R}$ and polynomials $f_j$ of degree $j$ satisfying $f_j{\left(c_i \right)} = P_{ij}$, where $P$ is the matrix of dual eigenvalues of the association scheme. If this property holds for the matrix of dual eigenvalues $Q$ instead of $P$, then the association scheme is known as a *$Q$-polynomial* association scheme. #### Theorem An association scheme is a metric association scheme if and only if it is a $P$-polynomial association scheme. Similarly, an association scheme is a cometric association scheme if and only if it is a $Q$-polynomial association scheme. ### Delsarte's linear programming bound Suppose we have a $k$-class association scheme, as well as a non-empty subset $X \subseteq \Omega$ of the points. Let $i \in \left\{0, 1, 2, \ldots, k \right\}$. Recall that the number of $i$th-associates of any point in $\Omega$ is precisely $n_i$. However, the number of $i$th-associates in $X$ of a chosen point in $X$ may vary depending on which point was chosen. For each $i$, let $a_i$ be the average number of $i$th-associates in $X$ of the points in $X$. That is, $$a_i = \frac{\left|\left(X \times X \right) \cap R_i \right|}{\left|X \right|}.$$ Then the *inner distribution* of $X$ is the $\left(k+1 \right)$-dimensional vector whose $i$th coordinate (indexed from $0$) is equal to $a_i$. Note that $a_0 = 1$, since the only $i$th-associate of any given point is itself. Delsarte's linear programming (LP) bound asserts that $aQ \geqslant 0$, where $Q$ is the matrix of dual eigenvalues of the association scheme. It can be used to find the largest possible subset $X \subseteq \Omega$ of the points given some known values of $a_i$. Delsarte's linear programming bound can also be used to obtain an upper bound on the sizes of cliques and cocliques of a graph with vertex set $\Omega$ and edge set equal to some union of the relations $R_i$. For example, suppose we have some set $I \subseteq \left\{1, 2, \ldots, k \right\}$ of integers, and that we wish to determine the largest possible coclique of the graph whose vertex set is $\Omega$ and edge set $\cup_{i \in I} R_i$. A subset $X \subseteq \Omega$ of the points is a coclique if and only if no two vertices in $X$ are $i$th-associates for any $i \in I$. The inner distribution $a$ of $X$ must therefore have a $0$ in its $i$th coordinate for every $i \in I$. The linear programming bound can be used to determine the largest possible sum of the components of $a$, which gives a limit on the size of the cocliques of $\Gamma$. An upper bound on clique sizes of such a graph can also be determined in this way, since the cliques of a graph are precisely the cocliques of the complement graph. For the graph $\Gamma$ mentioned above, its complement $\bar \Gamma$ is simply the graph with vertex set $\Omega$ and edge set $\cup_{i \in \bar I} R_i$, where $\bar I = \left\{1, 2, \ldots, k \right\} \setminus I$. Hence using Delsarte's linear programming bound to obtain a bound on the sizes of cocliques of $\bar \Gamma$ will yield a bound on the sizes of cliques of $\Gamma$. ### The code-anticode theorem _Theorem:_ Let $S$ and $S'$ be an $\mathcal{I}$-code$ and $\mathcal{I'}$-code respectively, with $\mathcal{I}\cup\mathcal{I}'=\{1,\ldots,d\}$. Then $|S|\cdot |S'|\leqslant |\Omega|$, with equality if and only if $|S\cap S'|=1$. ### The design-antidesign theorem _Theorem:_ Let $S$ and $S'$ be a $\mathcal{T}$-design$ and $\mathcal{T'}$-design respectively, with $\mathcal{T}\cup\mathcal{T}'=\{1,\ldots,d\}$. Then $|S|\cdot |S'|\geqslant |\Omega|$, with equality if and only if $|S\cap S'|=1$. ### Designs revisited inclusion matrices Let $T=\{1,\ldots,t\}$. A $T$-design of $J(v,k)$ is a combinatorial $t$-design, and conversely. ### Roos' theorem _Theorem:_ If $S,S'$ are design-orthogonal subsets of an association scheme $\mathcal{A}$ (with vertices $\Omega$), then $|S\cap S'|=\frac{|S||S'|}{|\Omega|}$. We can generalise to vectors: $$u\cdot v=\frac{(u.j)(v.j)}{|\Omega|}.$$ Examples ...  ### Spherical codes  The seminal paper on spherical codes was Delsarte, Goethals, Seidel (1977). Let $L$ be a subset of the interval $[-1,1)$ of the real number line. A finite nonempty set $\mathcal{C}$ of unit vectors in $\mathbb{R}^n$ is called a _spherical $L$-code_, if $\langle x,y\rangle \in L$ for any pair of vectors $x,y\in \mathcal{C}$. Note that if $L = \{-\alpha,\alpha\}$, then a spherical $L$-code corresponds to a set of _equiangular lines_ with common angle $\arccos \alpha$, where $\alpha\in [0, 1)$. For $L = [-1, \beta]$, finding the maximum size of a spherical $L$-code is equivalent to the problem of finding non-overlapping spherical caps of angular radius $\tfrac12 \arccos \beta$. We will see that cliques of association schemes often yield spherical $L$-codes. __Theorem:__ Let $\mathcal{A}$ be a $d$-class association scheme on an $n$-element set, with adjacency matrices $\{I,A_1,\ldots,A_d\}$. Let $\mathcal{I}\subset \{1,\ldots,d\}$. Let $j\in\{1,\ldots,d\}$ such that $Q_{0j}\ne Q_{tj}$ for all $t\in \mathcal{I}$. Let $$L:=\{ Q_{tj} / Q_{0j} : t \in \mathcal{I}\}.$$ Then an $\mathcal{I}$-code of size $r$ corresponds to a spherical $L$-code of $\mathbb{R}^m$, where $m=Q_{0j}$, of size $r$. _Proof:_ Let $\lambda$ be the eigenvalue of $A$ corresponding to $E_j$ (so $AE_j=\lambda E_j$), and let $X$ be the graph having $A$ as adjacency matrix. Let $m$ be the rank of $E_j$. Since $E_j$ is positive semidefinite, there exists an $n\times m$ matrix $Z$ such that $E_j=ZZ^\top$. Suppose we have two vectors $z_h$ and $z_i$, two different rows of $Z$, that are equal as coordinate vectors. Then in $E_j$, we have a $2\times 2$-submatrix about the diagonal: $$\begin{bmatrix}z_h\cdot z_h&z_h\cdot z_i\\ z_i\cdot z_h&z_i\cdot z_i\end{bmatrix}.$$ Let $A_t$ be the adjacency matrix which has a 1 in the $(h,i)$ entry. Recall that $$E_j= \frac{1}{n}\left(Q_{0j}I + Q_{1j}A_1 +\cdots +Q_{d j} A_d\right).$$ Then $z_h\cdot z_h=z_i\cdot z_i=\frac{1}{n} Q_{0j}$ (the coefficient of $I$ in the expression for $E_j$) and $z_h\cdot z_i=z_i\cdot z_h=\frac{1}{n} Q_{tj}$ (the coefficient of $A_t$ in the expression for $E_j$). Since $z_h=z_i$, we have $Q_{0j}=Q_{tj}$. Therefore, the first condition ensures that all rows of $Z$ pertaining to the $\mathcal{I}$-code are distinct as vectors. Next, let $$\mathcal{C}:=\left\{ \sqrt{ \frac{n}{m} }z_i : i\in \mathcal{I}\right\}.$$ Then as we have already observed, $$\begin{align*} \left( \sqrt{ \frac{n}{m} }z_i\right) \cdot \left( \sqrt{ \frac{n}{m} }z_i\right)=\frac{n}{m} (z_i\cdot z_i)=\frac{n}{m} (E_j)_{i,i}=1. \end{align*}$$ Moreover, $$\begin{align*} \left( \sqrt{ \frac{n}{m} }z_h\right) \cdot \left( \sqrt{ \frac{n}{m} }z_i\right) &=\frac{n}{m} (z_h\cdot z_i)\\ &=\frac{n}{m} (E_j)_{h,i}\\ & =\frac{1}{m} Q_{tj} \end{align*}$$ where $A_t$ is the adjacency matrix which has a 1 in the $(h,i)$ entry. Therefore, the pairwise scalar products from $\mathcal{C}$ are a subset of $L$. --- __Corollary [Example 4.4 of DGS]__ Suppose $\beta$ satisfies $-1\le \beta < 0$, and let $L$ be any subset of the interval $[-1,\beta]$. Then any $L$-code of $\mathbb{R}^n$ has size at most $1-1/\beta$. > Example: > Below is the matrix of eigenvalues $P$ for the collinearity/non-collinearity pair of strongly regular graphs of a generalised quadrangle of order $(s,t)$: > $$P= \begin{bmatrix} 1 & s(t+1) & s^2t\\ 1 & s-1 & -s \\ 1 & -t-1 & t \end{bmatrix}$$ So the matrix $Q$ of dual eigenvalues is $$Q= \begin{bmatrix} 1 & \frac{st (s+1) (t+1)}{s+t} & \frac{s^2 (s t+1)}{s+t} \\ 1 & \frac{\left(s^2-1\right) t}{s+t} & -\frac{s (s t+1)}{s+t} \\ 1 & -\frac{(s+1) (t+1)}{s+t} & \frac{s t+1}{s+t} \\ \end{bmatrix}$$ Take the minimal idempotent $E_1$ with rank $m=\frac{st (s+1) (t+1)}{s+t}$. The non-collinearity graph is the third adjacency matrix here, and so a clique for the non-collinearity graph yields an $L$-code where $$L:=\left\{ \frac{-1}{st }\right\}.$$ Therefore, using the Corollary above, a partial ovoid of a generalised quadrangle has size at most $1+st$. Other nice results: __Theorem [Neumaier 1981]__ Let $\mathcal{C}$ be a spherical $A$-code in $\mathbb{R}^d$. If $A=\{\beta,\alpha\}$ and $-1\leqslant \beta<\alpha<1$, then $\mathcal{C}\leqslant 2d+1$ unless $(1-\alpha)/(\alpha-\beta)\in\mathbb{Z}$. __Theorem [Balla, Dräxler, Keevash, Sudakov 2017]__ Let $\mathcal{C}$ be a spherical $A$-code in $\mathbb{R}^d$. If $A=[-1,-\beta]\cup \{\alpha\}$, where $\beta\in(0,1]$ and $\alpha\in[-1,1)$, then $\mathcal{C}\leqslant 2(1+\max(\frac{\alpha}{\beta},0))d+o(d)$. ### Schurian schemes For Schurian association schemes, there is a connection between irreducible characters of $G$ and minimal idempotents of the association scheme (see also Section 11.11 of Godsil and Meagher's book). Given $\psi\in \mathrm{Irr}(G)$, we have a matrix $M_\psi$ defined by $$(M_\psi)_{g,h}=\psi(gh^{-1}).$$ Then the corresponding minimal idempotent $E_\psi$ is $$E_\psi:=\frac{\psi(1)}{|G|}M_\psi.$$