One of the foundational results in modern combinatorics is Ramsey’s theorem which states that for every positive integers there exists a constant such that for all , every -coloring of edges of the complete graph has a monochromatic copy of either or . The smallest for which the statement holds true is then known as the Ramsey number ; that is, for all the statement above is true and there exists a -coloring of the edges of the complete graph on vertices that avoids monochromatic and . We know the exact values of only for some small values of and . A famous example is , while despite decades of research we only known that .
Determining the Ramsey numbers for larger values has been widely open since 1940’s. It has become one of the central problems of mathematics to determine the asymptotics of with and with fixed and . An easy upper bound follows from a nice inductive prove due to Erdős and Szekeres (1947), and it shows that . In particular, this implies and (with the constant depending on ). The best upper bounds that we know are not that far away from these. David Conlon proved in 2016 that there exists a constant for which
Ajtai, Komlós and Szemerédi proved in 1980 that for every fixed there exists a constant such that
For lower bounds, Erdős proved using a probabilistic argument that
and the only improvement (since 1947) in that lower bound has been by a factor of .
In case of , with fixed, we know the following lower bound by Bohman and Keevash from 2010 that is again proved probabilistically by carefully analysing a natural random -free process:
Ignoring the log factors in the bottom, we have
Any improvement in the powers of t here would be ground-breaking. What I want to talk about in this post is a recent work of Dhruv Mubayi and Jacques Verstraete that offers us a new way of possibly improving the lower bound. Briefly, they show that if the main conjecture on pseudorandom graphs that I mentioned in an earlier post is true, then for some constant . Therefore, the existence of the optimal -free pseudorandom graphs would give us the correct polynomial in .
Here is how their proof goes. Firstly, observe that by taking one of the colour classes to define the edges of a graph, we need to construct an vertex graph that has no as subgraphs and has independence number to show . The main result that they prove is as follows:
Theorem 1. Let If there exists a -free -graph, and is large enough, then for , we have
for some constant .
The proof of Theorem 1 is not too hard if you are comfortable with the probabilistic method and you know that you should use Theorem 2.1 from Alon-Rödl. It can be summarised as: “pick each vertex uniformly at random with probability and in the induced subgraph remove one vertex from each independent set of size ”.
If the conjecture regarding -free pseudorandom graphs is true, then for every integer there exists an infinite sequence of -graphs with and . Consider such a graph for large enough. From and we get . Since , from Theorem 1 we have , and from the previous expression for in terms of we get
So, all we need to do is construct these -free pseudorandom graphs. The best construction that we have so far (discussed here) has edge density . Sadly, the lower bound that this construction gives us on is , which is worse than the probabilistic bound of Bohman and Keevash. In general, if we can construction -free optimally pseudorandom graphs with density , we will get the bound
Therefore, even a construction with density (or in fact ) would already break the Bohman-Keevash lower bound! That should be doable, right? I leave it as an open problem to the readers.
UPDATE 15th Oct 2019: Xiaoyu He has shown that the existence of these optimal -free graphs for all would also determine the multicolour Ramsey numbers with fixed for all and , up-to a poly-logarithmic factor.