Ramsey Theorem
Ramsey Theory
http://www.cs.umd.edu/~gasarch/ramsey/Robertsapp.pdf
This is a paper talking about application of Ramsey Theory in computer science. Frank Ramsey was a mathematician from the 1920s who studied some areas of philosophy and mathematics. Ramsey’s theory is a theorem in combinatorics that says that given a coloring of a sufficiently large complete graph, there will exist a smaller complete monochromatic subgraph. More generally put, this means that there is no such thing as chaos in graph theory. As things get large, order appears.
The most well known example of Ramsey theory is the fact that clique (complete graph of people) where each edge represents that the two people know each other or they do not know each. By Ramsey theory, there exists at least three people who either all know each other or all do not know each other.
There is a simple proof of this. Suppose we look at the friendships of person A. Since there are 5 other people then he must either know at least three of them or not know at least three of them by the pigeonhole principle. Suppose he knows at least three of them (it doesn’t matter how we choose the coloring). Let us label three of the people that he knows as persons B, C, and D. If B and C know each other then we have the triangle ABC, if B and D know each other then we have the triangle ABD, if C and D know each other then we have the ACD. There are all triangles of people that all know each other. If B, C, and D all do not know each other then there is a triangle of three people that do not know each other.
While this is just a small example of Ramsey theory on six vertices and two colorings, it is easy to see how there could be applications to analyzing data on large-scale social networks. For example, if we expand the same example to eighteen people then we know that there must be at least a group of four people that either all know each other or all do not know each other. Several high Ramsey Numbers have not yet been determined but they may prove to be useful in studying social networks and networks in general.