The first lecture on Thursday was by Benny Sudakov, on robustness of graph properties. For purposes of exposition, he had decided to focus on one particular property, that of being Hamiltonian. Dirac’s famous theorem tells us that a graph on n vertices with minimum degree at least n/2 has a Hamiltonian circuit. Robustness of the property of Hamiltonicity could mean one of several things: there are many Hamiltonian circuits; there are many pairwise disjoint Hamiltonian circuits; an enemy would have to make significant changes to the graph to destroy the property; and so on. All these hold (and can be quantified). Moreover, not only is Hamiltonicity robust in a graph satisfying Dirac’s condition, but it tends to be robust in a random graph where edge probabilities are large enough to force the property to hold.
The second plenary was by Gi-Sang Cheon, on new applications of Riordan arrays. This was a rather technical talk, full of information. Unfortunately, since Gi-Sang was substituting at rather short notice for a plenary speaker who was unable to attend, he didn’t have an article in the book, and when I asked him afterwards he said that the material he was speaking about was too new to be in any survey yet. So I won’t attempt to describe the talk.
Of the contributed talks, there were several worth mentioning, but one of the best was by Iain Moffatt. He told us that the crucial property of the Tutte polynomial is the deletion-contraction relation, and in any situation where one has such a relation one should expect a “Tutte polynomial”. Why, he asked, are there three different Tutte polynomials for graphs embedded in surfaces in the literature? For the answer it is necessary to look more closely at deletion and contraction. Even if we use the nicest possible definition, where graphs are embedded so that faces are topological discs, trouble can arise when you delete or contract an edge. If you delete an edge going round a hole, a face of the resulting graph can fail to be a disc; and if you contract an edge which is a non-contractible cycle, you pinch the surface to a point, so you must either put up with a pseudosurface, or take your scissors and cut the surface at that point. Thus you actually expect four Tutte polynomials (allowing or disallowing non-simply-connected faces, and allowing or disallowing pseudosurfaces).
In the final session, I had to miss some talks I would like to have heard in order to give my own, on synchronization and separation in the Johnson association scheme. The slides are in the usual place.
Dinner was in the Barony Hall, a former huge church just beyond the cathedral, now used by the University of Strathclyde. A very good dinner, very congenial and interesting conversation, and after dinner a ceilidh, at which I guess the majority of the participants had at least one dance. After the band stopped and the staff were clearing the hall, we headed back to the hotel.
Friday morning saw us check out of the hotel in good time to be at the conference by 9, where I was introducing Bill Chen. He had chosen well; his topic, the spt-function of Andrews, was very technical, but his talk was well judged for the morning after the conference dinner, with little episodes into historical detail (Euler, Hardy and Ramanujan, Dyson, Andrews, and others), and even a quote from Rabindranath Tagore on the relation between simplicity and complication. (The definition of rank which led to the “combinatorial” proof of two of Ramanujan’s conjectures is very simple, but the proof is still very complicated.)
One contributed talk stood out for me: Bridget Webb’s. She and Daniel Horsley have constructed uncountably many countable homogeneous Steiner triple systems. (I need to point out here, as Bridget did, that we are regarding a Steiner triple system as a functional structure – a quasigroup – whose substructures correspond to subsystems, rather than as a relational structure whose substructures are partial Steiner triple systems: a structure is homogeneous if any isomorphism between finitely generated substructures extends to an automorphism of the structure. The construction required results on embedding partial Steiner triple systems which go well beyond what was previously known. I was reminded of Cherlin’s classification of homogeneous digraphs, where there are uncountably many of a general type together with a few sporadic examples. I suspect that turning the construction here into a classification will be extremely difficult!
The final talk of the conference, which was also the Rado lecture, was given by Vít Jelínek on Ramsey-type problems in permutations. Since Strathclyde is one of the top centres of research on permutation patterns, this was a good choice of topic; Vít’s take on permutations is similar to mine, regarding a permutation as a set carrying two total orders, and he did indeed quote my classification of homogeneous permutations (but there was far more in the talk than that).
And so ended what I thought had been an excellent and memorable British Combinatorial Conference, and we all headed home (slightly delayed, in our case, by Sergey Kitaev, who had very kindly invited us to a barbecue at his home in Linlithgow, preceded by a very brief detour to Linlithgow Palace, the birthplace of Mary Queen of Scots).