Algebraic properties of chromatic polynomials, 2

My paper with Kerri Morgan on algebraic properties of chromatic roots (described here) has just appeared in the Electronic Journal of Combinatorics: you can find it here.

I won’t say any more about it, except to pose a challenge which we were unable to solve. We found graphs for which the Galois groups of irreducible factors of the chromatic polynomial include all transitive groups of degree at most 4, and all of degree 5 with a single exception; for larger degree, the gaps become wider and wider … So here is the challenge:

Is there a graph whose chromatic polynomial has an irreducible factor with Galois group cyclic of order 5? [Preferably the chromatic polynomial should be a product of this factor and n−5 linear factors.]

Posted in open problems, Uncategorized | Tagged , , | 2 Comments

Polynomials taking integer values

This is not a hot new result, just part of general mathematical culture.

If a polynomial f(x) has integer coefficients, then its values at integer arguments are clearly integers. The converse is false; the simplest example is the polynomial x(x−1)/2.

Also, if a polynomial vanishes at infinitely many different arguments, then it vanishes everywhere. But it is not true that a polynomial which has integer values at infinitely many integer arguments takes integer values at all integer arguments. The simplest counterexample is x/2.

On the other hand, we might often be in the situation where we know that a polynomial takes integer values at all positive integers (for example, because it counts something). Does it follow that it takes integer values at all integers?

This is on my mind as a result of thinking about reciprocal polynomials, as described in a recent post. The cycle polynomial of a permutation group, divided by the group order, takes integer values at positive integers, since it counts something; if a reciprocal polynomial is to have the same property, then the original polynomial should take integer values at negative integers as well.

The answer is yes. If you haven’t thought about this before, please do so now before reading on.

Here is the outline of a simple argument for a more general fact:

If a polynomial of degree n takes integer values at n+1 consecutive integer arguments, then it takes integer values at all integer arguments.

Clearly by translation we may assume that f(0), f(1), …, f(n) are integers. Our proof is by induction on n; starting the induction at n = 0 is immediate. If f has degree n and satisfies the hypothesis, let g be the difference polynomial defined by g(x) = f(x+1)−g(x). Then g has degree n−1 and takes integer values at 0, 1, … n−1; so it takes integer values at all integer arguments, from which we see that the same is true for f.

Richard Stanley, in his celebrated book, gives the very nice representation theorem for such polynomials. The polynomial g in the preceding proof is the first difference polynomial of f; inductively one can define the ith difference polynomial for any i. Now the result is:

Let f be a polynomial of degree n taking integer values at all integers. Then f(x) is an integer linear combination of the “binomial coefficient” polynomials {x choose k}, for k = 0,…n; the coefficient is the kth difference polynomial evaluated at 0.

Of course, this theorem, lovely though it is, is not the most efficient representation in all situations. For example, if n is even, say n = 2m, then (x2m+xm)/2 is the cycle polynomial of the group consisting of the identity and a fixed-point-free involution (divided by the group order); I don’t know how to write it in terms of binomial coefficients.

Posted in exposition | Tagged , , , | 4 Comments

Apology

To my friends in the United States of America: I am sorry, but I do not expect I will be visiting you during the term of office of the current President.

This for two reasons. First, I find his policies terrifying (his encouragement of a new nuclear arms race, his disregard for the facts about climate change) or despicable (his attitude to those of different gender, skin colour, religion or sexual orientation to himself); and second, in the current climate I would be scared for my own safety in the USA (if I would even be allowed in).

It is sad to see the much-praised constitutional system of checks and balances torn up with such ease.

Posted in Uncategorized | 4 Comments

Reciprocity

The cycle index of a finite permutation group is a multivariate polynomial (with one variable si for each index i not exceeding the degree of the group) which is the generating function for the numbers of cycles of different lengths of the permutations in the group. Thus, it is a rather elaborate gadget. Its role in enumeration under group action is well known; that is not my subject here. Because of that, I will simplify things: the cycle index is traditionally divided by the order of the group, but to keep my polynomials integral I will not do this.

Because of its relative complication, certain specialisations of it have been studied. Christopher Harden wrote his PhD thesis at the University of Essex on the fixed point polynomial, the generating function for the numbers of fixed points of elements of G (obtained by putting all variables except s1 equal to 1); he wrote a paper with his supervisor David Penman, which is available here in the Electronic Journal of Combinatorics.

Recently, Jason Semeraro from Bristol proposed to me another specialisation, the cycle polynomial, FG(x), the generating function for the numbers of cycles of elements of G (including fixed points), obtained by putting all the variables of the cycle index equal to x. Again, it is a monic polynomial whose degree is the degree of G. Jason asked me a question about it, but before I could reply, he had answered his own question. But he had caught my interest, and we have just posted a paper on the cycle polynomial on the arXiv.

I’d like to draw attention to one interesting feature, and introduce it in a rather different way from the paper.

First, observe that since all the terms are positive, the cycle polynomial has no positive roots.

The parity of a permutation is the degree minus the number of cycles. As is well known, a permutation group either contains no odd permutations, or half its elements have even parity and half have odd parity. In the first case, all terms of the polynomial have exponents congruent to the degree modulo 2, and so the cycle polynomial is an even or odd function of x according as the degree is even or odd. It follows that the polynomial has no real roots at all except for 0.

The case where the group contains both even and odd permutations is more interesting. It can be shown that the integer roots are 0,−1,−2,…,−a for some positive integer a; this integer is a curious new invariant of a permutation group.

Does that remind you of anything?

The chromatic polynomial PΓ(x) of a graph Γ is the polynomial whose value at a positive integer q is the number of proper vertex-colourings of the graph with q colours. It has no negative real roots; its integer roots are 0,1,2,…,a, where a is one less than the chromatic number of Γ, the smallest number of colours required for a proper vertex-colouring.

Is there any connection between FG(x) and PΓ(−x)?

It turns out that there is a better question lurking here. In 2008, Bill Jackson, Jason Rudd, and I defined the orbital chromatic polynomial of a pair (Γ,G), where Γ is a graph and G a group of automorphisms of Γ. Evaluated at a positive integer q (and, with a slight modification to fit what is going on here, divided by the order of G), it counts orbits of G on proper vertex-colourings of Γ with q colours. Koko Kayibi and I wrote another paper examining the location of its roots.

Now it happens surprisingly often that, given a permutation group G, there is a G-invariant graph Γ such that the orbital chromatic polynomial of the pair (Γ,G) is (−1)nFG(−x).

This is an example of what Richard Stanley called a combinatorial reciprocity theorem.

I have made the two polynomials different in one respect: with the cycle polynomial, the coefficients count things; with the orbital chromatic polynomial, it is the evaluations that count. But this is not a real difference. The cycle polynomial evaluated at the positive integer a (and divided by the order of G) counts orbits of G on unrestricted colourings of the domain with a colours, whereas the orbital chromatic polynomial counts orbits on proper vertex-colourings of Γ.

For example, take Γ to be a 4-cycle, and G the dihedral group of order 8. The cycle polynomial is x(x+1)(x2+x+2), while the orbital chromatic polynomial is x(x−1)(x2x+2). So G has six orbits on 2-colourings, one of which is a proper vertex-colouring. (This was the example that first alerted me to what was going on.)

I won’t go through listing examples; there are several in the paper, and in particular we have decided exactly which pairs satisfy this reciprocity. But the big open question is:

For which pairs (Γ,G) does this reciprocity hold?

We have determined them in the case where Γ is a complete or null graph or a tree. But there is more to do. In particular, a solution which simply involved a classification would be less enlightening than one which gave some conceptual reason for the phenomenon.

I would be very interested to know if this reciprocity has been observed in similar situations involving a permutation group! (Stanley gave several examples, none of them involving permutation groups. In particular, he gives the correct reciprocity theorem for the chromatic polynomial; it involves acyclic orientations. I have no idea if there is a connection.)

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

70

The days of our years are threescore years and ten; and if by reason of strength they be fourscore years, yet is their strength labour and sorrow; for it is soon cut off, and we fly away.

So today I have achieved the days of my years; I hope that I will have strength enough to prolong them a bit, since I am enjoying myself at the moment, and don’t want to fly away just yet.

In the past year, I have put eleven papers (including one update) on the arXiv, involving 26 coauthors and totalling 292 pages. Quite a good record, I think, and one that should keep the REF accountants off my back for a while.

On my birthday, I lectured at 12 and saw a project student at 3. So I’m spending quite a bit of time on teaching as well.

And, even better: Jason Semeraro and I have nearly finished writing a paper, which I hope to write about here shortly; and on Saturday, Nicolas Thiéry and Justine Falque came to St Andrews to talk about oligomorphic permutation groups (one of my favourite topics, which is overdue a mention here) and to walk on West Sands.

Posted in Uncategorized | Tagged | 5 Comments

Impact update

My comments on impact were cited by Ursula Martin and her co-author Laura Meagher here. Worth a look.

PS Here’s the abstract:

This empirical study explored how research can generate impacts by investigating different sorts of impacts from one academic field—mathematics—and the diverse mechanisms generating them. The multi-method study triangulated across: (1 and 2) content analysis of impact case studies and environment descriptions submitted to the UK Research Excellence Framework (REF) assessment; (3 and 4) a survey and focus group of heads of mathematics departments; and (5) semi-structured interviews. Mathematics has had a full range of impact types, particularly conceptual impacts, although more tangible instrumental impacts were prioritized for REF. Multiple mechanisms were utilized, but seldom appeared in REF case studies. Long-term relationship building and interdisciplinarity are particularly important. Departmental culture and certain knowledge intermediaries can play proactive roles. In sharp contrast to simplistic linear narratives, we suggest that appreciation of diverse impact types, multiple, often informal, mechanisms and dynamic environments will enhance the likelihood of meaningful impacts being generated.

Posted in Uncategorized | Tagged | Leave a comment

Automorphism groups of transformation semigroups

I have been in the transformation semigroups game for nearly ten years now, but I still feel that I am finding my feet.

Here is apparently a huge difference between permutation groups and transformation semigroups, one which is still not fully understood. A permutation group may have automorphisms which are not induced by conjugation in the symmetric group. The most spectacular example of this is the symmetric group of degree 6, which has an outer automorphism, as I have discussed here. (This is the only symmetric group, finite or infinite, which has an outer automorphism.) This beautiful configuration is intimately connected with other interesting phenomena; I outlined here how to use this to construct the Mathieu groups M12 (which also has an automorphism not induced by a permutation) and M24, and one can go on to the Conway groups and the Monster. Chapter 6 of my book with Jack van Lint explains also how to use it to construct (and show uniqueness of) the projective plane of order 4 and the Moore graph of valency 7 (the Hoffman–Singleton graph).

Could anything similar happen for transformation semigroups?

It appears not. Forty years ago, R. P. Sullivan proved a very general theorem which implies, in particular, that a transformation semigroup on a set X which contains all the constant maps on X has the property that its automorphisms are all induced by permutations of X, so that its automorphism group is isomorphic to its normaliser in the symmetric group on X. (To show this, observe first that an automorphism of the semigroup must preserve the set of constant maps, which is naturally bijective with X; then we must show that an automorphism which fixes all the constant maps must be the identity.)

Now this is something interesting. The synchronization project, which was my introduction to semigroup theory, is concerned with those permutation groups G with the property that any transformation semigroup containing G and at least one singular transformation necessarily contains all the constant maps. It follows that if a transformation semigroup contains a synchronizing group, then all its automorphisms are induced by permutations. Moreover, we know that the class of synchronizing groups contains the 2-transitive groups (even the 2-homogeneous groups) and is contained in the class of primitive groups; this is a large and interesting class of permutation groups.

So what about transformation semigroups which contain a singular transformation and whose group of units is a non-synchronizing permutation group? For these, João Araújo, Wolfram Bentz and I have made the first small breakthrough. Embarrassingly small, I would say.

Assume that G is a primitive permutation group. We say that G synchronizes the singular map t if the semigroup generated by G and t contains a constant map (and, hence, contains all constants). Now we know, from our paper with Gordon Royle and Artur Schaefer which just appeared in the Proceedings of the London Mathematical Society, that a primitive group of degree n synchronizes any map whose rank (cardinality of the image) is 2 or at least n−4 (and, indeed, we conjecture that the upper value can be improved to n−5, but the labour involved in showing this with our techniques would be prohibitive). So the obvious case to consider is maps of rank 3.

Our theorem says that, if a transformation semigroup contains a primitive group and a map of rank 3, then all its automorphisms are inner.

There are some interesting examples of such groups to be found in the paper. These include the automorphism groups of the Heawood, Tutte–Coxeter, and Biggs–Smith graphs, acting on the edge sets of the graphs, and two different actions of the Mathieu group M12 on 495 points. The last two stand in a curious relation: they are automorphism groups of a pair of graphs where the vertices of one graph correspond to the triangles (images of endomorphisms of minimal rank) of the other, adjacency of vertices corresponding to intersection of triangles.

We go so far as to conjecture that the “rank 3” assumption can be dropped; all we need is a primitive group and a singular map. But we are a long way from the proof of this at the moment. Still, hopefully we have taken the first step, so here is a nice project for the new year.

Posted in doing mathematics, open problems, Uncategorized | Tagged , , | Leave a comment