London Combinatorics Colloquia 2019

In London last week for the two combinatorics colloquia, at Queen Mary and LSE. The weather was unusually grey and rainy; it seems in retrospect that it is almost always fine and sunny for this event, but I know that this is a trick of memory.

Two days, with six talks on each day; as usual I will only say a bit about my favourites.

The first talk on Wednesday at Queen Mary was by Péter Pál Pach, on Polynomial Schur’s Theorem. The Schur’s theorem here is the one that says, if you colour the natural numbers with finitely many colours, there is necessarily a monochromatic solution of the equation x+y = z. His talk was about the related equation x+y = p(z), where p is a polynomial. He described the case p(z) = z2 in detail; in this case, a pointer to what follows, the statement is true for two colours but false for three or more. In general, there is one case which is easily dispatched, typefied by the polynomial p(z) = 2z2+1; the right-hand side is always odd, so if we colour the even numbers red and the odd numbers blue, there is no monochromatic solution. Excluding this and related things, the same result holds: true for two colours, false for three or more.

Julia Wolf gave a talk which made some interesting connections, about an “additive combinatorics” version of the regularity lemma. The bounds which appear in the regularity lemma are very large (tower functions, as Gowers showed). But there is a graph called the “half graph” such that excluding it makes the proof easy and the bounds polynomial. The graph has vertices xi and yi for 1 ≤ i ≤ k, with xi joined to yj if and only if i ≤ j. This (and its infinite analogue) is a familiar object in parts of combinatorics and model theory; it is the case which must be excluded to get a Ramsey theorem for bipartite graphs, and its exclusion gives what model theorists call k-stability. To get nice results for subsets of finite abelian groups, you have to exclude the half-graph from the “additive Cayley graph” of the group, whose vertices are group elements, joined if their sum lies in the special subset. Julia and her collaborators proved strong results under this hypothesis, at which point the model theorists (including Anand Pillay) got into the act, and there was a race between the two groups.

In the afternoon, a rather low-key but very entertaining talk from Keith Ball. He began by exhibiting the Hadamard matrix of order 4, normalised so that its first row is positive. Any other row has two +s and two −s. The positions of the +s and the −s in the rows give a 1-factorisation of K4. So Keith asked: for which normalised Hadamard matrices of order n (a multiple of 4) is there a 1-factorisation of Kn with a bijection between 1-factors and rows after the first such that the two ends of each edge in the 1-factor have the same entry in the corresponding row? And (different question) for which normalised Hadamard matrices is there a 1-factorisation with a bijection between 1-factors and rows sso that the two ends of each edge in the 1-factor have opposite entries in the corresponding row? He conjectures that it is always so. He showed us the proof of the conjecture for Sylvester matrices (which he called “Walsh matrices”), and certain Paley matrices (the prime p has to have the property that 2 is the square of a primitive root).

His proof for Sylvester was by induction; to get from one to the next you take the Kronecker product with the Hadamard matrix of order 2. I wondered whether the property would be preserved by arbitrary Kronecker products of Hadamard matrices. After the talk, Natalie Behague assured me that it was so, and showed me the simple proof.

The next day, at LSE, I will describe just two of the six talks. The first, by Dhruv Mubayi, was my favourite of the whole two days. He talked about classical Ramsey numbers: colour the k-sets of an N-set red and blue; how large does N have to be to guarantee either a s-set with all subsets red, or a n-set with all subsets blue? He was particularly interested in the “off-diagonal” case where k and s are fixed, and n grows. Typically, upper and lower bounds are known, and they are tower functions of heights k and k−1 respectively. He surveyed the state of the art on this.

But his real interest was a refinement, due to Erdős and Hajnal, which introduces a new parameter t, between 1 and {s choose k}. The question is, how large does N have to be to guarantee either a s-set containing at least t red k-sets, or an n-set all of whose k-subsets are blue? Erdős and Hajnal conjectured that there are “threshold” values for t, at which the value of N jumps from polynomial to exponential, and from exponential to double exponential, and so on for each possible order of the tower. Dhruv and his colleagues have shown the existence of the first threshold, and found its precise value. Dhruv explained very clearly how this is a complicated mixture of randomness and induction, and neither part can be left out.

The other talk that impressed me was by Johannes Carmesin. He started off by telling us, or reminding us, about Kuratowski’s theorem: a graph is planar if and only if it has no K5 or K3,3 minor. It was not until 2006 that Lovász thought to ask about higher-dimensional analogues. Johannes interprets this as asking what are the obstructions to embedding a 2-dimensional simplicial complex into 3-space. He developed a theory of “space minors” for 2-dimensional complexes, rather more complicated than graph minors, and gave an excluded minor characterisation of embeddability in 3-space for a simply connected, locally 3-connected 2-complex. One remarkable feature of the theorem is the proof. You show that if the excluded minors don’t occur, then you can embed the complex in a simply connected 3-dimensional manifold. Now you use Perelman’s solution to the Poincaré conjecture: this manifold must be a 3-sphere, and you are done. And there is much more beside. He also has generalisations of Whitney’s theorems, matroid interpretations of everything, and so on. I don’t usually enjoy topology, but this was a very nice talk!

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition and tagged , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.