Ramsey Theory |

**In General** > s.a. Baire Category
Theorem; Coloring Problem.

* __Idea__: A branch of
combinatorics whose central theme is the emergence of order in large disordered
structures, with Ramsey numbers marking the threshold at which this order first
appears; Typically it studies the conditions, such as minimum size, under which
a certain structure is guaranteed to have a particular property; Many results
are centered around Ramsey's theorem, and, abstractly, attempt to decide when
a bipartite graph has the Ramsey property.

* __Ramsey number__: The minimum
number of vertices a complete graph must have so that every possible coloring of
its edges will contain at least one monochromatic complete subgraph of specified
order; These numbers are extremely difficult to compute because adding additional
vertices to a graph causes an explosion in the number of graph colorings that
must be checked.

* __Results__: 1990, The only
known Ramsey numbers are

R(3, 3) = 6, R(3, 4) = 9, R(3, 5) = 14, R(3, 6) = 18, R(3, 7) = 23, R(3, 8) = 29, R(3, 9) = 36, R(4, 4) = 18 ;

2012, only nine of the two-color Ramsey numbers R(*

@

@

@

>

**Ramsey Property for r Colors**

$

**Ramsey's Theorem** > s.a. partition.

* __Idea__: A special case
of partition relation, for infinite cardinality; It can be generalized to finite sets.

$ __Def__: The combinatorial set
theoretical theorem which states that ℵ_{0} →
(ℵ_{0})^{k}_{n},
for all finite *n* and *k*.

@ __References__: Ramsey PLMS(30);
Erdős & Rado BAMS(56) [generalization];
Xu JCTA(11) [stochastic extension].

main page
– abbreviations
– journals – comments
– other sites – acknowledgements

send feedback and suggestions to bombelli at olemiss.edu – modified 16 jun 2016