On uniform relationships between combinatorial problems

DOI10.1090/tran/6465WikidataQ59894937 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

05D15: Transversal (matching) theory

03B30: Foundations of classical theories (including reverse mathematics)

05D10: Ramsey theory

03D80: Applications of computability and recursion theory

03F35: Second- and higher-order arithmetic and fragments

05D40: Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)

03D32: Algorithmic randomness and dimension

Related Items

ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM, ON WEIHRAUCH REDUCIBILITY AND INTUITIONISTIC REVERSE MATHEMATICS, On the algebraic structure of Weihrauch degrees, 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, FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS, Thin set theorems and cone avoidance, Induction, Bounding, Weak Combinatorial Principles, and the Homogeneous Model Theorem, On the strength of marriage theorems and uniformity, The weakness of being cohesive, thin or free in reverse mathematics, On the uniform computational content of the Baire category theorem, A topological view on algebraic computation models, On the uniform computational content of computability theory, Embeddings between well-orderings: computability-theoretic reductions, \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models, Using Ramsey's theorem once, Pincherle's theorem in reverse mathematics and computability theory, Probabilistic computability and choice, Universality, optimality, and randomness deficiency, The uniform content of partial and linear orders, Coloring trees in reverse mathematics, A determinacy approach to Borel combinatorics, Ramsey’s theorem for singletons and strong computable reducibility, 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, On notions of computability-theoretic reduction between Π21 principles, Computable Reductions and Reverse Mathematics, Intuitionistic Provability versus Uniform Provability in $$\mathsf{RCA}$$

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