Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective

DOI10.1090/MEMO/1457MaRDI QIDQ6201447FDO

Authors Paul-Elliot Anglès d'Auriac, Peter A. Cholak, Damir D. Dzhafarov, Benoit Monin, Ludovic Patey

Publication date 20 February 2024

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

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

zbMATH Keywords

partition theoryreverse mathematicsRamsey's theoremstructural Ramsey theorycomputable combinatoricsMilliken's tree theorem

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Generalized Ramsey theory (05C55) Other combinatorial set theory (03E05) Extremal set theory (05D05) Ramsey theory (05D10) Applications of computability and recursion theory (03D80) Applications of set theory (03E75)

Abstract: Milliken's tree theorem is a deep result in combinatorics that generalizes a vast number of other results in the subject, most notably Ramsey's theorem and its many variants and consequences. Motivated by a question of Dobrinen, we initiate the study of Milliken's tree theorem from the point of view of computability theory. Our advance here stems from a careful analysis of the Halpern-La"{u}chli theorem which shows that it can be carried out effectively (i.e., that it is computably true). We use this as the basis of a new inductive proof of Milliken's tree theorem that permits us to gauge its effectivity in turn. The principal outcome of this is a comprehensive classification of the computable content of Milliken's tree theorem. We apply our analysis also to several well-known applications of Milliken's tree theorem, namely Devlin's theorem, a partition theorem for Rado graphs, and a generalized version of the so-called tree theorem of Chubb, Hirst, and McNicholl. These are all certain kinds of extensions of Ramsey's theorem for different structures, namely the rational numbers, the Rado graph, and perfect binary trees, respectively. We obtain a number of new results about how these principles relate to Milliken's tree theorem and to each other, in terms of both their computability-theoretic and combinatorial aspects. We identify again the familiar dichotomy between coding the halting problem or not based on the size of instance, but this is more subtle here owing to the more complicated underlying structures, particularly in the case of Devlin's theorem. We also establish new structural Ramsey-theoretic properties of the Rado graph theorem and the generalized Chubb-Hirst-McNicholl tree theorem using Zucker's notion of big Ramsey structure.

Recommendations

• Reverse mathematics, computability, and partitions of trees
• Ramsey's theorem for trees: the polarized tree theorem and notions of stability
• scientific article; zbMATH DE number 1303203
• On the uniform computational content of Ramsey's theorem
• Partition Theorems and Computability Theory

Cites work

• scientific article; zbMATH DE number 5830771 (Why is no real title available?)
• scientific article; zbMATH DE number 3523693 (Why is no real title available?)
• scientific article; zbMATH DE number 3446873 (Why is no real title available?)
• A Partition Theorem
• A Partition Theorem for the Infinite Subtrees of a Tree
• A Ramsey theorem for trees
• A dual form of Ramsey's theorem
• Algorithmic randomness and complexity.
• Big Ramsey degrees and topological dynamics
• Canonical partitions of universal structures
• Cohesive avoidance and strong reductions
• Coloring subgraphs of the Rado graph
• Coloring the rationals in reverse mathematics
• Coloring trees in reverse mathematics
• Counting canonical partitions in the random graph
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Introduction to Ramsey space
• On notions of computability-theoretic reduction between Π21 principles
• On sets of integers containing k elements in arithmetic progression
• On the Independence of the Kinna Wagner Principle
• On the strength of Ramsey's theorem
• On the strength of Ramsey's theorem for pairs
• Partitions of Products
• Rainbow Ramsey simple structures
• Ramsey's theorem and cone avoidance
• Ramsey's theorem and recursion theory
• Reverse mathematics, computability, and partitions of trees
• Searching for an analogue of \(\text{ATR}_0\) in the Weihrauch lattice
• Slicing the truth. On the computable and reverse mathematics of combinatorial principles
• Some logically weak Ramseyan theorems
• Splitting an α-Recursively Enumerable Set
• Subsystems of second order arithmetic
• The dichotomy between structure and randomness, arithmetic progressions, and the primes
• The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma
• The strength of the tree theorem for pairs in reverse mathematics
• Thin set theorems and cone avoidance
• Turing computability. Theory and applications
• Weihrauch Complexity in Computable Analysis
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(1)

• The Ginsburg-Sands theorem and computability theory

This page was built for publication: Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201447)