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(m, n) with m, n ≥ 3 are currently known.
Ramsey Property for r Colors
$ Def: A bipartite graph has it if for every r-coloring of the class A, there is a monochromatic vertex in B.
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)kn, 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