I spent last week in Waterloo (Ontario) attending a conference celebrating the work of Chris Godsil (and his 65th birthday). It was a week packed with excellent talks, mostly by current or former students and collaborators of Chris.
The conference title is a clear indication of the breadth of Chris’ work: “Algebraic combinatorics: spectral graph theory, Erdös-Ko-Rado theorems and quantum information theory”. The number of talks shows the impact of Chris Godsil’s research. There were way too many speakers for me to even mention all of them, so I’ll just talk about a few of the talks.
The conference opened with Brendan McKay, who talked about counting edge-coloured regular graphs. In the 1980s, together with Chris Godsil, the speaker had determined an asymptotic formula for counting edge-coloured regular bipartite graphs (which correspond to latin rectangles). This result suggested investigating the analogous problem for general edge-coloured regular graphs, which was the subject of the talk.
On the same day the only talk to mention matroids was delivered by Gordon Royle. He talked about roots of the chromatic polynomial of graphs and matroids. The chromatic polynomial of a graph is a polynomial that counts the number of proper colouring of the vertices of the graph with a certain number of colours. I won’t get into any details, you can find a small introduction to the chromatic polynomial on wikipedia . Despite being studied by mathematicians and physicists for a long time, there are many open questions about the chromatic polynomial of graphs, in particular about the location of its real and complex roots. Being an evaluation of the Tutte polynomial, the chromatic polynomial can easily be defined for matroids (although in this case it’s usually called characteristic polynomial). Almost nothing is known about the location of the roots of the chromatic polynomial of matroids, except for results on graphic matroids and cographic matroids (the chromatic polynomial of a cographic matroid is the flow polynomial of the associated graph). I will soon start a project with Gordon on this intriguing subject; hopefully this will lead to some posts about this.
Cheryl Praeger was also part of the small delegation from the University of Western Australia; she gave a history of the classification of finite 2-transitive permutation groups and its applications.
Peter Cameron talked about endomorphisms and synchronisation; every graph has a semigroup of endomorphisms, but one can also start from a transformation semigroup and construct a graph with nice properties.
Chris Godsil’s talk concerned the last part of the conference title, quantum information theory. He talked about a range of tools to obtain graph which have uniform mixing in quantum walks. Coding theory, association schemes and number theory all figured in his talk. Chris lived to his reputation of being an avid photographer by taking pictures of all the speakers at the conference. An email front he organisers, on the day before his talk, suggested that we all took pictures of him during his talk (more precisely, during the 5th slide). I didn’t do a very good job with my picture, but here it is anyway.
The conference closed with a talk by Karen Meagher, who was a post-doc at the University of Waterloo working with Chris Godsil. She talked about an algebraic perspective on Erdös-Ko-Rado theorems. The EKR-theorem gives the exact structure of the largest collection of k-subsets of n elements with the property that every two sets share at least one element. This type of question can be extended to many combinatorial objects. This is the topic of a book that Karen is writing with Chris. Quoting her abstract, the book is “$\epsilon$ away from completion”; I look forward to see it published.