Ramsey-Paris-Harrington numbers for graphs
type: Item
instance of: scholarly article
title: Ramsey-Paris-Harrington numbers for graphs
zbMATH Open document ID: 0553.05054
DOI: 10.1016/0097-3165(85)90018-4
author: George Mills
published in: Journal of Combinatorial Theory. Series A
publication date: 1985-01-01T00:00:00Z
review text: Let [k,n] denote the set \(\{k,k+1,...,n\}\); a subset H of [k,n] is said to be relatively large if \(| H| \geq \min H\) and \(| H| \geq 3.\) The Ramsey-Paris-Harrington numbers are then defined as follows: R(k;m) is the smallest integer n so that any graph on the vertex set [k,n] contains either a complete m-set (a complete subgraph on m vertices) or a relatively large independent set; R(k) is the smallest integer n so that any graph on the vertex set [k,n] contains either a relatively large complete set or a relatively large independent set. Several results concerning these numbers are proved including: Theorem 4. There exist constants \(\alpha,\beta,N>0\) such that for all \(m\geq 3\) and \(k\geq N\) \[ (i)\quad k^{2^{\alpha m}}<R(k;m)<k^{2^{\beta m}}\quad (ii)\quad k^{2^{\alpha k}}<R(k)<k^{2^{2\beta k}}. \]
reviewed by: Jack E. Graver
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 3880756
zbMATH Keywords: Ramsey-Paris-Harrington numbers
zbMATH Keywords: complete subgraph
zbMATH Keywords: large independent set
MaRDI profile type: Publication
full work available at URL: 0097-3165(85)90018-4
OpenAlex ID: W2078051625
cites work: Some bounds for the Ramsey-Paris-Harrington numbers
cites work: Some graph theoretic results associated with Ramsey's theorem
description: scientific article; zbMATH DE number 3880756