Ramsey number

(redirected from Ramsey's theorem)
Also found in: Wikipedia.

Ramsey number

[′ram·zē ‚nəm·bər]
(mathematics)
For any two positive integers, p and q, the smallest integer, R (p,q), that has the (p,q)-Ramsey property.
References in periodicals archive ?
Ramsey's theorem says that for every n, every sufficiently large graph has either a clique or an independent set of size n.
Ramsey's Theorem for graphs and hypergraphs only guarantees the existence of rather small cliques or independent sets.
It discusses Ramsey's theorem, van der Waerden's theorem, Szemeredi's theorem, graphic and Euclidean Ramsey theory, a general Ramsey product theorem, and the theorems of Schur, Folkman, Hindman, and Rado.
His proof, given for relational structures of finite signature, was based on Ramsey's theorem [45] and the compactness theorem of first order logic.
From Ramsey's theorem, Fraisse deduced the following lemma.
8 is built on the integrity of the age algebra of infinite multichainable relational structures and Ramsey's theorem.
In the 1930s, Hungarian mathematician Paul Erdos, who pioneered many of the key ideas extending Ramsey's theorem, started thinking about the question of exactly how large a set must be to guarantee the presence of a certain subset.
Ramsey's Theorem tells us that every graph on n vertices has a clique or independent set of size at least a constant times log n.
Subjects covered include the structure theory of various notions of degrees of unsolvability, algorithmic randomness, reverse mathematics, forcing, large cardinals and inner model theory, with papers on such topics as the strength of some combinatorial principles related to Ramsey's theorem for pairs, absoluteness for universally Baire sets and the uncountable, modaic definability of ordinals, eliminating concepts, rigidity and bi-interpretability in hyperdegrees, fundamental issues of degrees of unsolvability, a "tt" version of the Posner-Robinson theorem, and prompt simplicity, array computability and cupping.
Some graph theoretic results associated with Ramsey's theorem.