The 2022 Special Project

This project is defined as "special" because it is much larger than the other projects. It will include many more participants, many more mentors, and cover several different fields. More than that, some parts of the project fall under theoretical computer science ("computer-assisted proofs", "automated theorem solving", and more) while others under pure math (combinatorics, group theory, and more). Participants will be able to focus on the parts that best fit their interests. 

To make sure that participants get good support in this project, we aim for it to have a better participant-to-mentor ratio than the other projects.

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. Stanisław Radziszowski, the author of the survey, will advise us on the levels of difficulty of the different variants. More generally, we will meet with and rely on advice of many experts from around the world. 

Different problems and approaches rely on completely different tools, from different fields. You will be able to choose the problems and tools that you wish to. Just a few first examples:

  • A few years ago, Angeltveit and McKay proved the new upper bound R(5,5)≤48. This was done by a computational approach. We can study this approach and try to apply it to other small Ramsey numbers.

  • Recently, Ferdinand Ihringer improved a few small Ramsey numbers by using basic group theory. Ferdinand will be a mentor in the project, working with students who wish to explore this group theoretic approach. 

  • David Narvaez, another mentor, will work on formalizing as many of the results regarding small Ramsey numbers as possible using a combination of interactive and automated theorem provers.

  • Anurag Bishnoi will be a mentor for using pseudorandom graphs and finite geometry to improve general bounds on Ramsey numbers. 

  • Other mentors will work on improving small Ramsey numbers using more basic combinatorial proofs.

  • And more! 

ramsey-theory-2.jpg
Ramsey5.png