Improved lower bounds for multicolour diagonal Ramsey numbers

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 3 (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 \geq 4 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 R(t; \ell) is the minimum n such that any colouring of the edges of K_n using \ell colours gives rise to a monochromatic K_t, 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 \ell = 2), the best upper bound we have for all \ell \geq 3 is R(t; \ell) \leq \ell^{\ell t}, and improving the base of the exponent from \ell^\ell to anything smaller seems out of reach by our current methods. As far as the lower bounds are concerned, the best lower bounds for \ell = 3, 4 are R(t; 3) \geq (\sqrt{3})^t and R(t;4) \geq 2^t, as shown by Erdős in 1940’s. For larger \ell, one can improve the lower bound of R(t;\ell) \geq \sqrt{\ell}^t by using the following observation of Leffman:

R(t; \ell_1 + \ell_2) - 1 \geq (R(t;\ell_1) - 1)(R(t;\ell_2) - 1).

Conlon and Ferber improve all of these bounds as a corollary to the following result:

Theorem 1. For any prime p, R(t; p + 1) > 2^{t/2} p^{t/3 + o(t)}.

This, along with Leffman’s observation, gives an exponential improvement for the known lower bound on R(t;\ell) for all \ell \geq 3.

As the appearance of the prime p 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 p, R(t; p + 1) > 2^{t/2} p^{3t/8 + o(t)}.

Note that this is an exponential improvement. Let’s see how we can prove this.

Let p be a prime, and let V be the set of all isotropic vectors in \mathbb{F}_p^t with respect to the symmetric bilinear form B(x, y) = x_1 y_1 + \cdots + x_t y_t. In other words, V = \{(x_1, \dots, x_t) \in \mathbb{F}_p^t : x_1^2 + \cdots + x_t^2 = 0\}. It is well known, and in fact not so hard to show, that |V| \sim p^{t - 1}. Though all we need for the bounds is that |V| = p^{t - O(1)}, which is what Conlon and Ferber show in their paper (more precisely, they show |V| \geq p^{t-2}). Consider the following edge colouring of the complete graph on V: the edge \{x, y\} is coloured with i \in \mathbb{Z} if B(x, y) = i  \pmod{p} with i \neq 0, and if B(x, y) = 0 then it is coloured from the set \{p, p + 1\} uniformly at random and independently for all such edges. Thus we have a (p + 1)-colouring of the complete graph on |V| vertices, where the colours are just the integers 1, \dots, p + 1.

In each colour 1 \leq i \leq p - 1 we can show algebraically that the graph on these edges has no cliques of size larger than t, assuming t is not divisible p, which we will assume (for the exact argument see the paper of Conlon and Ferber). Therefore, we are aiming for a lower bound on R(t+1; \ell), but asymptotically it would be the same for R(t; \ell). Now with the random colouring in the last two colours, Conlon and Ferber show that for n = 2^{t/2}p^{t/3 + o(t)}, there exists a subset of V of size n such that the complete graph on these vertices, with the same edge-colouring as before, has no monochromatic clique of size t in colours p or p + 1. This is done by choosing a random subset where each vertex is chosen with a certain probability which is a function of n. 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 n, is an upper bound on the number of cliques of size t in the graph defined on V where two vectors are adjacent if they are orthogonal to each other, that is, x \sim y if B(x, y) = 0. Note that in our edge colouring, the edges of this graph were the ones that got colours from \{p, p + 1\}. Let’s denote this number by N_t. Each such clique is a collection x_1, \dots, x_t of vectors in \mathbb{F}_p^t such that B(x_i, x_j) = 0 for all 1 \leq i \leq j \leq t. Conlon and Ferber estimate the number N_{t, r} of such cliques that have rank r, that is, the dimension of the space spanned by x_1, \dots, x_t is r, by N_{t, r} \leq p^{2tr - 3r^2/2 + r/2}, and then just use the upper bound N_t = \sum_{r = 1}^{t} N_{t, r} \leq t \max_{r = 1}^t N_{t, r}.

Until this point it’s all fine, but what we can improve upon is the argument that follows. They say that N_{t, r} is maximized for r = 2t/3 + 1/6 (which is not at all hard to see) and thus conclude that N_t \leq p^{2t^2/3 + o(t^2)}. But they miss a crucial linear algebraic fact at this point. The rank of a clique can never be larger than t/2. This is an easy fact that follows from (i) \dim S + \dim S^\perp = t for any subspace S, and (ii) S \subseteq S^\perp 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 N_t \leq t N_{t, t/2} \leq p^{5t^2/8 + o(t^2)}. After this, if you do the calculation of Conlon-Ferber then you’ll see that we can take n = p^{3t^2/8  + o(t^2)}, thus proving Theorem A. \square

Remark: If you are familiar with the theory of polar spaces, then you can easily estimate this number N_t, 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 \ell \geq 4 colours (see this).

About Anurag Bishnoi

A mathematician working at UWA Perth as a postdoc. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Extremal Combinatorics, Finite Geometry, Incidence Geometry, Ramsey Theory and tagged , , , , , , . Bookmark the permalink.

19 Responses to Improved lower bounds for multicolour diagonal Ramsey numbers

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

  2. Fabricio Benevides says:

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

  3. Ago-Erik Riet says:

    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.

    • Ago-Erik Riet says:

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

      • I am ignoring the K_{t+1}-freeness in colour i for i = 1, \dots, p - 1 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 p or p + 1, 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 B(x, y) = x_1y_1 + \cdots + x_n y_n (but you could take any non-degenerate form and the proof will work).

      • Ago-Erik Riet says:

        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.

  4. Ago-Erik Riet says:

    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.

    • Ago-Erik Riet says:

      I mean they count matrices up to row permutations.

      • Ago-Erik Riet says:

        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.

    • Ago-Erik Riet says:

      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.

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

    • Ago-Erik Riet says:

      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?

    • Ago-Erik Riet says:

      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.

    • Ago-Erik Riet says:

      The upper-bounding of N_{t,r} 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 t/2. For sure there is at least one set of r vectors in a rank r clique that are linearly independent and can be chosen as the first vectors to be picked (see the counting in Conlon-Ferber). Thus each t-clique is chosen at least r!(t-r)! times in this counting. This more than (t/6)^t when $t$ is close to $t/2$. What am I missing here?

  6. Ago-Erik Riet says:

    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.

    • Ago-Erik Riet says:

      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 p = 2 and p = 3. For larger number of colours, you get better bounds by using Leffman’s observation instead, as they discuss in the paper.

Leave a Reply

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

WordPress.com Logo

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

Google photo

You are commenting using your Google 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