London Combinatorics Colloquia

The second speaker at this year’s Queen Mary colloquium, János Pach, said at the start of his talk that he first came to Britain as a backpacker some years ago; at that time he never imagined that by now there would be enough combinatorialists here to fill the quite large Peston Lecture Theatre in the Graduate Centre.

He was kind enough to mention me as one of the people who had helped bring this about, but (quite rightly) attributed a lot of credit to Paul Erdős and Bill Tutte. He told Bruce Schechter’s story about how Erdős had changed the course of Western civilisation, which bears repeating, I think. Erdős, seeing which way the wind was blowing, left Hungary in 1934. His first stop was Cambridge, where he posed the problem of tiling a square with finitely many pairwise non-congruent squares. (There is some suggestion that Erdős thought that it would turn out to be impossible.) Four bright undergraduates, Brooks, Smith, Stone and Tutte, took up the challenge, and found an elegant method that led them to the existence of such a decomposition. This success inspired Tutte to change from chemistry to mathematics. At this he made enough of an impression that he was recruited for Bletchley Park, where he broke the Lorenz Sägefisch cipher used for strategic communications by the German high command, which according to some historians may have shortened the war by a couple of years.

Since I have started with János Pach’s talk, I will say more about it. His abstract on the website and in the conference book said, simply,

This will be the bestest talk ever.

An insert gave a much more detailed abstract. In his talk, he disclaimed all responsibility for the short abstract, but said it would probably be the best part of the talk, and that things would be downhill from here on. Not so, in fact; for me, his talk was the best of the day, even if it ran over time a bit. He was talking about the analogous problem for tiling an equilateral triangle with pairwise non-congruent equilateral triangles. He and Gabor Tardos have proved that there is no such tiling, by a remarkable proof, which begins with some elementary geometry, and then wheels in random walks and martingales!

Carsten Thomassen spoke first, and told us about several new results on flows on graphs, where the flow values are restricted to a subset F of an abelian group A. (Incidentally, Carsten used G for a graph and Γ for a group; I had to change Γ to A in my notes so as not to confuse myself.) As well as the set of non-zero elements of a finite abelian group, he considered cases such as the set of third (or fifth) roots of unity in the complex plane, or the unit sphere in 2- or 3-dimensional Euclidean space.

After lunch, we had a Ramsey theory talk from Paul Russell. He began by showing us that, if the natural numbers are finitely coloured, there is an infinite subset such that all sums of two distinct elements have the same colour. Can you make the same statement for all subsets? No, he showed us ingenious constructions which refute this. These can be extended to the integers, the rationals, and finite or countable dimensional vector spaces over the rationals; but in very large vector spaces, the constructions don’t work, and the assertion holds.

Katherine Staden talked about the induced version of Turán’s theorem, maximising the number of induced subgraphs of a graph which are isomorphic to your favourite graph F. (This corresponds to the complement of Turán’s theorem as usually stated.) The induced condition makes the problem much harder; the answer is not even known for the four-vertex path. She considered the case where F is complete partite (that is, there is a partition of the vertex set so that F has all edges between parts and none within parts). In this case, the extremal graphs are partite, and there are uniqueness and stability results, proved by turning the question into an algebraic optimisation problem.

Agelos Georgakopoulos (who had to pull out at short notice last year because of the birth of his baby) talked about some nice results on the analyticity of the percolation probability function above the critical point. The tools are old theorems of Weierstrass together with some combinatorics (inclusion-exclusion, estimates for the partition function). He began with a growth model for the mafia, having the remarkable property that there is a finite limit graph which occurs almost surely as a limit component.

Finally, Nikhil Bansal spoke on the discrepancy problem: you have a family of subsets of a set, and you want to 2-colour the set so that each subset is as balanced as posisble. There was a fairly recent breakthrough on this problem by Banaszczyk; Nikhil and his collaborators have found a simpler proof together with an algorithmic version which efficiently finds a colouring doing as well as the theory promises.

The weather is always beautiful for the London colloquia; this indeed goes back to the days when its predecessor used to be in Reading. It rained overnight but by morning the weather was fine again, a little cooler and a little clearer than the day before.

The second day, at LSE, featured an innovation: a poster competition, with a lot of entrants, which was judged by a subset of the speakers, and the prizewinners announced at the reception at the end of the day.

The first talk, by Perlis Sousi, was on random walks on dynamic percolation. People have considered random walks on the component containing the identity of graphs such as lattices (this component is infinite if the percolation probability is above the critical value). The new feature was letting edges change their status, independently of what it was before but with the same probability of being open; to make the question interesting, we assume that these changes are on a slower timescale than the movement of the random walker. (I wonder what would happen if you let the edges change faster but assumed some positive correlation between the new and old state of the edge.)

Patrice Ossona de Mendez has been working with Jarik Nešetřil and many others (incuding one of our hosts, Jan van den Heuvel) on sparsity in graph theory for some years now. They have developed two concepts of sparsity, called “bounded expansion” and “nowhere dense”, which turn out to be stable in the sense that a huge variety of alternative definitions come up with the same thing. He talked about five questions, concerning graph colouring, Hasse diagrams of posets, VC-dimension of families induced on subsets by vertex neighbourhoods, category theory, and first-order definability. Then he defined some new concepts called “structurally X”, where X is one of the two types of sparse graph; such graphs can be quite dense but many results about them (including complexity) work similarly to the sparse case. As usual with Patrice, it was an elegant talk, but there was rather a lot of material to take in.

After lunch, Sofia Lindqvist gave an assured performance on her result with Ben Green on monochromatic solutions to x+y = z² in the natural numbers. They have found a phenomenon which to my knowledge has not been observed before: the answer is that they must exist for two colours, but can be avoided for three or more.

Maria Axenovich talked about induced arboricity. The arboricity of a graph is the least number of forests needed to cover all the edges of the graph. This is a well-understood parameter, and a theorem of Nash-Williams gives a formula for it. For induced arboricity, you require the subgraphs to be induced forests, which makes things far more complicated.

It is easy to see that a graph with maximum degree Δ can be coloured with Δ+1 colours (a sequential algorithm does this since there is always a colour available). Choosing a random colouring is different, and a Markov chain based on recolouring a vertex if possible requires at least Δ+2 colours (and it is conjectured that this is enough for the Markov chain, or “Glauber dynamics” as it is known, to be rapidly mixing. However, the best we knew until recently was a result of Vigoda that (11/6)Δ is enough for rapid mixing. Michelle Delcourt and her team have shaved a bit off this constant. Within a week of their result being announced, another team announced that with a different method they had shaved a bit more off.

The final talk, the Norman Biggs lecture, was given by Alexander Sidorenko, who pulled a remarkable rabbit out of a hat. He talked about two apparently unrelated areas: first, the largest Sidon set (containing no solutions of x+y = z+w), or set containing no subset summing to zero, or containing no arithmetic progression, in certain finite abelian groups. Last year there was an amazing breakthrough on the “no 3-AP problem” in abelian groups of exponent 3. The other problem was the “codegree Turán problem” for hypergraphs. He showed how results on the first type of problem can give substantially improved bounds for the second.