Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 471.05045
Autor: Erdös, Paul; Mills, George
Title: Some bounds for the Ramsey-Paris-Harrington numbers. (In English)
Source: J. Comb. Theory, Ser. A 30, 53-70 (1981).
Review: ``It has recently been discovered that a certain variant of Ramsey's theorem cannot be proved in first-order Peano arithmetic although it is in fact a true theorem. in this paper er give some bounds for the ``Ramsey-Paris-Harrington numbers'' associated with the variant of Ramsey's theorem, involving coloring of pairs. In the course of the investigation we also study certain weaker and stronger partition relations.'' Let k be a fixed positive integer. For n > k, let [k,n] denote {k,k+1,...,n}; for any set X let X2 denote the collection of two element subsets of X. A two coloring of [k,n]2, F: [k,n]2 ––> {1,2} is proper if there exists Y\subseteq[k,n] and a color 1 in {1,2} such that: (i) F({a,b}) = i for all {a,b} in Y2; (ii) |Y| \geq max{a| a in Y}\cup{3}. The integer n is proper if all two coloring of [k,n]2 are proper. R(k) is then the minimum proper n. The authors compute: R(1) = 6, R(2) = 8, R(3) = 13, and R(4) \leq 687. They prove: (i) There exists c > 0 such that (c\sqrt k/ log k)2^{k/2} < R(k) for all sufficiently large k; (ii) R(k) < 2k^{2k} for all k \geq 2.
Reviewer: J.E.Graver
Classif.: * 05C55 Generalized Ramsey theory
Keywords: Ramsey-Paris-Harrington numbers
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag