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(m, n) with m, n ≥ 3 are currently known.
* Ramsey number for two graphs: For two graphs G1 and G2, the Ramsey number R(G1, G2) is the smallest integer p such that for any graph G on p vertices either G contains G1 or G* contains G2, where G* denotes the complement of G.
@ General references: Graham et al 90; Graham & Spencer SA(90)jul.
@ Quantum algorithms: Gaitan & Clark PRL(12)-a1103, Bian et al PRL(13)-a1201 [for two-color Ramsey numbers]; Wang PRA(16)-a1510; Ranjbar et al QIP(16) [using adiabatic quantum optimization].
@ Related topics: Huang et al EJC(06) [for two groups, bounds]; Clark & Gaitan AADM-a1303 [distribution of Ramsey numbers]; > s.a. Polytopes.
> Online resources: see MathWorld page; Wikipedia page.

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