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.

**What’s next?**

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).

Pingback: To cheer you up in difficult times 12: Asaf Ferber and David Conlon found new lower bounds for diagonal Ramsey numbers | Combinatorics and more

In the sentence: “uniformly at random and independently for all such edges”, I believe you actually mean “for all edges that do NOT fall in the previous case”.

Indeed. I’ll make it clearer. Thanks for your comment.

Anurag, do you mean each clique, i.e. each set of vectors with pairwise dot-product equal to i is a subset of a generator? How do you see that? What is your non-degenerate bilinear form? Excuse my unfamiliarity with polar spaces.

Sorry, I read that you mean only the vectors with B(.,.)=0.

I am ignoring the -freeness in colour for in this post. There are linear algebraic reasons for their non-existence, and you can see the paper of Conlon and Ferber for a proof. For the cliques in colour or , we first look at the cliques in the orthogonality graph (which is the collinearity graph of the polar space), and then see what the probability of them being monochromatic is (again, see the paper for details). Indeed, any such clique lies in a generator of the polar space. Note that the span of a clique is a totally isotropic subspace of the polar space.The non-degenerate bilinear form is (but you could take any non-degenerate form and the proof will work).

An interesting curiosity perhaps is, can you do the argument for colors 1\le i\le q-1, over finite fields which are not prime fields. Conlon-Ferber find eigenvalues over Z and then reduce modulo a prime p, so they look at the p-rank of the matrix. I don’t know what is a meaningful setting for non-prime finite fields.

The upper-bounding of the number of potential rank-r cliques in Conlon-Ferber is done over F_q^t, without regard to B(.,.)=0, they just count rank-r t-by-t matrices over F_q. Perhaps there could be some room for improvement there.

I mean they count matrices up to row permutations.

Plus, they make a choice of r linearly independent vectors. Perhaps there are several such sets of cardinality r for a fixed potential rank-r clique. That is, you could order the vectors of a potential rank-r clique, such that some r linearly independent vectors come first, potentially in more than one way.

No, sorry, I was not right. Actually they are using B(.,.)=0 in the counting, and they use the linearity of this bilinear form, since the choice for the next row is from the orthogonal complement of the first rows built.

The upper bound is asymptomatically sharp, so I don’t think there is room for improvement. The permutations, and other considerations, only help you improve lower order terms.

You mean you have a geometric argument for the number of potential r-rank t-cliques, such as subspace counts by dimension in polar spaces, right?

Without extra (geometric?) arguments sharpness is not clear to me. For example consider permutations. Consider an r-by-t MDS matrix and arbitrarily complete it into an t-by-t matrix. Now all the t! orderings of rows have the property that the first r rows are linearly independent.

The upper-bounding of in Conlon-Ferber is done for example by choosing vectors one-by-one and noticing that the next vector lies in the orthogonal complement of the span of the previous vectors. You have noticed each clique has rank up to . For sure there is at least one set of vectors in a rank clique that are linearly independent and can be chosen as the first vectors to be picked (see the counting in Conlon-Ferber). Thus each -clique is chosen at least times in this counting. This more than when $t$ is close to $t/2$. What am I missing here?

, so I don’t see exact what is the issue here. Note that we have a bound of .

Over a (non-skew) field the value of the determinant should determine the invertibility of a matrix. Therefore to do the linear algebra proof for colors i=1,…,q-1 we can do row and column operations to find a row-echelon form of the matrix and then find the determinant. I think it is non-zero whenever s is not 1 modulo p where p is the characteristic of the field.

The implication is that the Conlon-Ferber proof is valid for any finite field, so we may start with a prime power p^k and make the assumption that t is non-zero modulo p.

Indeed. Though we only need it to be true for and . For larger number of colours, you get better bounds by using Leffman’s observation instead, as they discuss in the paper.

Pingback: Bilinear forms and diagonal Ramsey numbers | Anurag's Math Blog