Ramsey’s Theorem

Ramsey’s theorem states that for any complete graph, there exists some number such that any edge 2-coloring yields a complete subgraph of that size in one of the colors, or informally, “complete disorder is impossible”.
June 21, 2017—Dennis Hou

Friends and Strangers

We begin by looking a famous special case of Ramsey’s theorem (the theorem on friends and strangers) which states that in a group of six people, either three people mutually know each other or three people mutually do not know each other.
Make a complete graph with six vertices:
In[]:=
CompleteGraph[6]
Out[]=
The theorem begins with six people at a party, so we label each vertex to represent a person.
Label vertices on the graph:
In[]:=
CompleteGraph[6,VertexLabels{1Alice,2Bob,3Carol,4Dan,5Erin,6Frank}]
Out[]=
Now assume these people are either mutually friends or strangers. We can use two colors to represent the relations.
Color edges on the graph:
In[]:=
HighlightGraph[CompleteGraph[6,VertexLabels{1Alice,2Bob,3Carol,4Dan,5Erin,6Frank}],{12,15,23,24,35,45,46}]
Out[]=
A blue edge means two people are friends, while a red edge means they are strangers. Now let us separate the two graphs.
Draw the subgraph with only the red edges:
In[]:=
Graph[{12,15,23,24,35,45,46},VertexLabels{1Alice,2Bob,3Carol,4Dan,5Erin,6Frank},EdgeStyleRed]​​
Out[]=
Draw the complete graph with the red edges removed:
In[]:=
EdgeDelete[CompleteGraph[6,VertexLabels->{1Alice,2Bob,3Carol,4Dan,5Erin,6Frank}],{12,15,23,24,35,45,46}]
Out[]=
We first check the red subgraph for complete subgraphs with three vertices.
Find any cliques of at least three vertices in the red subgraph:
In[]:=
FindClique[Graph[{12,15,23,24,35,45,46}],{3,6}]
Out[]=
{}
The theorem on friends and strangers tells us that since the red subgraph has no complete subgraphs of size 3, then the blue subgraph must.
Find any cliques of at least three vertices in the blue subgraph:
In[]:=
FindClique[EdgeDelete[CompleteGraph[6],{12,15,23,24,35,45,46}],{3,6}]
Out[]=
{{1,3,6}}
Highlight the clique with thick edges:
In[]:=
HighlightGraph
,StyleSubgraph
,FindClique[EdgeDelete[CompleteGraph[6],{12,15,23,24,35,45,46}],{3,6}],{Blue,Thick}
Display the 2-colored complete graph and highlight the clique with thick edges:
We can try some more examples. Since any 2-coloring will work, we can randomly select an edge set from the graph to represent the other color.
Choose a random edge subset from the complete graph:
Display the 2-colored complete graph, and highlight cliques of either color with thick edges:
Define a function to display the 2-colored complete graph and highlight cliques of either color with thick edges:
Apply the function to thirty random-edge subsets:

Ramsey Numbers

Non-Diagonal Ramsey Numbers

FURTHER EXPLORATIONS
Generalized and Hypergraph Ramsey Numbers
Schur Numbers
Distributed Computing in Case of Alien Invasion
AUTHORSHIP INFORMATION
Dennis Hou
6/21/17