** (**I had a post a while back requesting people to submit open problems in Luca Trevisan's honor with deadline Oct 1. I am extending that to Oct 14, but that is a HARD deadline. See my original post which I have updated, here.)

And now back to our regularly scheduled program.

** ====================================**

**Breaking News**: \(R(5) \le 46 \)

I know this since 46 people have emailed me this link here.

(ADDED) Recall that \(K_n\) is the complete graph on \(n\) vertices which consists of \(n\) vertices and every single pair of vertices has an edge.

Recall that R(5) is the least n such that

*For all 2-colorings of the edges of \(K_n\) there is a set of 5 vertices such that all of the edges between them are the same color. *

Here is a history of what is known about R(5). It is not complete.

Proofs of points 1 and 2 below are on my slides here.

1) Let R(a,b) be 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.

Note that

R(2,b)=b

R(a,2)=a

It is well known that R(3,3)=6.

Is it well known that \( R(a,b) \le R(a,b-1) + R(a-1,b) \).

From this one can derive \( R(5,5) = R(5) \le 70 \)

2) One can also show that if R(a,b-1) and R(a-1,b) are even then

\( R(a,b) \le R(a-1,b) + R(a,b-1) -1 \).

From this one can derive \(R(5,5)=R(5)\le 62 \).

3) In 1989 Exoo showed \(R(5) \ge 43 \). That is, Exoo gave a 2-coloring of \(K_{42}\) with no monochromatic \(K_5\). I was unable to find his paper online; however, there is a modern exposition of his paper here.

4) In 1997 McKay and Radzisowski showed \(R(5) \le 49\). The paper is here. This used some clever math and lots of computer time. This paper also has a more complete history of R(5) up to 1997 then I have in this post. (Radzisowski also has a dynamic survey of small Ramsey numbers here.)

5) In 2017 Angelveit and McKay showed \(R(5) \le 48 \). This used some clever math of and lots of computer time. The paper is here. That is the arxiv version. The journal version is behind a paywall; however, if you want to reference it and need to know journal etc, the link is here.

6) In 2024 Angelveit and McKay showed \(R(5) \le 46 \). This used some clever math and and a big computer search. The paper is here. (ADDED LATER - they used Glucose, a SAT Solver.)

COMMENTS ON ALL THIS

1) It is widely believed that R(5)=43.

2) I have been asked if AI or SAT Solvers will help. I asked Radziowski and Angelveit and McKay and they all thought NO. There is just no way around ALL those possiblities.

**Lance**: Getting 46 via an extensive computer search using "30 years of CPU time." Hard to believe AI and SAT Solvers won't play some role in future advances.

**Bill:** Some problems are just really hard for SAT Solvers. Getting \(R(5)\le 45\) may take 3000 years of CPU time. So it may not be for a while or ever.

**Bill: **How about a wager? If R(5) =43 is proven by 2040 then you win, otherwise I win.

**Lance:** Let's make it an exact value for R(5). "Widely believed" doesn't always mean "true". What do we win?

**Bill:** Bragging rights! And the loser buys dinner.

(ADDED LATER- A commenter left a comment which probably means they want to ask the following:

**Commenter: **Since SAT Solvers did play a role in the new result, why are you skeptical that they won't play a role in getting further improvements, and perhaps finding R(5)?

**Bill: **Even with SAT Solvers, it is taking more and more time. Do you want in on the bet? If so then email me privately.

)

3) IF there is some clever math that will help a lot then an AI or a Human may find it. But I am skeptical this will happen.

4) I am surprised the bound went from 48 to 46 without a paper about 47.

5) Has any nice math come out of trying to find R(5) (and other concrete values)?

a) YES- the work on R(k) for large k has lead to nice math.

b) NO- the results above on R(5), and the math for other concrete values has largely been clever and computer work, but nothing that generalizes that much.

6) One of the Anonymous commenters pointed this out: here

Your post seems to imply that SAT solvers don't play a role, while they use Glucose in the paper.

ReplyDeleteGood point- I have added that to my post

DeleteWould be good to include $K_n$ is a complete graph with n vertices to make the R(5) problem statement complete without prerequisites.

ReplyDeleteThanks for the advice- I added it.

DeleteProblem

ReplyDeleteSolved

https://cdn.vox-cdn.com/thumbor/6yteUIDdQxwbFo2aHerioITCB6w=/1400x1400/filters:format(jpeg)/cdn.vox-cdn.com/uploads/chorus_asset/file/24418234/1456247036.jpg

So we've got 3 or 4 data points where we have some idea of the computational work needed. If we graph it out, what does it look like for how much computation may be needed for R(5)<46, 45 or even 44?

ReplyDeleteR(4) did not require any computation time, though the coloring for the lower bound took some cleverness. Past that (e.g., R(4,5)) its been really hard. For R(5) brute force won't work- even getting R(5)\le 46 took some cleverness as well as LOTS of computing time. I stand by my bet with Lance- won't be known for quite some time--- if ever.

ReplyDelete