Do I Know You?
Frank Ramsey was tangling with a mathematics problem back in 1928. In the end he realized that he should invent a whole new mathematics branch in order to find a solution to this specific problem. Unfortunately Frank Ramsey died at the age of 27, even before his findings were published. Although he won immortality as this new mathematics branch was named after him: Ramsey Theory.
One of the fundamental problems in Ramsey theory: Could one find order inside chaos? (Here, chaos is used as “disorder”.)
Ramsey theory has various applications in different mathematics branches including logic and graph theory. In this article I will be talking about how graph theory emerges with Ramsey theory.
What is needed: Randomly chosen six people.
Existing chaos: Among those six people who is friends or not friends (strangers) with whom. (Being a friend is mutual: Just because you know Sean Connery doesn’t mean that you are friends with him.)
Desired order: Set of three people among the group of six who are friends or not friends with each other.
Let’s draw the graph of these six people in which dots will represent the individuals, straight lines will represent friendship and dashed lines represent being strangers (not friends).
You might wonder where chaos is in this graph. There are over 30.000 possibilities for only six people to be or not be friends with each other. This is an enormous numbers for a very small group and the graph above shows only one possibility.
In our graph a triangle with sides that are straight lines means that three people are friends with each other. That means a triangle with sides that are dashed lines shows that three people are not friends with each other. This is why we have to look for any kind of triangles in the graph. Obviously we see multiple examples of both in our graph: For instance Bill-Rasputin-Lewinsky makes a friendship triangle as Alexandra-Lewinsky-Hürrem makes a not-friends triangle.
Now there is another important question: How can we know that all those over 30.000 possibilities possess either one of these triangles?
Yes
As it is almost impossible to try every single possibility, we have to come up with a simple and short proof.
Take Rasputin in hand: If he was friends with everyone that would mean that he had 5 friendships and 0 not friendships. All the possibilities for Rasputin are shown below:
These possibilities show us that for every individual in the group, there are at least 3 possibilities for being friends or being strangers. So, we can choose either one of them. Assume that Rasputin is friends with 3 people in the group.
At this situation in order to avoid a triangle for friendship with Rasputin, Lewinsky-Hürrem-Alexandra should be strangers with each other.
Thus, those three would provide a triangle with dashed lines: A triangle of strangers.
This proves that every one of those over 30.000 possibilities has at least one three-friend set or one three-stranger set.
If Lewinsky is friends with Hürrem, they make a friendship triangle with Rasputin. Same goes for Hürrem&Alexandra and Lewinsky-Alexandra. Thus it is impossible to avoid triangles.
One wonders…
Try to find out what would happen if we had 5 people in our group.
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 