Some bounds for the Ramsey-Paris-Harrington numbers
type: Item
instance of: scholarly article
title: Some bounds for the Ramsey-Paris-Harrington numbers
zbMATH Open document ID: 0471.05045
DOI: 10.1016/0097-3165(81)90040-6
author: George Mills
author: P. Erdős
published in: Journal of Combinatorial Theory. Series A
publication date: 1981-01-01T00:00:00Z
review text: ``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\).
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 3737718
zbMATH Keywords: Ramsey-Paris-Harrington numbers
reviewed by: Jack E. Graver
MaRDI profile type: Publication
full work available at URL: 0097-3165(81)90040-6
OpenAlex ID: W2141157177
cites work: On Harrington's partition relation
cites work: Graph Theory and Probability. II
cites work: Some graph theoretic results associated with Ramsey's theorem
cites work: Q4138726
cites work: Some independence results for Peano arithmetic
cites work: Rapidly growing Ramsey functions
description: scientific article; zbMATH DE number 3737718