Ghent University Academic Bibliography

Advanced

Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension

Andreas Weiermann UGent and Wim Van Hoof UGent (2012) PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY. 140(8). p.2913-2927
abstract
This article is concerned with investigations on a phase transition which is related to the (finite) Ramsey theorem and the Paris-Harrington theorem. For a given number-theoretic function g, let R-c(d)(g)(k) be the least natural number R such that for all colourings P of the d-element subsets of {0, . . . ,R - 1} with at most c colours there exists a subset H of {0, . . . , R - 1} such that P has constant value on all d-element subsets of H and such that the cardinality of H is not smaller than max{k, g(min(H))}. If g is a constant function with value e, then R-c(d)(g)(k) is equal to the usual Ramsey number R-c(d)(max{e, k}); and if g is the identity function, then R-c(d)(g)(k) is the corresponding Paris-Harrington number, which typically is much larger than R-c(d)(k). In this article we give for all d >= 2 a sharp classification of the functions g for which the function m bar right arrow R-m(d)(g)(m) grows so quickly that it is no longer provably total in the subsystem of Peano arithmetic, where the induction scheme is restricted to formulas with at most (d - 1)-quantifiers. Such a quick growth will in particular happen for any function g growing at least as fast as i bar right arrow epsilon . log(. . . (log(i). . .)(sic)(d-1)-times (where epsilon > 0 is fixed) but not for the function g(i) = 1/log*(i) . log(. . . (log( i). . .).(sic)(d-1)-times (Here log* denotes the functional inverse of the tower function.) To obtain such results arid even sharper bounds we employ certain suitable transfinite iterations of nonconstructive lower bound functions for Ramsey numbers. Thereby we improve certain results from the article A classification of rapidly growing Ramsey numbers (PAMS 132 (2004), 553-561) of the first author, which were obtained by employing constructive ordinal partitions.
Please use this url to cite or link to this publication:
author
organization
year
type
journalArticle (original)
publication status
published
subject
keyword
Ramsey theorem, rapidly growing Ramsey functions, Peano arithmetic, fast growing hierarchies
journal title
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY
Proc. Amer. Math. Soc.
volume
140
issue
8
pages
2913 - 2927
Web of Science type
Article
Web of Science id
000306387400033
JCR category
MATHEMATICS
JCR impact factor
0.609 (2012)
JCR rank
128/296 (2012)
JCR quartile
2 (2012)
ISSN
0002-9939
DOI
10.1090/S0002-9939-2011-11121-3
project
phase transitions in logic and combinatorics
language
English
UGent publication?
yes
classification
A1
copyright statement
I have transferred the copyright for this publication to the publisher
id
1972866
handle
http://hdl.handle.net/1854/LU-1972866
date created
2011-12-22 11:15:09
date last changed
2016-12-19 15:45:31
@article{1972866,
  abstract     = {This article is concerned with investigations on a phase transition which is related to the (finite) Ramsey theorem and the Paris-Harrington theorem. For a given number-theoretic function g, let R-c(d)(g)(k) be the least natural number R such that for all colourings P of the d-element subsets of \{0, . . . ,R - 1\} with at most c colours there exists a subset H of \{0, . . . , R - 1\} such that P has constant value on all d-element subsets of H and such that the cardinality of H is not smaller than max\{k, g(min(H))\}. If g is a constant function with value e, then R-c(d)(g)(k) is equal to the usual Ramsey number R-c(d)(max\{e, k\}); and if g is the identity function, then R-c(d)(g)(k) is the corresponding Paris-Harrington number, which typically is much larger than R-c(d)(k). In this article we give for all d {\textrangle}= 2 a sharp classification of the functions g for which the function m bar right arrow R-m(d)(g)(m) grows so quickly that it is no longer provably total in the subsystem of Peano arithmetic, where the induction scheme is restricted to formulas with at most (d - 1)-quantifiers. Such a quick growth will in particular happen for any function g growing at least as fast as i bar right arrow epsilon . log(. . . (log(i). . .)(sic)(d-1)-times (where epsilon {\textrangle} 0 is fixed) but not for the function g(i) = 1/log*(i) . log(. . . (log( i). . .).(sic)(d-1)-times (Here log* denotes the functional inverse of the tower function.) To obtain such results arid even sharper bounds we employ certain suitable transfinite iterations of nonconstructive lower bound functions for Ramsey numbers. Thereby we improve certain results from the article A classification of rapidly growing Ramsey numbers (PAMS 132 (2004), 553-561) of the first author, which were obtained by employing constructive ordinal partitions.},
  author       = {Weiermann, Andreas and Van Hoof, Wim},
  issn         = {0002-9939},
  journal      = {PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY},
  keyword      = {Ramsey theorem,rapidly growing Ramsey functions,Peano arithmetic,fast growing hierarchies},
  language     = {eng},
  number       = {8},
  pages        = {2913--2927},
  title        = {Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension},
  url          = {http://dx.doi.org/10.1090/S0002-9939-2011-11121-3},
  volume       = {140},
  year         = {2012},
}

Chicago
Weiermann, Andreas, and Wim Van Hoof. 2012. “Sharp Phase Transition Thresholds for the Paris Harrington Ramsey Numbers for a Fixed Dimension.” Proceedings of the American Mathematical Society 140 (8): 2913–2927.
APA
Weiermann, A., & Van Hoof, W. (2012). Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 140(8), 2913–2927.
Vancouver
1.
Weiermann A, Van Hoof W. Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY. 2012;140(8):2913–27.
MLA
Weiermann, Andreas, and Wim Van Hoof. “Sharp Phase Transition Thresholds for the Paris Harrington Ramsey Numbers for a Fixed Dimension.” PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY 140.8 (2012): 2913–2927. Print.