Busy times, 10: in Waterloo

After a week in London, off to Waterloo for Chris Godsil’s 65th birthday conference.

The week at home was no holiday: among other things I managed to

  • read and examine Christopher Harden’s PhD thesis (a nice study of fixed point polynomials of permutation groups);
  • write a talk for the Waterloo conference, and most of a talk for the
    Portuguese Mathematical Society summer meeting, from scratch;
  • make my annual foray to Oxford Street for clothes shopping (this didn’t get done last year, I was too busy, and having to divide my clothes between two places meant things were getting rather desperate);
  • go on an expedition to the dinosaurs in the Natural History Museum with my children and grandchildren.

A couple of nice speculations from Christopher Harden’s thesis (I don’t think he would call them conjectures unless he were feeling extremely optimistic; but he worked many examples and these speculations appear to hold). The fixed point polynomial of a permutation group is the generating function for the number of fixed points of elements of the group; that is, the coefficient of xm is the number of group elements with m fixed points.

  • The number of real roots of the fixed point polynomial of a transitive permutation group is bounded above by an absolute constant.
  • The roots of fixed point polynomials for arbitrary permutation groups are dense in the complex plane (not true for transitive groups, he found a zero-free region).

Then an early start on Sunday morning in order to catch a 10:40 flight from
Gatwick to Toronto.

I was delighted to be asked to speak, although I have no formal connection with Chris; much to people’s surprise, we don’t even have a joint paper. (Plenty of time yet! As far as the photography session before the conference banquet was concerned, what I share with Chris is being aged 65+ and being Australian/New Zealander.) But we have enough common interests that I felt I had things to say about graph endomorphisms and synchronization that would be interesting to him and his students and postdocs; I hope that proved to be the case.

With Chris Godsil

The conference was in the quantum nano centre, which seems to be practical as well as theoretical: is this the kit needed to build a quantum computer?

Building a quantum computer

It was a wonderful occasion, a very happy conference, which is a tribute to the esteem in which Chris is held by colleagues and present and former students. I first met Chris in 1980 (if I recall correctly): I was visiting Sydney, and he and Brendan McKay invited me down to Melbourne to work together for a few days. So it seems that I had known him for longer than most people at the meeting (Brendan, Cheryl Praeger and Wilfried Imrich excepted).

The front wall of the lecture room under the projector screen was one huge whiteboard – but the pens were not good enough to risk a board talk. The very left of the board was reserved for information; the first item concerned “collaboration space”, a room in another building where people could go to work together. I suggested that the term might be interpreted as “collaboration graph with extra structure”, e.g. with a simplex pasted on for every set of authors who have written a paper together (or should we require that to form a simplex it would have to be the case that every subset of those authors should have a paper together? I think not, since this requirement is not enforced for the graph.)

A lot of good talks too, some of which I will try to describe briefly.

  • Brendan McKay talked about his result on counting k-regular graphs with 1-factorisation. This is new, but Brendan and Chris did the bipartite case (aka counting Latin rectangles) long ago, and some of Chris’ tricks are useful here too.
  • Gordon Royle gave a summary of results about roots of chromatic polynomials. Since the Newton Institute programme in 2008, much of this wasn’t new to me, but the pictures really add something to the results.
  • There were several talks on perfect state transfer in quantum random walks on graphs. This seems to be a relatively rare phenomenon, each new example being something to take note of.
  • On a related theme, Chris himself talked about perfect mixing in quantum random walks. This is in some sense the reverse. Instead of wanting the wave function concentrated at a single vertex at some time, you want the probabilities evenly spread over all vertices. This is almost as rare. The only cycles known to have the property are those of lengths 3 and 4. It is known that there are no other even cycles, but the proof of this apparently simple fact requires tools as deep and devious as the Gel’fond–Schneider theorem on the transcendence of ab for algebraic numbers a and b (if the latter is irrational) and an analytic theorem of Haagerup. As he said, new tools needed! Akihiro Munemasa followed up with a talk about finding some examples (aka complex Hadamard matrices in 3-class association schemes). He also explained the array of antipodean animals on the front of the conference programme.
  • A couple of authors including David Roberson and Simone Severini talked about graph parameters lying between the clique number and the chromatic number (and so potentially useful in the synchronization project).
  • Although I had heard part of it before, I really liked Bojan Mohar’s talk about median eigenvalues of graphs (especially bipartite graphs). He took us right from Hückel’s molecular orbital theory (which, using an approximate version of Schrödinger’s equation, reduces analysis of aromatic hydrocarbons to a problem on eigenvalues of graphs) to recent results on the “median gap”. An interesting speculation was whether there could be a carbon molecule with the configuration of the Heawood graph (a kind of super-buckyball). Apparently such a molecule would have metal-like properties.
  • Marston Conder talked about “Extreme graph symmetries”, which sounds like a new sport for the daredevil mathematician.
  • Cheryl Prager told us how much of her joint work with Chris had involved asking questions about doubly transitive groups which could not be answered just by having a list of the groups available – these included distance-transitive graphs, imprimitive rank 3 groups, and neighbour-transitive codes in the Johnson schemes. I certainly agree that there are many more problems hiding here, as in some of my work with João Araújo.

My slides are in the usual place.


For the excursion, we went to Elora, where the Grand River flows through a spectacular gorge. Ian Wanless and I went for a walk along the gorge, and came back to look at a map in the tourist information (which suggested some much less interesting walks). Then we had lunch in a pub, coffee in another, and a beer in a third, until it was time to go.

About Peter Cameron

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

2 Responses to Busy times, 10: in Waterloo

  1. Jon Awbrey says:

    We spend a couple weeks in Stratford every summer — get thee to a play if you have a day! — and often visit Elora, the Mill by the “Tooth of Time”. They have a summer music festival but the timing has been off for us in recent years.

  2. Another report on this conference appears on the Matroid Union blog: http://matroidunion.org/?p=919

Leave a Reply

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

WordPress.com Logo

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.