Ramsey Numbers
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.
Complete Graphs
Complete Graphs
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 2 colors, red and blue, to color the edges of, 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.
For example, we can use 2 colors, red and blue, to color the edges of
K
6
◼
Draw a dynamic, 2-colorable .
K
6
6/23/17 18:52:01 In[463]:=
Table[ CompleteGraph[ n ], {n, 3, 6} ]
6/23/17 18:52:01 Out[463]=
,
,
,
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 2 colors, red and blue, to color the edges of, 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.
For example, we can use 2 colors, red and blue, to color the edges of
K
6
Graph Edge Coloring
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 2 colors, red and blue, to color the edges of, 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.
For example, we can use 2 colors, red and blue, to color the edges of
K
6
◼
Draw a dynamic, 2-colorable .
K
6
6/23/17 18:52:01 In[464]:=
redEdges = RandomChoice[ EdgeList[ CompleteGraph[6] ], RandomInteger[ {1, 15} ] ]
6/23/17 18:52:01 Out[464]=
{13,36,36,23,13,25,23,15,34,16,15,35,13}
◼
Draw a dynamic, 2-colorable .
K
6
6/23/17 18:52:01 In[465]:=
blueEdges = Complement[ EdgeList[ CompleteGraph[6] ], redEdges ]
6/23/17 18:52:01 Out[465]=
{12,14,24,26,45,46,56}
◼
Draw a dynamic, 2-colorable .
K
6
6/23/17 18:52:02 In[466]:=
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 ] ]
6/23/17 18:52:02 Out[466]=
6/21/17 16:53:44 In[57]:=
Monochromatic Cliques
Monochromatic Cliques
A monochromatic clique is a subgraph H of some graph G that is itself a complete graph, and in which all edges are the same color. That is, it is a graph on a subset of the vertices of H such that every distinct pair of vertices is connected by an edge, and the entire graph contains only one color.
◼
Draw a dynamic, 2-colorable .
K
6
6/23/17 18:52:02 In[467]:=
MapThread[ Table[ HighlightGraph[ coloredK6, Style[ Subgraph[#1, clique], Directive[#2, "Thickness" -> .05, Opacity[1] ] ] ], {clique, FindClique[#1, { 3, Infinity }, All ]} ]&, {{blueEdges, redEdges}, {Darker[Green], Orange}}]
6/23/17 18:52:03 Out[467]=
,
,
,
,
,
In the above image, monochromatic cliques are highlighted. Green-highlighted edges correspond to blue monochromatic cliques, and orange-highlighted edges correspond to red monochromatic cliques. Note that if a monochromatic clique contains 3 or more vertices, then it also contains as subgraphs all monochromatic cliques of fewer vertices.
If there are no cliques shown of either green or orange, then the graph contains no monochromatic cliques corresponding color.
If there are no cliques shown of either green or orange, then the graph contains no monochromatic cliques corresponding color.
Ramsey’s Theorem and Ramsey Numbers
Ramsey’s Theorem and Ramsey Numbers
The main statement Ramsey’s theorem makes is that, if a complete graph is large enough, then no matter how the edges are colored, we will always be able to find a monochromatic clique contained in the graph.
The Ramsey Numbers R( r, s ) give the smallest number of vertices that must be contained in a graph so that the graph contains a clique on r vertices of one color (say, red), or a clique on s vertices of the other color (blue).
The Ramsey Numbers R( r, s ) give the smallest number of vertices that must be contained in a graph so that the graph contains a clique on r vertices of one color (say, red), or a clique on s vertices of the other color (blue).
R( 3 , 3 ) = 6
R( 3 , 3 ) = 6
For example, the Ramsey Number R( 3, 3 ) = 6. That is, the smallest complete 2-colored graph that is guaranteed to contain a monochromatic clique of 3 vertices, no matter how the graph is colored, has 6 vertices.
To see this firsthand, we can try to 2-color in any way. Notice that every coloring will always yield at least one clique of at least 3 vertices.
To see this firsthand, we can try to 2-color
K
6
◼
Draw a dynamic, 2-colorable .
K
6
6/23/17 18:52:03 In[468]:=
allEdges6 = EdgeList[ CompleteGraph[6] ]
6/23/17 18:52:03 Out[468]=
{12,13,14,15,16,23,24,25,26,34,35,36,45,46,56}
Use the toggle bar to turn particular edges red. The toggle button labels “ i j ” correspond to the edge between the vertices labeled with numbers i and j.
◼
Draw a dynamic, 2-colorable .
K
6
6/23/17 18:52:20 In[474]:=
DynamicModule[{ r = {} }, Row[ CheckboxBar[ Dynamic[r], Table[i allEdges6[[i]], {i, Range[15]}], Appearance "Vertical" {Automatic, Automatic} ], Dynamic[ CompleteGraph[ 6, BaseStyle Directive[ Blue, Thickness 0.03, Opacity[1] ], EdgeStyle Table[ edge Red, {edge, Part[ allEdges6, r ]}], VertexSize Medium, VertexStyle White, VertexLabels Placed[ Automatic, Center ], VertexLabelStyle Directive[ Bold, 20 ], ImageSize Medium ] ] ]]
Ramsey Numbers Are Hard to Find!
Ramsey Numbers Are Hard to Find!
Authorship information
Hikari Sorensen
2017/06/22
laurensorensen@college.harvard.edu