The recent breakthrough of Conlon and Ferber has shown us that algebraic methods can be used in combination with probabilistic methods to improve bounds on multicolour diagonal Ramsey numbers. This was already shown for the off-diagonal Ramsey numbers by Mubayi and Verstraete last year, as discussed here. Sadly, for two colours we still don’t have any improvement over the classic probabilistic bound proved by Erdős in 1947 (except for some constant factors in front of the exponential function). More concretely, we haven’t been able to prove , for any since 1947, despite considerable effort by various mathematicians. Therefore, it might sound reasonable to think that is equal to , but the exponential improvement over the (purely ) probabilistic lower bounds on multicolour Ramsey numbers should cast some doubt on that.
In an end remark Conlon and Ferber mention that the lower bound of can be proved in a new way, using the arguments of their paper, where we have a mix of algebra and probability. This sounds like a very promising approach for further improvements as well. In this post I want to explore that, and attempt to explain why we will need some really new ideas to improve the lower bound. In the process, we will see some basic theory of bilinear forms, which is crucial to the arguments. For a more in depth exploration of the topic, see these notes of Keith Conrad and Chapter 3 of the book by Simeon Ball.
Given a vector space over a field , a bilinear form is a function , such that for any fixed , both and are linear functions. This is an abstraction of the dot product, which is so crucial in understanding the geometry of the real space . Inspired by that, we define a vector to be orthogonal to a vector if . There is a certain lack of symmetry in the definition here, namely, doesn’t necessarily imply , or in other words, we could have orthogonal to but non-orthogonal to . To fix that we introduce the notion of reflexivity and call a bilinear form reflexive if implies for all . Once have have a reflexive bilinear form we can talk about orthogonality of two vectors. From now on, will denote a reflexive bilinear form.
While this orthogonality defined in terms of reflexive bilinear forms might seem like a very general notion, it ends up being restricted to only two cases. A fundamental result, attributed to John von Neumann, states that for any vector space , a reflexive bilinear form on is of one of the following two types:
- Symmetric: for all .
- Alternating: for all .
For example, the dot product on defined by is a symmetric bilinear form, whereas the function (assuming to be even) is alternating. These examples are in fact examples of what we call non-degenerate bilinear forms, i.e., form with respect to which no vector is orthogonal to every vector of the vector space.
One interesting property of alternating forms is that they are skew symmetric. Indeed, we have for any and thus . If the characteristic of the underlying field is even, then this shows that every alternating form is in fact symmetric. The following lemma gives us a relation in the other direction as well.
Lemma 1: If is a symmetric bilinear form on a vector space over a field of characteristic , then where and the restriction of on is an alternating form.
For example, if we take over , then we can take , which is equal to the hyperplane , since for any . The form restricted to is alternating by the definition of .
One of the basic notions associated to a bilinear form is that of an isotropic subspace, which shows up in the construction of Conlon and Ferber as well, as discussed in the previous post. An isotropic subspace is a subspace such that for any two, not necessarily distinct, in (such a subspace is usually a totally isotropic but we’d ignore that here). For an arbitrary subset of , if we denote the set by , then being isotropic is the same as saying . Note that is always a vector subspace. The following is another fundamental result whose corollary is what we used in the previous post.
Lemma 2: Let be a non-degenerate reflexive bilinear form over a finite dimensional vector space . Then for any subspace , we have .
Corollary 3: An isotropic subspace with respect to a non-degenerate (reflexive) bilinear form over an dimensional vector space has dimension at most .
The max dimension of an isotropic subspace is known as the Witt index of the bilinear form. It can be shown that every non-degenerate alternating form has Witt index exactly equal to (see Theorem 3.8 in Simeon Ball’s book). This also implies that there are no non-degenerate alternating forms over odd dimensional vector spaces.
Let us now look at the graph that plays the main role in the construction of Conlon and Ferber. Let be the orthogonality graph on the set of isotropic vectors in with respect to the bilinear form , with even. Then as we saw earlier, the set of isotropic vertices form a dimensional vector subspace on which is an alternating form. Moreover, this alternating form is degenerate because is orthogonal to every other vector in since is even. As there is no other isotropic vector which is orthogonal to every other isotropic vector, the set vector space can be decomposed as such that the form induced on is a non-degenerate alternating form. Therefore, we should be able to understand this graph starting from the non-degenerate alternating form. Let’s do that and start over.
Let be an even integer, and a non-degenerate alternating form on . Let be the orthogonality graph on these vectors, that is, if . We can notice the following property.
Lemma 4: There are no independent sets of size in .
Proof. Let be an independent set, and say . Then by applying on this sum and each we get that is in the null space of . But has eigenvalues and , which are both non-zero (since is even), and thus is non-singular. Therefore, for all , and these vectors form an independent set in the vector space. This is a contradiction since the dimension of the vector space is strictly less than .
While there can’t be any large independent sets, certainly has really large cliques. Any (totally) isotropic subspace of dimension gives rise to a clique of size , and in fact these are the largest possible cliques. So, trivially does not give any good lower bound on the Ramsey number . Still, we can apply the basic idea of Conlon and Ferber (which was also the main idea of Mubayi and Verstraete) and take a random induced subgraph of , hoping that it can destroy all large cliques while giving us a graph of reasonable size. (Note that any induced subgraph will also be free of any independent sets of size .) For that, let’s first count the total number of cliques of size in .
Every clique in spans an isotropic subspace of , which has a certain rank . The number of cliques of size and rank can be bounded from above by , where the first terms correspond to choosing linearly independent members of the clique and then we pick the remaining elements from this -dimensional subspace. By simplifying, we have
This number is increasing in from until , and then decreases till , where it finally becomes (unless , which is a trivial case that we’ll ignore). But, we know that from Corollary 3, and hence for , i.e., for , and for . While we are interested in , we will soon need the estimates for smaller cliques as well.
Repeating the probabilistic argument of Conlon and Ferber, we see that if we sample each vertex independently with probability , then there exists a subset of vertices of size inducing no clique of size as long as we can ensure that . Since , we can take , which then gives us the bound on the Ramsey number . This is worse than the purely probabilistic bound of . Can we do anything better?
Here’s an idea that is extracted from the paper of Conlon and Ferber. We can look at cliques, and independent sets, of size smaller than in this graph. Perhaps for some , we can get good lower bound on by taking a random induced subgraph of that does not contain any cliques of independent sets of size .
For that, let’s count the number of independent sets of size in . For even, the proof of Lemma 4 tells us that any such set will also be an independent set of vectors. Therefore, is at most or , depending on whether is even or odd. In any case, for , we have .
Recall that we had for and for . Therefore, we see that asymptotically is always bigger than . Thus, the probabilistic argument from before gives us a subset of vertices on which the induced graph has no cliques of size and no independent sets of size as long as , and since (for large enough), it suffices to pick an for which . We can achieve this by taking where for and for .
Sadly, both of these values of are , with equality only at . Therefore, we are always worse than the basic probabilistic bound except for the case of where we can show . This asymptotically matches the probabilistic bound but we arrive at it via a different (and much more complicated) construction. For improvements, using this easy method, it looks like we’ll have to consider some other graphs. This new approach definitely gives me hope that one can find graphs with a better control on the total number of cliques and independent sets, which can then be used to give an exponential improvement in the lower bound on two-colour diagonal Ramsey numbers.