Some bounds for the Ramsey-Paris-Harrington numbers (Q1157345)

``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,\dots,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\to\{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\min\{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\).