Who Knows Who?

There’s a nice area of math called Ramsey Theory which is quite rich in its ideas. It’s a sub-section of graph theory, and a here’s a proof for one of the most fundamental ideas which comprises this field, which can give you an interesting taste of the concepts in it.

In any party of six people either at least three of them are  (pairwise) mutual strangers or at least three of them are (pairwise) mutual acquaintances.

Ramsey.png

If you are not familiar with graph theory, it basically consists of the analysis of nodes and edges, and everything about them (it’s not an x and y-axis like you may have thought). One of the best parts of this is that you get to draw a lot. First we should give each person a node, and each person is connected to another with either a blue or red edge. Blue can signify that these two people know each other, and red means that they don’t. Therefore each possible edge has to be drawn and has to be one of the two colors.

If we take one particular person, he/she will be connected to the other 5 people with 5 edges, and by the pigeonhole principle we know that there have to be at least 3 edges of the same color in these 5 since there are only two possible colors. So let’s say that A is connected to B, C, and E by blue edges (AB, AC, and AE). If we consider the edges between B, C, and E (BC, CE, and BE), we know that either all three are of one color, or there are edges of both colors. If there is any edge which is blue, we have completed a triangle, because AB, AC, and AE are already blue, so for example if CE is blue, A, C, and E form a triangle which are pair-wise acquaintances. So what if there are no blue edges between B, C, and E? Well then they must all be red, meaning then that they form their own triangle of pair-wise strangers. This means that for any set of 6 people, there has to be a set of 3 people who are either all friends or all strangers when taken in pairs. If it is hard to visualize it, always just try drawing it out.  Are you starting to get how powerful a graph can be at modeling things?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s