Yesterday I went to Edinburgh to give a colloquium talk about synchronization, including the recent stuff about butterflies. The day before, I had discussed Artur Schäfer’s work with him, and he expressed a hope that if he went to the Postgraduate Combinatorics Conference (at which I am speaking) I wouldn’t steal his topic! At the same time, I am preparing lectures to my year 5 class on counting graph colourings up to symmetry.
So in the morning as I lay half asleep, these ideas assembled themselves into a pattern. Maybe not a really significant pattern, but maybe worth something. It occurred to me that perhaps someone should write a book on this …
Recently I wrote about the formulae for the number of ways of choosing a sample of k from a set of n objects:
- Order significant: with replacement , without replacement (the falling factorial)
- Order not significant: with replacement , without replacement
In my view this table illustrates the main division of combinatorics. This is perhaps clearest if we interpret the n objects as “colours”, and regard the task as counting colourings of a set of size k (which we can regard as a complete graph). The first formula is the simplest. Going right along a row, we impose a structural condition: the colouring should be proper (that is, the ends of an edge should get different colours). So the second entry in the first row is the chromatic polynomial of Kk, evaluated at n.
The second row is different: it counts the colourings up to symmetry. That is, it counts orbits of the symmetric group of degree k on the colourings of the two types described in the first row.
Structural combinatorics will take us from this example to graphs, matroids, and beyond. Symmetry seems only to lead to group actions and the resulting counting, but in fact it is much more widespread than that, as I want to discuss.
Orbital chromatic polynomial
It is not hard to extend the above analysis to any graph. The chromatic polynomial of a graph X is a monic polynomial whose degree is equal to the number of vertices of X; it is defined by the property that its evaluation at a positive integer q is equal to the number of q-colourings of X.
What corresponds to the second entry in the second row of our introductory example, when we impose both symmetry and structure (that is, count proper colourings up to symmetry)?
If G is a group of automorphisms of X, there is a polynomial, the orbital chromatic polynomial of X and G: its degree is equal to the number of vertices of X, and its leading coefficient is 1/|G|; its evaluation at a positive integer q is equal to the number of q-colourings up to the action of G, that is, the number of orbits of G on colourings.
To see this, we use the Orbit-counting Lemma, according to which the number of orbits is equal to the average number of fixed points of elements of G. So we have to count the colourings fixed by an automorphism g. Such colourings must be constant on the cycles of g. So, if there are two adjacent vertices in the same cycle, the number is 0. Otherwise, form a contracted graph X/g by shrinking each cycle to a vertex; there is a bijection between colourings of X fixed by g and colourings of X/g, so the required number is the chromatic polynomial of X/g evaluated at q.
Thus, the orbital chromatic polynomial is an average of terms each of which is zero or a chromatic polynomial; the chromatic polynomial of the whole graph appears once in this average. So the claimed result is true.
Koko Kayibi and I started an investigation of roots of orbital chromatic polynomials. There are some similarities, and some differences, with the theory of roots of chromatic polynomials.
In a paper with Bill Jackson and Jason Rudd, which I secretly regard as one of my best (though not many people seem to agree), we gave a far-reaching extension of the orbital chromatic polynomial.
This is in some sense inspired by two pieces of folklore, which are not quite what they seem:
- Nowhere-zero flows in a graph (with values in a finite abelian group of order q) are “dual” to q-colourings.
- The number of nowhere-zero flows depends only on the order of the abelian group, and not on its structure.
I wanted to understand these statements, and I believe that the orbital versions given in the paper throw some light on this.
In the case of the first statement, nowhere-zero flows (or 1-coboundaries) are really dual to nowhere-zero tensions (or 1-boundaries). A tension on X with values in an abelian group A is a function on the (oriented) edges with the property that the (signed) sum round any cycle is zero. Thus, such a function is derived from a “potential” function on vertices, so that the value on an edge is the difference of the values at its head and its tail. The tension is nowhere-zero if and only if the potential takes different values on adjacent vertices, in other words, is a q-colouring of the graph. So the numbers of colourings and nowhere-zero tensions are equal (up to a simple normalising factor qc, where c is the number of components). But this is no longer true if we count orbits of an automorphism group.
The second statement is not really folklore, it is a theorem of Tutte. But the same comment applies. The number of orbits of an automorphism group on nowhere-zero flows with values on an abelian group A does depend on the structure of A, and can be expressed as the evaluation of a polynomial which has a variable for each element order in A; the required substitution for this variable is the number of elements of that order. But a variable only occurs in the polynomial if the corresponding order divides the order of the automorphism group G. So, if G is trivial, the structure of A has no effect.
By phrasing the result in the paper in terms of matrices over principal ideal domains, we were able to give a general theorem which specialises not only to nowhere-zero flows and tensions in graphs, but also to weight enumerators of codes.
One final point on this. The nowhere-zero condition is enforced by an inclusion-exclusion argument over subgraphs of the graph. This indicates a general phenomenon: an evaluation of the Tutte polynomial with one of the variables equal to −1 often is equivalent to an inclusion-exclusion argument!
I have discussed before the connection between transformation monoids and graphs. There are constructions of each type of object from the other, which are not functorial but carry a lot of structural information.
Now transformation monoids, and in particular endomorphism monoids of graphs, are closely connected with a lot of important combinatorics.
This is obscured by the fact that most graphs are cores: they have no proper endomorphisms. But there are many interesting graphs. I will describe here one particular family, but there are many other instances.
The square lattice graph L2(n) has as vertex set the cells of an n×n array; two vertices in the same row or column are joined.
This graph is a pseudocore: it has clique number equal to chromatic number, and all its proper endomorphisms are colourings which take values in a maximum clique.
Now the n-cliques are easy to understand: they are just the rows and columns of the array. But the n-colourings are much more interesting: they are the Latin squares of order n:
So we have a transformation monoid whose elements are pairs consisting of a Latin square and a row or column of the corresponding array.
At first, when I realised this, I was excited at the thought that Latin squares could be composed. But, of course, the way the composition works, any product is equal to its leftmost factor (up to some renormalisation), so the algebraic structure is not so interesting.
The monoid may not be interesting in its own right. But here is a case where a very important classification in semigroup theory (the J-classes, equivalence classes for Green’s relation J) coincide with an important classification of Latin squares. Two Latin squares are equivalent in this sense if they differ by permuting rows, columns and symbols, and possibly transposing rows and columns. So the equivalence classes lie between isotopy classes and main classes.
In terms of the Green’s relations, the L-classes (corresponding to multiplying by automorphisms on the left) correspond to permuting rows and columns and/or transposing; the R-classes (corresponding to multiplying on the right) correspond to permuting the entries of the square.
There are several other examples where interesting combinatorial structures and their classification problems correspond to computing the endomorphisms of a pseudocore.
For some of our recently-discovered graphs, inspired by the butterfly, things are much more complicated, and the semigroups have a rich structure which we have only begun to explore. Almost certainly there is interesting combinatorics to be discovered, but what will it be?