This graph theory project will be run by Adam Sheffer. It involves a mix of mathematical proofs, algorithm design, and code writing. It continues a successful 2022 Polymath Jr project of Adam, which produced a paper. 

​​

Small Ramsey Numbers.

​

This project studies Ramsey Theory. A first example of a Ramsey statement:

 

For every six people, there exist three such that every two of the three are friends or every two are not friends.

​

We usually think of the above statement as a graph such as

​

​

​

​

​

​

​

​

A blue edge represents a friendship while a red edge represents a non-friendship. The above states that, no matter what the edge colors are, there will always be a blue triangle or a red triangle. This is true whenever there are at least six people, but not for every five people.

 

 

 

 

 

 

Formally, the Ramsey number R(3,3) is the minimum number of people to ensure a red triangle or a blue triangle. We know that R(3,3)=6. 

​

We can now ask how many people we need to have at least 4 who are all friends or all non-friends. (In graph theory, a monochromatic K₄). This is the Ramsey number R(4,4). A quote by the mathematician Joel Spencer:

​

"Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens."

​

Indeed, we still don't know the value of R(5,5). 

​

The current project.

​

Briefly, we will work on improving the current best bounds for various Ramsey problems. Specifically, on problems involving small Ramsey numbers.

​

There is a HUGE number of Ramsey problems. This survey on small Ramsey numbers is over 100 pages long. It only contains problems - no proofs or other information. Thus, we have a HUGE number of problems to choose from, at many different levels of difficulty. 

 

Adam's 2022 Polymath Jr project found the exact value of a Ramsey number. Adam originally planned to use the same approach to derive more new Ramsey bounds. However, a new breakthrough appeared recently, showing that R(5,5)≤46. It might be more exciting to study this approach and see what else can be done with it.

​

​