Sunday, September 10, 2023

Asymptotics of R(4,k)- a new result!

 At the workshop 

Ramsey Theory: Yesterday, Today, and Tomorrow, Edited by Alexander Soifer, 2011. (There is a printed proceedings that you can find.)

 I saw Joel Spencer give a great talk titled 

                               80 years of R(3,k).

( Recall that  R(a,b) is the least n such that for all 2-colorings of the edges of K_n there is either a red K_a or a blue K_b).

 The talk was about improvements on both the upper and lower bound on R(3,k) and finally:

                                  R(3,k) = \(\Theta\biggl (\frac{k^2}{\ln^2 k}\biggr )\).

The obvious question was raised: What about R(4,k). The general sense I got was that this would be a much harder problem. However, there has been some progress. A recent paper, here, improved the best known lower bound, so it now stands at

                                   \( c_1\frac{k^3}{\log^4 k} \le r(4,k) \le c_2\frac{k^3}{\log^2 k} \)

How long before we see matching upper and lower bounds?

1) How long did it take to get matching upper and lower bounds for R(3,k). The name of the talk would make one think 80 years, but I would start at a paper of Erdos from 1961 which had the first non-trivial lower bounds. And it was solved in 1995, so that's 34 years. (Note, the talk of Spencer was also on later algorithmic aspects of the problem). 

2) Argument for why matching bounds on R(4,k)  will be found  in \(\le 10\) years: There are more people using more sophisticated tools then were known for the R(3,k) search.

3) Argument for why matching bounds on R(4,k) will take (\ge 20\) years: This problem is dang hard! Triangles are much easier to deal with then  4-cliques.

This is a general problem math has: If a problem is not been solved, is it just dang hard, or are people one or two (or some small finite number) steps away from solving it?

No comments:

Post a Comment