I’m sure many people find it crazy to believe that there is a whole field of theoretical computer science and mathematics dealing to different ways we can color edges going between dots. After all, it just looks like a bunch of scribbling. Believe it or not, there are some really cool results from these drawings which have important impacts across many different mathematical fields. A graph like the one in the picture above was one of the pieces in solving the famed Fermat’s Last Theorem.
This field is generally referred to as Ramsey Theory. Ramsey Theory studies patterns that show up if we have a large amount of stuff. In essence its saying that no matter how much disorder you can find in a system, you can find a subsystem that is perfectly ordered. That is a pretty abstract concept, so I’ll try to illuminate with a simple example.
Think of 6 people you know. They could be anyone: friends, neighbors, politicians. No matter who you choose, I can guarantee that either there are 3 of them who all know each other or there are 3 people who all don’t know each other. Try it and see. The proof of this case is actually not too bad (I’ll leave it as an exercise).
You can actually see this in action if you represent the people as dots, having blue lines between dots of people who know each other and red lines between dots who don’t know each other. Thus, the problem reduces to finding a blue or red triangle in the drawing. Below is an illustration of this concept.
As you can see from above, the diagram with 6 dots has some triangles, but the one with 5 doesn’t. So we need at least 6 people to achieve this result. A natural extension of this would be to ask how many people we need so that either 4 people all know each other or 4 people don’t know each other. Here people have calculated the number to be 18. The crazy thing is that we don’t have an exact expression for how many people we need, only various bounds. For example, to know how many people we need such that 5 people are either all friends with each other or 5 are not friends with each other is not exactly known. We know it’s between 43-48, but it takes more computing power than we have to test out all the possible combinations.
That’s why an important branch of Ramsey Theory is trying to improve on the bounds we have for the numbers required to satisfy various conditions. Right now our bounds are not great, growing exponentially as we try to find higher values. Another generalization of Ramsey Theory allows for k different colors rather than just 2 (red and blue) which leads to some very large bounds in terms of k and the size of complete subgraphs t. The simplest proof of an upper bound of the Generalized Ramsey Theorem blows up as a power tower 3^2^2^2…^2 (logn times). After some research I found a stronger bound in a 1955 paper. I then decided to try to come up with a better upper bound on my own. I actually did come up with an improvement over the current state of the art in the case where k > e*t. The link to the LaTex Document can be found here (it’s a bit technical).
Even though I’m just playing around with stuff that isn’t really practical at the moment, I love trying different ways to approach these problems. Ramsey Theory is still a relatively unexplored field with lots of improvements coming along which are all really cool. If anyone has further questions about this field or my proof feel free to contact me.