In Oxford at the weekend, on a rather flying visit from St Andrews, for a conference to mark Colin McDiarmid’s retirement. Colin was a student of Dominic Welsh, a tutor at Corpus Christi (the college next door to Merton), and a neighbour of mine in North Oxford for many years. The theme of the conference was “Probabilistic Combinatorics”, but that was not all that was on the menu!
I will revert to my usual practice of describing only a few of the talks.
Joel Spencer opened proceedings with a wonderful talk on the logic behind Galton–Watson trees, in particular, an explanation for why some questions about them throw up “wrong” solutions. He began with a provocative quote from Peter Jagers’ account of the history of branching processes (you can find the original here):
Rarely does a mathematical problem convey so much of the flavour of its time, colonialism and male supremacy hand in hand, as well as the underlying concern for a diminished fertility of noble families, paving the way for the crowds from the genetically dubious lower classes.
Apart from the mathematics, his talk was full of interesting terminology: “green child” (shades of Herbert Read), “old China”, “draconian fecundity”, and “strange logic” among them.
Angelika Steger talked about “robustness”. What is this? Dirac’s classical theorem about Hamiltonian cycles can be phrased like this. If you give an opponent a complete graph, and allow her to delete edges, but with the restriction that fewer than half of the edges through any vertex can be removed, the opponent cannot destroy the property of containing a Hamiltonian cycle. Accordingly, we say that the robustness of the complete graph for Hamiltonian cycles is 1/2. Angelika went on to several related problems including the square of a long cycle in a random graph.
That evening, at dinner, Dominic Welsh spoke movingly about his former student, and Colin was clearly very touched.
Next morning Alex Scott opened the proceedings, bringing us up-to-date with his joint work with Maria Chudnovsky and Paul Seymour. They are tackling questions of the form “If G is a graph with large chromatic number, must G contain either a large clique or a large (something)?” or, phrased another way. “Is it true that, in (something)-free graphs, chromatic number is bounded above by a function of clique number?” He told us quite a lot about forests of chandeliers, but in the end came to the conclusion that they are “not the answer to everything”.
For me the highlight of the meeting was the talk by Jorge Ramírez-Alfonsín. Starting from the “jugs of wine” problem, on which he had worked with Colin, he turned to aspects of the Frobenius problem: given a finite set of positive integers, which non-negative integers can be expressed as non-negative integer combinations of them? (In other words, given a set of values of stamps, which amounts of postage can be paid exactly by putting the right stamps on an envelope?) If S is this set, then S is an additive semigroup, and is also partially ordered by the relation that x ≤ y if y−x is in S. He was concerned with computing the Möbius function of this poset. Its generating function is a rational function, and is the inverse of the Hilbert series of S (analogous to the fact that the Dirichlet series of the number-theoretic Möbius function is the inverse of the Riemann zeta function).