Glossary

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.

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.

If we replace each relation R_i by its zero-one adjacency matrix A_i, we get an alternative definition. An association scheme is a collection of d+1 symmetric zero-one matrices A = {A₀, A₁, . . . , A_d} satisfying:
(i) A₀ is the identity matrix I;
(ii) the sum of the A_i is the all-ones matrix J;
(iii) the linear space spanned by {A₀, A₁, . . . , A_d} 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.)

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 R_i can also be defined as the relation "x and y are at distance i in the graph R₁". Often,R₁ 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 R_i is the distance-i relation of R₁, a distance-regular graph. Often, R₁ is referred to as the Johnson graph.

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.

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.

An equitable partition of a graph G is a partition {C₁, . . . , C_m} of its vertices such that, for any choice of i and j, all vertices in C_i have the same number of neighbours in C_j. 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:
C_i = { 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 V_j, 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

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, x_i. The edge-difference polynomial, f(x), is the product of (x_i-x_j) over all edges ij of G. The annihilator polynomials are {g_i(x): i} where g_i is the product of (x_i - c) as c ranges over the colours allowable at vertex i. Let I be the ideal generated by the g_i.
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 x_i is less than that of g_i 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[X₁,...,X_n].) 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