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


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , . Bookmark the permalink.

One Response to Reciprocity

  1. Jon Awbrey says:

    Very nice, filed under “Table of Marks”. (I’m just putting this link here to remind me to come back to it later.)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s