Ramsey Numbers

Ramsey’s theorem states that, for a sufficiently large complete graph, any coloring of the edges yields a monochromatic clique. Ramsey numbers, written R(r,s), give the minimum number of vertices that a complete graph must contain such that the graph contains either an r-clique of one color or an s-clique of the other color.
June 22, 2017—Hikari Sorensen

Complete Graphs

A complete graph
K
n
is a set of n vertices and
n(n-1)
2
edges such that each pair of distinct vertices is joined by an edge.
Draw a set of complete graphs on 3, 4, 5 and 6 vertices:
In[]:=
Table[CompleteGraph[n],{n,3,6}]
Out[]=

,
,
,

Notice that in general, the complete graph on
n
vertices requires exactly
n(n-1)
2
edges in order to connect each distinct pair of vertices by a unique edge.

Graph Edge Coloring

We can divide the set E of edges of a graph G into disjoint subsets of edges by using colors; each subset is then composed of edges of a particular color.
For example, we can use two colors, red and blue, to color the edges of
K
6
, the complete graph on 6 vertices. The vertices are labeled 1 through 6, and an edge joining vertices i and j is denoted by i  j.
Randomly choose a (non-empty) subset of edges to color red:
In[]:=
redEdges=RandomChoice[EdgeList[CompleteGraph[6]],RandomInteger[{1,15}]]
Out[]=
{13,36,36,23,13,25,23,15,34,16,15,35,13}
The set of blue edges is the complement of the set of red edges:
In[]:=
blueEdges=Complement[EdgeList[CompleteGraph[6]],redEdges]
Out[]=
{12,14,24,26,45,46,56}
Finally, draw the complete graph with the appropriately colored edges:
In[]:=
coloredK6=CompleteGraph[6,​​ BaseStyleDirective[Blue,Thickness0.02],​​ EdgeStyleTable[edgeRed,{edge,redEdges}],​​ VertexLabelsPlaced[Automatic,Center],​​ VertexSizeMedium,​​ VertexStyleWhite,​​ VertexLabelStyleDirective[Bold,14]​​ ]
Out[]=
In[]:=
​

Monochromatic Cliques

Ramsey’s Theorem and Ramsey Numbers

R(3,3)=6

Ramsey Numbers Are Hard to Find!

AUTHORSHIP INFORMATION
Hikari Sorensen
6/22/17
​
​
​