Upper and lower Ramsey bounds in bounded arithmetic

DOI10.1016/j.apal.2005.01.001zbMath1073.03033OpenAlexW1974091179MaRDI QIDQ2488271

Kerry Ojakian

Publication date: 25 August 2005

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2005.01.001

zbMATH Keywords

Ramsey theoryprobabilistic methodbounded arithmeticweak pigeonhole principle

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Intersection theorems with geometric consequences
• Lifting independence results in bounded arithmetic
• A model-theoretic characterization of the weak pigeonhole principle
• The proof complexity of linear algebra
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• On the weak pigeonhole principle
• An upper bound for some ramsey numbers
• Provability of the pigeonhole principle and the existence of infinitely many primes
• A survey of bounds for classical Ramsey numbers
• Existence and feasibility in arithmetic
• A new proof of the weak pigeonhole principle

This page was built for publication: Upper and lower Ramsey bounds in bounded arithmetic