Ramsey-Paris-Harrington numbers for graphs (Q801937)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ramsey-Paris-Harrington numbers for graphs |
scientific article |
Statements
Ramsey-Paris-Harrington numbers for graphs (English)
0 references
1985
0 references
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}}. \]
0 references
Ramsey-Paris-Harrington numbers
0 references
complete subgraph
0 references
large independent set
0 references