##
**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 X^{2} 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 Y^{2}; (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) < 2^{k^{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