Ramsey's theorem is a generalization of Dilworth's lemma which states for each pair of positive integers 
and 
there exists an integer 
(known as the Ramsey number) such that any graph with
nodes contains a clique
with at least 
nodes or an independent set with at least 
nodes.
Another statement of the theorem is that for integers 
, there exists a least positive integer 
such that no matter how the complete
graph 
is two-colored, it will contain a green subgraph 
or a red subgraph 
.
A third statement of the theorem states that for all 
, there exists an 
such that any complete
digraph on 
graph vertices contains a complete vertex-transitive subgraph
of 
graph vertices.
For example, 
and 
,
but 
are only known to lie in the ranges 
and 
.
It is true that
 |
if 
.
