Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension
 Author
 Andreas Weiermann (UGent) and Wim Van Hoof (UGent)
 Organization
 Project
 phase transitions in logic and combinatorics
 Abstract
 This article is concerned with investigations on a phase transition which is related to the (finite) Ramsey theorem and the ParisHarrington theorem. For a given numbertheoretic function g, let Rc(d)(g)(k) be the least natural number R such that for all colourings P of the delement 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 delement 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 Rc(d)(g)(k) is equal to the usual Ramsey number Rc(d)(max{e, k}); and if g is the identity function, then Rc(d)(g)(k) is the corresponding ParisHarrington number, which typically is much larger than Rc(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 Rm(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)(d1)times (where epsilon > 0 is fixed) but not for the function g(i) = 1/log*(i) . log(. . . (log( i). . .).(sic)(d1)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), 553561) of the first author, which were obtained by employing constructive ordinal partitions.
 Keywords
 Ramsey theorem, rapidly growing Ramsey functions, Peano arithmetic, fast growing hierarchies
Downloads

(...).pdf
 full text
 
 UGent only
 
 
 237.62 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU1972866
 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.
@article{1972866, abstract = {This article is concerned with investigations on a phase transition which is related to the (finite) Ramsey theorem and the ParisHarrington theorem. For a given numbertheoretic function g, let Rc(d)(g)(k) be the least natural number R such that for all colourings P of the delement 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 delement 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 Rc(d)(g)(k) is equal to the usual Ramsey number Rc(d)(max\{e, k\}); and if g is the identity function, then Rc(d)(g)(k) is the corresponding ParisHarrington number, which typically is much larger than Rc(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 Rm(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)(d1)times (where epsilon {\textrangle} 0 is fixed) but not for the function g(i) = 1/log*(i) . log(. . . (log( i). . .).(sic)(d1)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), 553561) of the first author, which were obtained by employing constructive ordinal partitions.}, author = {Weiermann, Andreas and Van Hoof, Wim}, issn = {00029939}, journal = {PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY}, keyword = {Ramsey theorem,rapidly growing Ramsey functions,Peano arithmetic,fast growing hierarchies}, language = {eng}, number = {8}, pages = {29132927}, title = {Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension}, url = {http://dx.doi.org/10.1090/S000299392011111213}, volume = {140}, year = {2012}, }
 Altmetric
 View in Altmetric
 Web of Science
 Times cited: