Yesterday was World Book Day.

A perfect excuse to post this picture of my amazingly cute grandchildren …

Yesterday was World Book Day.

A perfect excuse to post this picture of my amazingly cute grandchildren …

Neill’s new book came out a little while ago, and this morning I saw that he had finally got round to announcing it on his blog, and asking people to spread the news by word of mouth, since the publishers can’t afford big notices on the sides of buses (more’s the pity).

So here it is. It is book 1, and unlike the unfortunate Mo-Bot High, it is likely that there will be a book 2 (especially if it sells well!)

Posted in books, geography, history, Neill Cameron artwork, the Web
Tagged dinosaurs, pirates
Leave a comment

… to Rosemary Bailey, who has been elected a Fellow of the Royal Society of Edinburgh.

It is pleasing when one of us gets to go through such a door!

Here is my calendar picture for March.

The shiny fruit are images of an artwork based on concave circular mirrors in the Kampa Gallery in Prague, the art gallery which inspired the whole enterprise and provided the basic picture for the cover.

If you look closely you can see the photographer’s reflection in the strange fruit.

Yesterday my colleague Collin Bleak sent me an email containing the number 1247. I will explain why this made me so pleased.

Our problem concerns automata. If you know Collin, you may suspect that it has something to do with the Thompson groups; indeed it does, but I won’t explain this now.

An *automaton* with *N* states over an alphabet *A* is a machine whose action consists of reading a symbol from *A* and as a result undergoing a transition to a possibly different state. It does this repeatedly. No question of start and end states or languages accepted.

So an automaton can be represented by a directed graph with *N* vertices (corresponding to the states), edges labelled by *A*, and with the property that there is exactly one edge with any given label *leaving* any vertex. If it is in state *v* and reads a symbol *a* then it follows the unique directed edge with label *a* leaving *v*, and changes to the state corresponding to the terminus of this edge.

An automaton is said to be *k*-*determined* if, whenever it reads a word *w* = *a*_{1}…*a _{k}* of length

Our basic question is: How many *k*-determined automata are there over an alphabet with *n* symbols? (To avoid trivialities we assume every vertex can be reached by reading some sequence.) The number 1247 is the answer for *k* = 4 and *n* = 2. The sequence for *n* = 2 and increasing *k* runs 2, 5, 30, 1247, …. This sequence is not (yet!) in the OEIS.

De Bruijn showed that given a positive integer *m* and a finite alphabet *A*, there is a circular sequence of length |*A*|^{m} which contains every *m*-tuple exactly once as a consecutive subsequence.

He proved this by constructing a directed graph as follows. The vertices are all the (*m*−1)-tuples over *A*. Each *m*-tuple *a*_{1}…*a _{m}* labels an edge which joins its initial (

If we instead label the edge just by the last symbol in its *m*-tuple, then the graph becomes an automaton. Moreover, it is (*m*−1)-determined, since if we read a sequence of *m*−1 symbols we arrive at the vertex with that sequence as label. Even more, the de Bruijn graph is the “universal” (*m*−1)-determined automaton, since different sequences lead to different vertices.

To avoid confusion, I will now use *k* rather than *m*−1.

The picture shows the de Bruijn graph with *k* = 3 and alphabet {0,1}, drawn as an automaton.

Any *k*-determined automaton gives an equivalence relation on the vertex set of the de Bruijn graph: two vertices are equivalent if their labelling strings put the automaton into the same state. This equivalence relation has the further property that, if two vertices with labels *u* and *w* are equivalent, then for any letter *a* in the alphabet, the vertices with labels *v ^{-}a* and

Such an equivalence relation is called a *folding* of the graph.

Conversely, given a folding, there is a unique automaton which gives rise to it: we can take the vertices to be the equivalence classes, and define the transitions in the obvious way.

So to count the *k*-determined automata, we only have to count foldings of the de Bruijn graph whose vertices are labelled by *k*-tuples.

This is what we have done for a variety of small values, including *k* = 4 and |*A*| = 2, as noted above.

The number 1247 (and indeed most of the others) has been calculated twice. Collin used the strategy of taking the set of all strings, making an identification, working out its consequences, making another, and so on, keeping track of what has already been found to avoid duplications; he programmed in C++ and the calculation of the number 1247 took less than a minute.

I worked from the other end, iterating over all partitions of the set of strings and checking the “closure” condition in the definition of a folding, so that no check for duplicates was necessary. I programmed it in GAP, and my program took about ten minutes to calculate the number. A reasonable difference, I think.

Incidentally, GAP contains iterators for some combinatorial objects, but not for set partitions, so I had to write my own. In my Combinatorics textbook, written in the mid-1990s, I emphasised the value of being able to iterate over a large set of objects, rather than generating them all at the start, so it was a good opportunity to practise my own philosophy.

I hope to say more about the relevance of this to Thompson groups sometime in the future. There is an interesting story there too.

Following up a conversation with John Amson at Rufflets Hotel, just outside St Andrews, I was led to a paper on combinatorial physics:

Ted Bastin, H. Pierre Noyes, John Amson, Clive W. Kilmister: On the physical interpretation and the mathematical structure of the combinatorial hierarchy, *International Journal of Theoretical Physics* **18** (1979), 445–488; doi: 10.1007/BF00670503

Here is the abstract. See what you make of it.

The combinatorial hierarchy model for basic particle processes is based on elementary entities; any representation they may have is discrete and two-valued. We call them Schnurs to suggest their most fundamental aspect as concatenating strings. Consider a definite small number of them. Consider an elementary creation act as a result of which two different Schnurs generate a new Schnur which is again different. We speak of this process as a “discrimination.” By this process and by this process alone can the complexity of the universe be explored. By concatenations of this process we create more complex entities which are themselves Schnurs at a new level of complexity. Everything plays a dual role in which something comes in from the outside to interact, and also serves as a synopsis or concatenation of such a process. We thus incorporate the observation metaphysic at the start, rejecting Bohr’s reduction to the haptic language of common sense and classical physics. Since discriminations occur sequentially, our model is consistent with a “fixed past-uncertain future” philosophy of physics. We demonstrate that this model generates four hierarchical levels of rapidly increasing complexity. Concrete interpretation of the four levels of the hierarchy (with cardinals 3,7,127,2^{127}-1∼10^{38}) associates the three levels which map up and down with the three absolute conservation laws (charge, baryon number, lepton number) and the spin dichotomy. The first level represents +, −, and ± unit charge. The second has the quantum numbers of a baryon-antibaryon pair and associated charged meson (e.g.,n^{-}n,p^{-}n,p^{-}p,n^{-}p,π^{+},π^{0},π^{-}). The third level associates this pair, now including four spin states as well as four charge states, with a neutral lepton-antilepton pair (e^{-}e or v^{-}v), each pair in four spin states (total, 64 states) – three charged spinless, three charged spin-1, and a neutral spin-1 mesons (15 states), and a neutral vector boson associated with the leptons; this gives 3+15+3×15=63 possible boson states, so a total correct count of 63+64=127 states. Something like SU_{2}×SU_{3} and other indications of quark quantum numbers can occur as substructures at the fourth (unstable) level. Breaking into the (Bose) hierarchy by structures with the quantum numbers of a fermion, if this is an electron, allows us to understand Parker-Rhodes’ calculation of *m*_{p}/*m*_{e} =1836.1515 in terms of our interpretation of the hierarchy. A slight extension gives us the usual static approximation to the binding energy of the hydrogen atom, α^{2}*m*_{e}*c*^{2}. We also show that the cosmological implications of the theory are in accord with current experience. We conclude that we have made a promising beginning in the physical interpretation of a theory which could eventually encompass all branches of physics.

My first reaction is something along these lines. Pythagoras is thought to have believed that “all is number”, and also to have believed in reincarnation. (Of course, we know nothing about what he really believed.) So perhaps these authors are channelling the spirit of Pythagoras.

Note also that *Schnur* is German for “string”, as claimed, but is also defined by the Urban Dictionary as “the ultimate insult that means absolutely nothing”. Interesting?

Actually reading the paper didn’t clear up all my doubts. The setting is sets of binary strings. A set of strings is called a *discriminately closed subset* if it consists of the non-zero elements in a subspace of the vector space of all strings of fixed length *n*. Such a subset has cardinality 2^{j}−1, where *j* is its dimension. Now a step in the *combinatorial hierarchy* involves finding a set of 2^{j}−1 matrices which are linearly independent and have the property that each of them fixes just one vector in the subset (I think this is right, but the wording in the paper is not completely clear to me). These matrices span a DCsS of dimension 2^{j}−1 in the space of all strings of length *n*^{2}.

Of course, the exponential function grows faster than the squaring function, so the hierarchy (starting from any given DCsS) is finite. Their most important example starts with *j* = *n* = 2 (two linearly independent vectors in {0,1}^{2} and their sum), and proceeds to *j* = 2^{2}−1 = 3, *n* = 2^{2} = 4; then *j* = 2^{3}−1 = 7, *n* = 4^{2} = 16; then *j* = 2^{7}−1 = 127, *n* = 16^{2} = 256; then *j* = 2^{127}−1 ∼ 10^{38}, *n* = 256^{2} = 65536 (but this is impossible, so I am not sure what it means to continue the hierarchy to this point).

They point out that the numbers 127 and 2^{127}−1 are close to, respectively, the fine structure constant and the ratio of strengths of electromagnetic to gravitational force between protons. If you use cumulative sums, you get 3, 10, 137 and a number which is again about 10^{38}, and of course 137 is even closer to the target. But I am not sure why you should do this, and in any case, the fine structure constant is measureably different from 137. The non-existence of 10^{38} linearly independent matrices of order 256 supposedly has something to do with “weak decay processes”.

The paper contains some constructions of the appropriate hierarchies. One could pose the mathematical question: do the required linearly independent non-singular matrices exist for any *n* and *j* for which 2^{j}−1 ≤ *n*^{2}?

By this stage I was floundering, so I gave up my careful reading. I noted at a certain point a calculation of the ratio of proton mass to electron mass giving a value 137π/((3/14)×(1+(2/7)+(2/7)^{2})×4/5), agreeing with the experimental value to eight significant figures. (There are three terms in the geometric series because the hierarchy falls over at step 4.) Of course, putting in a more accurate value for the fine structure constant would make the agreement less good: the authors do attempt to explain this.

(If you are a mathematician looking at the paper, the mathematics is put in an appendix starting on page 480, so you can avoid the physics.)

At another point in the conversation, John told me that he ran with the fox and hunted with the hounds. On the strength of this, I can perhaps attribute to him a certain degree of scepticism about all this.

Posted in exposition
Tagged combinatorics, fine structure constant, John Amson, linear independence, physics
Leave a comment

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 *K _{k}*, evaluated at

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.

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 *q ^{c}*, where

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* *L*_{2}(*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.

So even finding the order of this monoid requires the classification of Latin squares, which has only been achieved for *n* ≤ 11 (see here andhere).

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?