Glossary

Last modified: March 29, 2009

algebraic combinatorics is the study of the interaction between algebra (systems of objects endowed with binary operations, e.g., groups, rings, fields, algebras, matrix algebras) and combinatorics (finite or countably infinite arrangements such as binary relations or set systems). For me, a (simple) graph is a symmetric, irreflexive binary relation, or just a bunch of dots joined by lines.

A distance-regular graph is a graph with the following property. Let G have diameter d. For any vertices x and y of G and any integers i, j between 0 and d (inclusive), the number of vertices z at distance i from x and at distance j from y depends only on i, j and k := dist(x,y) and not on the choice of x and y themselves.

This is a natural generalisation of the concept of a distance transitive graph. A graph is distance transitive if its group of automorphisms is transitive on pairs of vertices at distance i for each i from 0 to d, the diameter of G.

A further generalisation is afforded in the notion of an association scheme. Let X be a finite set of size n and let
A = {R0, R1, . . ., Rd} be a set of symmetric relations on X. Call elements x, y of X "i-related" if the ordered pair (x,y) belongs to Ri. Then A is an association scheme if the following conditions are satisfied:
(i) R0 is the identity relation;
(ii) the union of the Ri forms the complete relation X x X;
(iii) For any two elements x and y of X (not necessarily distinct) and any two integers i and j, 0<=i,j<=d, the number of elements z of X which are i-related to x and j-related to y does not depend on the choice of x and y, but only on i, j and that k for which x and y are k-related. A simple example is the association scheme on six points determined by distance along a hexagon or 6-cycle.

If we replace each relation Ri by its zero-one adjacency matrix Ai, we get an alternative definition. An association scheme is a collection of d+1 symmetric zero-one matrices A = {A0, A1, . . . , Ad} satisfying:
(i) A0 is the identity matrix I;
(ii) the sum of the Ai is the all-ones matrix J;
(iii) the linear space spanned by {A0, A1, . . . , Ad} is closed under matrix multiplication.

What I have just given is actually the definition of a symmetric association scheme. Many sources will not require symmety, but will still ensure that the set A is closed under the transpose operation. (Hence the linear algebra in (iii) above is closed under the conjugate transpose.)

I now describe two fundamental examples of association schemes which happen also to be distance-regular graphs.

The Hamming scheme H(n,q) has vertex set X equal to the set of all strings of length n over an alphabet with q symbols. Two strings x and y are defined to be i-related if they differ in i coordinate places. This is the Hamming metric. So Ri can also be defined as the relation "x and y are at distance i in the graph R1". Often,R1 is referred to as the Hamming graph. For q=2, we get the n-cube. Subsets of vertices of the Hamming scheme are codes and orthogonal arrays.

The Johnson scheme J(v,k) has vertex set X equal to the set of all k-subsets of a fixed v-set V. Two k-sets x and y are defined to be i-related if their intersection has k-i elements. This defines a metric. So Ri is the distance-i relation of R1, a distance-regular graph. Often, R1 is referred to as the Johnson graph.

An interesting application of mathematics to modern communications systems is the theory of error-correcting codes. In practical terms, an error-correcting code is a collection of zero-one strings ("words" or "messages") with the property that no two strings in the set look similar. More precisely, C is a collection of n-tuples over the alphabet {0,1} such that any two distinct elements of C differ in at least d places. If we agree to communicate using only messages from C, then we can always detect up to d-1 bit errors in transmission and we can correct [(d-1)/2] errors (where [x] is the greatest integer less than or equal to x).

If all of the strings in the code have the same length (i.e., it is a "block code"), then one can view it as a subset of the vertices of the n-cube. It is advantageous to generalise the concept and say that a code is any subset of the vertices of the Hamming graph. That is, we not only consider 01-strings, but strings over arbitrary finite alphabets.

Let H(n,q) denote the Hamming scheme on the set of all n-tuples over a fixed alphabet of size q. For any non-empty subset C of the vertices, we have the four fundamental parameters of Delsarte.

• minimum distance of C is the minimum of the Hamming distance dist(x,y) as (x,y) ranges over the pairs of distinct elements in C.
• degree of C is the number of distinct non-zero distances which occur among the elements of C:
d(C):=|{ dist(x,y): x, y in C, x neq y}|.
• strength of C is the largest integer t such that, upon restricting to any t coordinates, the codewords of C yield each q-ary t-tuple exactly lambda times for some lambda. (That is, C is an orthogonal array of strength t.)
• dual degree of C is the number of non-trivial eigenspaces of H(n,q) to which the characteristic vector of C is not orthogonal. (See the texts!) If C is a linear code, then -- as expected -- the dual degree is equal to the degree of the dual code of C.

Early in the twentieth century, statisticians (mainly interested in agricultural experiments) introduced the idea of a balanced incomplete block design.

Let V be a finite set of size v and let B be a collection of k-subsets of V (possibly with repeated elements). Then (V,B) is a balanced incomplete block design with parameters (v, |B|, r, k, s) if
(i) evey pair of distinct elements of V occur together in exactly s blocks for some positive integer s;
(ii) every element of V appears in exactly r blocks (elements of B) for some r (note (ii) follows from (i)).

An example with parameters (6,10,5,3,2):
V = {1, 2, 3, 4, 5, 6}
B = {{1,2,3}, {1,2,4}, {1,3,5}, {2,3,6}, {1,4,6},
{1,5,6}, {2,4,5}, {2,5,6}, {3,4,5}, {3,4,6} }

Gradually, combinatorialists have perverted this concept to arrive at the theory of combinatorial designs. The classical examples are the finite projective and affine geometries. Other examples include triple systems and Hadamard designs (essentially Hadamard matrices). In the 1960's, Hanani introduced the more general t-design (in which the t-sets should occur among the blocks equally frequently) and this strengthened the relationship between design theory and finite group theory. Each t-transitive permutation group on the collection of k-sets of {1,2,...,v} determines a t-design. By the way, when t=2, we get the balanced incomplete block designs above. If every block b in B has exactly k elements, then B can be viewed as a subset of the vertices of the Johnson scheme J(v,k). This is more than just a formality. Delsarte showed that a subset B of the vertices of J(v,k) is a t-design if and only if its characteristic vector is orthogonal to the first t eigenspaces of the Bose-Mesner algebra.

A graph G consists of a set V of vertices and a set E of unordered pairs of vertices called edges. Usually, I restrict attention to simple graphs: those where each edge has distinct endpoints and no two edges have the same pair of endpoints. Thus a simple graph is just an irreflexive symmetric binary relation. Associated to every such graph is a symmetric 01-matrix with zero diagonal. I like to study the eigenvalues of this matrix and am interested in the information they give about the graph.

An equitable partition of a graph G is a partition {C1, . . . , Cm} of its vertices such that, for any choice of i and j, all vertices in Ci have the same number of neighbours in Cj. For example, the set of orbits of any group of automorphisms of G form an equitable partition. Many of the objects I study are related to equitable partitions of graphs.

Given any subset C of the vertices of a graph G, the vertex set V of G is partitioned naturally according to distance from C:
Ci = { x : closest vertex to x in C is at distance i}
This is called the distance partition of G with respect to C.

A completely regular code (or "completely regular subset", as it should be called) is a subset C of the vertices of a graph G such that the distance partition of G with respect to C is equitable. Completely regular codes were first studied in the Hamming graphs. This class includes all perfect codes, uniformly packed codes, as well as any subset of an antipodal class in an antipodal distance-regular graph. There is a theorem in the book by Brouwer, Cohen and Neumaier which says something like: "If one forms a graph by taking a partition of a distance-regular graph G with all cells isomorphic and (treating these as vertices of a new graph H) join two cells if they contain adjacent vertices, then this new graph H is distance-regular if and only if each cell is completely regular."

I am also interested in a more general type of subset. Godsil and I call these simple subsets. Let me define them. Let C be a subset of the vertices of a graph G (or an association scheme). For each vertex x in V, build the profile of x: this is a vector of length d+1 (usually, d= diameter(G)) with i-th entry equal to the number of vertices of C which lie at distance i from x. (There is an obvious generalisation to association schemes.) Let R be the matrix whose rows are all distinct profiles as x ranges over the entire vertex set V. (I call R the "reduced outer distribution matrix" of C.) Call C simple if R has full row rank. It is easy to show that every completely regular subset is simple. In my paper with Chris Godsil, a theorem is established which generalises the above result; essentially, one replaces "distance-regular graph" by "association scheme" and replaces "completely regular" by "simple". So, in a sense, the completely regular subsets are the "metric" or "P-polynomial" simple subsets.

In a recent project, I look at designs in association schemes. These cand be defined in two ways, usually. In the algebraic formulation, a T-design is a subset of the vertices whose characteristic vector is orthogonal to the eigenspaces Vj, j in T. (Here, T is any subset of {0,1,...,d}.) In the combinatorial formulation, the concept can usually be described in terms of covering sets inside certain "posets" (partially ordered sets). For these purposes, I define a Q-poset. This poset should have a unique minimal element; its maximal elements should be the vertices of the graph. The elements of the poset should be partitioned into ranks 0,1,...,d with the incidence matrix of objects of rank j versus objects of rank d having the direct sum of the first j+1 eigenspaces as its rowspace. (Such a poset exists, for example, for the Johnson scheme. It is simply the truncated Boolean lattice.)

Stipulation Polynomials
These polynomials arise out of an algebraic approach to graph colouring originated by N. Alon and M. Tarsi.

A list-colouring problem has as input a graph G and, at each vertex of G, a list of allowable colours. The question is: Can G be properly vertex-coloured in such a way that each vertex takes its colour from its prescribed list?

Associate to each vertex i of G an indeterminate, xi. The edge-difference polynomial, f(x), is the product of (xi-xj) over all edges ij of G. The annihilator polynomials are {gi(x): i} where gi is the product of (xi - c) as c ranges over the colours allowable at vertex i. Let I be the ideal generated by the gi.
Alon and Tarsi: G is list-colourable if and only if f does not belong to I. (Beautiful result!)

Now assume G is list-colourable. The coset f+I is uniquely represented by a polynomial F whose degree in xi is less than that of gi for each i. Call F the stipulation polynomial of G. A stipulation is any irreducible factor of F. (I am working over the integers here: F is in Z[X1,...,Xn].) In many cases, each stipulation is the stipulation polynomial of some (edge-induced) subgraph of G (with modified lists of colours). But, this is not always true. Perhaps it is seldom true? I would like to know.

Configurations in Euclidean Space
If S and T are both k-dimensional subspaces of n-dimensional Euclidean space, then, under orthogonal projection onto T, the unit sphere in S maps to an ellipsoid. If this ellipsoid is itself a sphere, then we say that S is isoclinic to T. This relation is in fact symmetric. Also, every space is isoclinic to itself and, if two k-spaces are orthogonal, then they are isoclinic. Wong wrote a long paper on isoclinic spaces in 1960. If two k-dimensional spaces are isoclinic, then there is a well-defined angle between them: its cosine is the radius of the sphere mentioned above. In 1973, Lemmens and Seidel studied the following problem: given n and k, what is the maximum number of k-dimensional subspaces in Rn pairwise isoclinic with the same angle?
Return to my research page.