World Book Day

Yesterday was World Book Day.

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

World Book Day

Posted in Uncategorized | Tagged , , | Leave a comment

Pirates of Pangaea

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).

Pirates of Pangaea

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 , | Leave a comment

Congratulations …

… 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!

Posted in Uncategorized | Tagged | 3 Comments

March

March

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.

Posted in Uncategorized | Tagged , , | 1 Comment

1247

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

Automata

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 = a1ak of length k, its final state depends only on the word w and not on the initial state. In other words, all information about the initial state is lost after k steps.

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 graphs

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 a1am labels an edge which joins its initial (m−1)-tuple a1am−1 to its final (m−1)-tuple a2am. The digraph is connected and has in-degree and out-degree both equal to |A|. By Euler’s theorem, it has a closed trail passing once along each edge. Reading the symbols on this trail gives the required de Bruijn sequence.

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.

De Bruijn graph

Foldings of de Bruijn graphs

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 w-a are also equivalent, where v- is obtained by dropping the first symbol of v.

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.

Posted in exposition | Tagged , , | 1 Comment

The combinatorial hierarchy

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,2127-1∼1038) 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 SU2×SU3 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 mp/me =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, α2mec2. 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 2j−1, where j is its dimension. Now a step in the combinatorial hierarchy involves finding a set of 2j−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 2j−1 in the space of all strings of length n2.

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 = 22−1 = 3, n = 22 = 4; then j = 23−1 = 7, n = 42 = 16; then j = 27−1 = 127, n = 162 = 256; then j = 2127−1 ∼ 1038, n = 2562 = 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 2127−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 1038, 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 1038 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 2j−1 ≤ n2?

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 , , , , | Leave a comment

Orbital combinatorics

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 …

The prototype

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 n^k, without replacement n(n-1)\cdots(n-k+1) (the falling factorial)
  • Order not significant: with replacement n+k-1\choose k, without replacement n\choose k

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.

A generalisation

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!

Another generalisation

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:

Latin square colouring a grid

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?

Posted in exposition | Tagged , , , , , , , , , , | 1 Comment