London Combinatorics Colloquia 2023

In London last week for this (usually) annual event, now happily back live. In contrast to usual practice, I will discuss the second day first.

Norman Biggs was the founder of the combinatorics group at the London School of Economics, and so the LSE day this year was devoted to celebrating his 80th birthday (even though he is now 81). Unfortunately he was not well enough to travel in for the event, but we did get to see a video he had recorded (after some technical problems had been resolved). Norman had known Bill Tutte well, and he told us about Tutte’s work at Bletchley Park during the second world war, details of which were not made public until 2000, by which time the public perception was that Alan Turing was the hero of Bletchley Park. Turing had an actual Enigma machine to work on, brought to Britain by the Polish cryptographers who had studied it before the war. By contrast, Tutte worked on the Lorenz cipher machine, more complicated than the Enigma and used for the highest level communications between Hitler and his generals, even though nobody in Britain had ever seen this machine (Tutte first saw it in 1947). Tutte was able to work out the details of the machine, including all the wheel sizes, from a string of key which had been obtained as a result of an error by a German radio operator. Norman couldn’t explain precisely what Tutte did, but was able to show us one of Tutte’s working diagrams.

Also, because of the event for Norman Biggs, there were other oldies speaking: Robin Wilson, Martin Anthony, and Paul Seymour (though I regard Paul as a youngster). Robin started to tell us about the main developments in graph theory in the century from 1890 to 1990, though he only got as far as about 1970 because of the time lost to the technical problems. Martin told us about his work on machine learning, where the positive and negative training instances are not cut and dried but are weighted according to, for example, the margin between the instance and the boundary between positive and negative (if the classifiers are real valued) or what he called “sample width” (if they are Boolean). Paul told us about a variant of tree decomposition of a graph where the subgraphs in the “bags” are required to be, not just connected, but of bounded diameter. (An interesting side story: he and his colleague Eli Berger had proved a nice theorem, but had just been scooped, so they simply sat down and proved an even stronger theorem.)

The day also included two talks on the G_n,p random graph model: Annika Heckel on concentration results for the chromatic number when p = ½, and Nina Kamčev on canonical colourings (in the Erdős–Rényi sense).

At the Queen Mary day the previous day, there were many very nice talks, so it is hard for me to choose. Carla Groenland talked about skipless chains in the Boolean lattice (where the ranks of the chains form an interval); the main theorem states that the union of m disjoint chains can be covered by m disjoint skipless chains (so that Dilworth’s Theorem holds for skipless chains). She wondered whether this could be true in other lattices; of course I wondered about projective spaces.

My colleague Louis Theran works on rigidity of frameworks, but is always open to connections and relations with other areas. He told us about Gaussian graphical models where you have some data on n-dimensional space and an n-vertex graph, and you want a maximum likelihood estimate if the covariance matrix is constrained to be zero on non-edges of the graph; the question of interest is: What is the minimum number of datapoints you need for an MLE to exist? This is called the maximum likelihood threshold (MLT) of the graph. Louis showed us that it is related to global rigidity of the graph. He proposed a better version which looks at (d+2)-vertex subgraphs (a paradigm in rigidity theory).

Torsten Mütze talked about the conjecture of Lovász that, with five known exceptions, any vertex-transitive graph has a Hamilton cycle (and mentioned the competing conjecture of Babai that there is a positive ε with the property that infinitely many vertex-transitive graphs have no cycle longer than (1−ε)n, where n is the number of vertices. He was able to prove that Lovász was right for various graphs in the Johnson association scheme (still a very long way from resolving the question, in my view).

Thomas Bloom gave us an entertaining survey of the past, present and possible future of work on counting 3-term arithmetic progressions in large subsets of {1,…,n}.

I sometimes wonder why I write summaries like this. I think it is as backup memory; if I write down what I learn, or even just a brief summary, I have a better chance of finding it again in the future.