On uniform relationships between combinatorial problems

DOI10.1090/TRAN/6465OpenAlexW2963693343WikidataQ59894937 ScholiaQ59894937MaRDI QIDQ2796522

Jeffry L. Hirst, Damir D. Dzhafarov, François G. Dorais, Joseph R. Mileti, Paul Shafer

Publication date: 29 March 2016

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1212.0157

Mathematics Subject Classification ID

Transversal (matching) theory (05D15) Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Algorithmic randomness and dimension (03D32)

Related Items (40)

An inside/outside Ramsey theorem and recursion theory ⋮ Reverse mathematics and Weihrauch analysis motivated by finite complexity theory ⋮ On the uniform computational content of the Baire category theorem ⋮ Reduction games, provability and compactness ⋮ On notions of computability-theoretic reduction between Π21 principles ⋮ Computable Reductions and Reverse Mathematics ⋮ RAMSEY-LIKE THEOREMS AND MODULI OF COMPUTATION ⋮ Intuitionistic Provability versus Uniform Provability in $$\mathsf{RCA}$$ ⋮ The uniform content of partial and linear orders ⋮ Coloring trees in reverse mathematics ⋮ A topological view on algebraic computation models ⋮ Algebraic properties of the first-order part of a problem ⋮ Ramsey’s theorem for singletons and strong computable reducibility ⋮ On the uniform computational content of computability theory ⋮ ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM ⋮ ON WEIHRAUCH REDUCIBILITY AND INTUITIONISTIC REVERSE MATHEMATICS ⋮ Induction, Bounding, Weak Combinatorial Principles, and the Homogeneous Model Theorem ⋮ Reverse Mathematics of Matroids ⋮ The Vitali Covering Theorem in the Weihrauch Lattice ⋮ Many-one reductions and the category of multivalued functions ⋮ Some Questions in Computable Mathematics ⋮ The weakness of being cohesive, thin or free in reverse mathematics ⋮ Embeddings between well-orderings: computability-theoretic reductions ⋮ FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS ⋮ On the algebraic structure of Weihrauch degrees ⋮ On the strength of marriage theorems and uniformity ⋮ Using Ramsey's theorem once ⋮ A determinacy approach to Borel combinatorics ⋮ \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models ⋮ Thin set theorems and cone avoidance ⋮ Pincherle's theorem in reverse mathematics and computability theory ⋮ Highness properties close to PA completeness ⋮ RAMSEY’S THEOREM FOR PAIRS ANDKCOLORS AS A SUB-CLASSICAL PRINCIPLE OF ARITHMETIC ⋮ Weihrauch and constructive reducibility between existence statements ⋮ COH, SRT 2 2 , and multiple functionals ⋮ Probabilistic computability and choice ⋮ Parallelizations in Weihrauch reducibility and constructive reverse mathematics ⋮ Weihrauch Complexity in Computable Analysis ⋮ Universality, optimality, and randomness deficiency ⋮ Restrictions of Hindman's theorem: an overview

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• Closed choice and a uniform low basis theorem
• Algorithmic randomness, reverse mathematics, and the dominated convergence theorem
• Countable algebra and set existence axioms
• Some logically weak Ramseyan theorems
• Measure theory and weak König's lemma
• On the strength of Ramsey's theorem for pairs
• Rainbow Ramsey Theorem for Triples is Strictly Weaker than the Arithmetical Comprehension Axiom
• Term extraction and Ramsey's theorem for pairs
• On the (semi)lattices induced by continuous reducibilities
• Weihrauch degrees, omniscience principles and weak computability
• Algorithmic Randomness and Complexity
• On notions of computability-theoretic reduction between Π21 principles
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• Slicing the Truth
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Ramsey's theorem and cone avoidance
• The strength of the rainbow Ramsey Theorem
• A proof of Beigel's cardinality conjecture
• Random reals, the rainbow Ramsey theorem, and arithmetic conservation
• Comparing DNR and WWKL
• SEPARATING PRINCIPLES BELOW RAMSEY'S THEOREM FOR PAIRS
• Representations of Reals in Reverse Mathematics
• Cohesive avoidance and strong reductions
• ∏ 0 1 Classes and Degrees of Theories
• Ramsey's theorem and recursion theory

This page was built for publication: On uniform relationships between combinatorial problems