Upper and lower Ramsey bounds in bounded arithmetic

Annals of Pure and Applied Logic 135 (1-3):135-150 (2005)
  Copy   BIBTEX

Abstract

Pudlák shows that bounded arithmetic proves an upper bound on the Ramsey number Rr . We will strengthen this result by improving the bound. We also investigate lower bounds, obtaining a non-constructive lower bound for the special case of 2 colors , by formalizing a use of the probabilistic method. A constructive lower bound is worked out for the case when the monochromatic set size is fixed to 3 . The constructive lower bound is used to prove two “reversals”. To explain this idea we note that the Ramsey upper bound proof for k=3 uses the weak pigeonhole principle in a significant way. The Ramsey upper bound proof for the case in which the upper bound is not explicitly mentioned, uses the totality of the exponentiation function in a significant way. It turns out that the Ramsey upper bounds actually imply the respective principles used to prove them, indicating that these principles were in some sense necessary

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Infinite substructure lattices of models of Peano Arithmetic.James H. Schmerl - 2010 - Journal of Symbolic Logic 75 (4):1366-1382.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
The Complexity of Bounded Quantifiers in Some Ordered Abelian Groups.Philip Scowcroft - 2007 - Notre Dame Journal of Formal Logic 48 (4):521-550.
A note on sharply bounded arithmetic.Jan Johannsen - 1994 - Archive for Mathematical Logic 33 (2):159-165.
Strengths and Weaknesses of LH Arithmetic.Chris Pollett & Randall Pruim - 2002 - Mathematical Logic Quarterly 48 (2):221-243.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Automatic structures of bounded degree revisited.Dietrich Kuske & Markus Lohrey - 2011 - Journal of Symbolic Logic 76 (4):1352-1380.

Analytics

Added to PP
2014-01-16

Downloads
23 (#584,438)

6 months
1 (#1,040,386)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Existence and feasibility in arithmetic.Rohit Parikh - 1971 - Journal of Symbolic Logic 36 (3):494-508.
Dual weak pigeonhole principle, Boolean complexity, and derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
A model-theoretic characterization of the weak pigeonhole principle.Neil Thapen - 2002 - Annals of Pure and Applied Logic 118 (1-2):175-195.
Lifting independence results in bounded arithmetic.Mario Chiari & Jan Krajíček - 1999 - Archive for Mathematical Logic 38 (2):123-138.

View all 6 references / Add more references