Final project

My Final project is about graphs and it it called 'Introduction to Graph Colouring and Random Walks on Graphs'. Graph is, loosely speaking, mathematical structure used to model pairwise relations between objects. I don't want to go into details about some more involved results I studied, but I would like to share with you one particular result which I find interesting and easy to understand.

Imagine that you are throwing a party for certain people you do not know, which is not as uncommon as one would think, and you want to have at this party at least 3 people who know each other or at least 3 people who do not know each other, because group of people who know each other may safe the party and group of people who do not know each other may make it more spicy. Then you may find yourself asking: ”How many people do I have to invite to this party so I am sure that there will be either 3 people who know each other or 3 people who do not know each other?” And you may very well find yourself replying: ”I don’t know!”

After a while you may even start thinking that it is not at all obvious that there is some finite number for which this holds. But there is! Using graph theory, it is quite easy to show that to be sure to have a group of three people who do not know each other or a group of three people who know each other, we have to invite 6 people. If we want to have one group where 4 people do not know each other or one group where  4 people do know each other, we would  have to invite 18 people.

Although the above task may look easy at first glance, it is not at all so. Great mathematician of the last century, Paul Erdos, once told a story about this topic: ”Aliens invade the earth and threaten to obliterate it in a year’s time unless human beings can find R(5, 5) (the number of people we have to invite to a party to be sure that there is a group of 5 people who do not know each other or a group of 5 people who know each other). We could marshal the world’s best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded R(6, 6), however, we would have no choice but to launch a preemptive attack.”  Erdos said this more than thirty years ago, but we still do not know the answer to R(5, 5). Such an easy question: How many people do I have to invite to my party so I am sure there is a group of 5 people who do not know each other or a group of 5 people who know each other? And yet, we do not know the answer. Our world is still full of mystery, no doubt.