Ramsey-Paris-Harrington numbers for graphs (Q801937)

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}}. \]