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