Laszlo Babai in St Andrews

I promised to say a few words about Laci Babai’s visit to St Andrews. In an amazing performance, he gave five talks: one of nominally an hour at the Scottish Combinatorics Meeting (it was actually the last talk of the meeting, and had to be cut slightly so people could leave), two ninety-minute tutorials on the proof of his quasi-polynomial bound for graph isomorphism, and two talks to the undergraduate mathematics and computer science societies.

I don’t intend to give a blow-by-blow account of all this.

The big theorem says that there is an algorithm which tests isomorphism of two n-vertex graphs in time bounded by exp(O(log n)c) for some constant c. As the name might suggest, the bound is polynomial if the constant c is equal to 1. The best previous result for graph isomorphism was exp(O(nc)), that is, fractional exponential.

The strategy is “divide and conquer”, and as Laci explained, his job was to divide, since the conquering had already been achieved by Luks. The dividing is rather involved, and I won’t attempt to describe it. Any graph isomorphism algorithm has to name an object in the graph; this incurs a multiplicative cost equal to the number of objects which could have been named.

The basic division step is called “split or Johnson”. It identifies, at a cost which can be controlled, either a small subset of the vertex set, or a partition of the vertex set, or a Johnson graph (whose vertices are the k-element subsets of an auxiliary m-element set). But for the induction, we have to have the structure of a graph on the auxiliary set, and further complicated reductions were needed to achieve this.

In the second tutorial, he described carefully the mistake that Harald Helfgott had found in the proof, and how he had fixed it. The arguments seemed fairly familiar to me; there are similar things in my Oxford DPhil thesis in 1971. This was the time when the graph-theoretic methods introduced into permutation group theory by Charles Sims and Donald Higman were beginning to make their mark on permutation group theory.

Nothing is ever lost!


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in Uncategorized. Bookmark the permalink.

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 )

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.