Ramsey theory is a fascinating subfield of combinatorics. It deals with the idea that you can find always find regular substructures in large enough arbitrary, not necessarily regular, structures. It can be considered a generalization of the Pigeonhole Principle. A simple case of the general Ramsey's theorem is the following statement: among any group of 6 people, there is either a group of 3 people who mutually know each other, or there is a group of 3 people who mutually do not know each other. Couched in graph theory, this is equivalent to the statement that for any 2-coloring of of the complete graph on 6 vertices $K_6$, there exists a subgraph of 3 vertices that is monochromatic, i.e. all the edges in the subgraph are colored with the same color.

For this simple case, the proof is quite easy. Pick a person $A$ from the group. If $A$ has $3$ or more friends, pick $3$ of them, say $B$,$C$ and $D$. If $2$ people among these friends are friends with each other, then together with $A$ they would form a group of 3 mutual friends. Otherwise $B$,$C$ and $D$ mutually do not know each other.

If $A$ has $2$ or less friends, then there are at least $3$ people who $A$ does not know and you have a similar argument. Pick $3$ among them, if they are not mutual friends, then there are $2$ of them who are not friends, then these $2$ people along with $A$ form a group who mutually do not know each other.

## Saturday, May 24, 2014

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment