Big news in combinatorics today: David Conlon and Asaf Ferber have posted a 4-page preprint on arXiv that gives exponential improvements in the lower bounds on multicolour diagonal Ramsey numbers, when the number of colours is at least (also see the post by Gil Kalai). The best known lower bounds so far were completely probabilistic, combined with an inductive argument of Leffman that gave better bounds for colours. The new construction on the other hand has a deterministic part to it, which in fact uses finite geometry. In this post I’ll describe their construction, and also show how to improve their bounds further using a simple observation.
The multicolour Ramsey number is the minimum such that any colouring of the edges of using colours gives rise to a monochromatic , which is known to exist by Ramsey’s theorem. Ignoring the lower order terms (which is what the big recent breakthrough of Ashwin Sah improved for ), the best upper bound we have for all is , and improving the base of the exponent from to anything smaller seems out of reach by our current methods. As far as the lower bounds are concerned, the best lower bounds for are and , as shown by Erdős in 1940’s. For larger , one can improve the lower bound of by using the following observation of Leffman:
Conlon and Ferber improve all of these bounds as a corollary to the following result:
Theorem 1. For any prime , .
This, along with Leffman’s observation, gives an exponential improvement for the known lower bound on for all .
As the appearance of the prime in this result might suggest, it uses finite fields. In fact, it uses the basic theory of polar spaces/quadratic forms over finite fields. By giving more precise estimate on a certain count in their proof, I can show the following:
Theorem A. For any prime , .
Note that this is an exponential improvement. Let’s see how we can prove this.
Let be a prime, and let be the set of all isotropic vectors in with respect to the symmetric bilinear form . In other words, . It is well known, and in fact not so hard to show, that . Though all we need for the bounds is that , which is what Conlon and Ferber show in their paper (more precisely, they show ). Consider the following edge colouring of the complete graph on : the edge is coloured with if with , and if then it is coloured from the set uniformly at random and independently for all such edges. Thus we have a -colouring of the complete graph on vertices, where the colours are just the integers .
In each colour we can show algebraically that the graph on these edges has no cliques of size larger than , assuming is not divisible , which we will assume (for the exact argument see the paper of Conlon and Ferber). Therefore, we are aiming for a lower bound on , but asymptotically it would be the same for . Now with the random colouring in the last two colours, Conlon and Ferber show that for , there exists a subset of of size such that the complete graph on these vertices, with the same edge-colouring as before, has no monochromatic clique of size in colours or . This is done by choosing a random subset where each vertex is chosen with a certain probability which is a function of . Therefore, we have a random colouring of certain pairs of vectors, and a random subset of all the isotropic vectors.
A crucial step in the estimation used in the proof, that leads to this particular choice of , is an upper bound on the number of cliques of size in the graph defined on where two vectors are adjacent if they are orthogonal to each other, that is, if . Note that in our edge colouring, the edges of this graph were the ones that got colours from . Let’s denote this number by . Each such clique is a collection of vectors in such that for all . Conlon and Ferber estimate the number of such cliques that have rank , that is, the dimension of the space spanned by is , by , and then just use the upper bound .
Until this point it’s all fine, but what we can improve upon is the argument that follows. They say that is maximized for (which is not at all hard to see) and thus conclude that . But they miss a crucial linear algebraic fact at this point. The rank of a clique can never be larger than . This is an easy fact that follows from (i) for any subspace , and (ii) for a totally isotropic subspace, which is exactly what the span of the vectors forming the clique is going to be. In terms of the theory of polar spaces (or quadratic forms), it says that the rank of a polar space is always at most half of the dimension of the underlying vector space (something all the finite geometers must be familiar with). From this we see that . After this, if you do the calculation of Conlon-Ferber then you’ll see that we can take , thus proving Theorem A.
Remark: If you are familiar with the theory of polar spaces, then you can easily estimate this number , as each such clique must be contained in a generator (maximal totally isotropic subspaces) and you can count the total number of generators (see for example Theorem 4.11 in the book by Simeon Ball). Depending on the type of the polar space, you can even get an exact count but here we are just interested in the asymptotic results.
I think it’s really exciting that finite geometry, or in fact anything not completely probabilistic, can be used in the case of diagonal Ramsey numbers to improve the known bounds. This was recently shown to be true for the two-colour off-diagonal case by Mubayi and Verstraete, which was extended to multicolours by He and Wigderson, as I describe here and here. Therefore, finite geometry is paying a crucial role in developing Ramsey theory. I think a deeper understanding of these constructions, and new ideas from finite geometry (perhaps group theoretic ones) can lead to even further progress.
Update 28/09/20: Yuval Wigderson has managed to improve the bound further for colours (see this).