Mastodawn

There's been a major advance in the asymptotic bounds for off-diagonal Ramsey numbers.

-----

The topic concerns a network of things (doesn't matter what) where each pair of things is connected with either a red or a blue line.

Consider a smaller subgroup of these things. That smaller group might contain some things connected with red lines, and some with blue lines—a largish subgroup will have a large number of lines, so probably it has some of each color.

A theorem says that for any numbers r and s, there must be a group of r of them where every pair is connected only red lines, OR a group of s where every pair is connected with only blue lined—if you just start with enough things.

For example, when r=s=3 it's known that any group of SIX things has this property: there must be a group of three connected with all red or with all blue lines. It should be obvious that 3 isn't enough to guarantee that—there are only 3 lines total, and one might be different from the others. 4 isn't enough either, as you can verify with pen and paper, and there's even a way to color all the lines among 5 things so that every group of 3 things has lines of both colors. But once you have six, there must be three where the lines connecting them are all the same color.

Similarly, when r=4 and s=3, nine things is enough. There must be a group of 4 with only red lines among them, or a group of 3 with only blue lines.

It's been a well-studied question since the 1930s to find out how many things is “enough” and how that changes depending on particular r and s. These "enough" numbers are called “Ramsey numbers” R(r,s).

“Off-diagonal” here simply means that r≠s.

#RamseyTheory

Off-diagonal Ramsey numbers

For positive integers $s$ and $k$, the Ramsey number $r(s,k)$ is the minimum integer $n$ such that any graph on $n$ vertices contains a clique of size $s$ or an independent set of size $k$. We prove that for any fixed $s \ge 3$ and $k$ tending to infinity, the off-diagonal Ramsey numbers satisfy \[ r(s, k) \ge Ω\left(\frac{k^{s-1}}{(\log k)^{2s-4}} \right), \] which matches, up to polylogarithmic factors, the upper bound established over 90 years ago by Erdős and Szekeres. For $s \ge 5,$ this improves the best known lower bound of the form $r(s, k) \ge k^{\frac{s+1}{2} + o(1)}$ which was first established by Spencer in 1977 and has since only seen polylogarithmic improvements.

arXiv.org