BCC26, 1

About halfway through the British Combinatorial Conference, at last I have time to say something about it.

I am not just a combinatorialist, but I always feel that the BCC delegates are the group into which I naturally fit. It is always a pleasure meeting old friends and indeed new friends.

So to begin with the least interesting part: I am never really off duty at the BCC, since I have to chair the business meeting on Tuesday and the committee meeting on Wednesday, perform at the concert, give my talk, and run the problem session. Also, there are far too many contributed talks for me to go to more than a tiny fraction of them; I have already had to miss one talk by a co-author of mine, and others by colleagues or students.

One innovation this time has been the introduction of mini-symposia, of which there were three: on extremal combinatorics, on graph colouring, and on permutation patterns. The speakers in the mini-symposia were given a little longer than ordinary contributed speakers. These seem to have been popular, and look to be here to stay; I hope that the result is not perceived to be two classes of speakers (apart from plenary speakers). One highlight was a lovely talk by Bruce Sagan on descent polynomials and related things. A descent in a permutation π is a value i such that π(i) > π(i+1). MacMahon proved that the number of permutations with descents in specified positions (and no others) is given by a polynomial; these polynomials were ignored for a long time but are now of great interest, as are the related peak polynomials counting permutations with a given set of peaks.

On Monday night we had a civic reception in the amazing Glasgow City Chambers.

The dignitary who addressed us was well briefed. This is the 100th anniversary of the birth of Bill Tutte, who among other things was a Bletchley Park codebreaker who was instrumental in breaking the Lorenz cipher used by the German high command in World War 2. She knew this, and gave us a well-informed potted account about Tutte (but didn’t know that, like her, Tutte was a graduate in Chemistry; I told her this when we spoke later).

On Tuesday we had the conference concert, the highlight of which was Bruce Sagan leading us in singing Scottish folk songs including “Wild Mountain Thyme”.

Just a bit about the main talks. The first was by Daniel Horsley, who showed us some of the results that have been proved about graph decompositions by “local switching” (including embeddings of partial Steiner triple systems, cycle decompositions, and almost regular decompositions). He illustrated what he meant by “local switching” (a somewhat vague but fruitful idea) by showing us that, if a graph has a proper t-edge-colouring, then it has one in which the sizes of the colour classes differ by at most one.

Rosemary Bailey began by showing us why experimental design is the study between relations between partitions of a set, of which the most important in this context are refinement, orthogonality, and balance; by looking at the possible relations between three partitions, many interesting classes of designs emerge naturally, including triple arrays, which I have recently spoken about here.

Julia Böttcher and Peter Allen are here with their new baby, and bravely take turns in looking after it while the other goes to a talk. (Actually, it is one of the best-behaved babies I have seen, and I wouldn’t object if it came to my talk.) On Tuesday, Julia talked about large-scale structures in random graphs. What is the threshold for a large structure, or for all the structures in some family, to appear in the Erdős–Rényi random graph? And when do they appear robustly, so that an adversary would have to make many changes to destroy the property? This is a fertile meeting ground of extremal and random graph theory.

Robert Morris talked about “cellular automata”, but in fact the problems he discussed were essentially percolation problems. The set-up is that, initially, a finite set of cells in the plane square lattice are “infected”; at any time, a newe cell becomes infected if all the cells obtained from it by one of a given set of translations are infected (for a simple example, at least two nearest neighbours); an infected cell remains infected. Does the whole plane eventually become infected, and if so, how fast?

Wednesday brought us two of the best talks so far. Graham Farr celebrated Tutte by a lecture on his life and his early work in graph theory, illustrated by some remarkable photographs. This prompted me to remember my closest encounter with Tutte. This was at the 1973 British Combinatorial Conference in Aberystwyth; Rosemary had already related my encounter with Donald Preece at that conference. The railway line to Aberystwyth was, as often happens, closed by a flood, and so we had to take the train to Worcester from where coaches were provided. As the bus wound along narrow roads through the Welsh hills, I went forward to have a word with someone. As I turned around to return to my seat, the bus gave an especially violent jerk, and I was thrown into Tutte’s lap.

I have always considered Tutte’s book Graph Theory as I have known it remarkable for being both a textbook on graph theory and a historical account of Tutte’s own passage through the subject, explaining the connections between the very disparate things (polynomials, network flows, spanning trees, symmetry, determinants, …), and how he was naturally led from one topic to the next. Graham certainly agreed with this assessment!

Julia Wolf introduced us to the use of entropy methods in additive combinatorics; these typically give improvements on the “energy methods” (as the earlier techniques are now called). She worked all the time in the elementary abelian 2-group, or vector space over the 2-element field, where the Fourier transform is particularly easy to understand, and its basic properties easy to prove. This was the closest plenary so far to the material at the Finite Geometry summer school last week.