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

DOI10.1090/MEMO/1457arXiv2007.09739MaRDI QIDQ6201447FDOQ6201447

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)

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.

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)

Cites Work

• Algorithmic randomness and complexity.
• Subsystems of second order arithmetic
• On sets of integers containing k elements in arithmetic progression
• A dual form of Ramsey's theorem
• ∏ 0 1 Classes and Degrees of Theories
• On the strength of Ramsey's theorem for pairs
• Slicing the Truth
• Introduction to Ramsey space
• Title not available (Why is that?)
• Ramsey's theorem and recursion theory
• Splitting an α-Recursively Enumerable Set
• Title not available (Why is that?)
• Title not available (Why is that?)
• Partitions of Products
• A Partition Theorem
• On the strength of Ramsey's theorem
• Degrees of members of \(\Pi_ 1^ 0\) classes
• A Ramsey theorem for trees
• Turing Computability
• The dichotomy between structure and randomness, arithmetic progressions, and the primes
• A Partition Theorem for the Infinite Subtrees of a Tree
• Some logically weak Ramseyan theorems
• On notions of computability-theoretic reduction between Π21 principles
• Ramsey's theorem and cone avoidance
• Cohesive avoidance and strong reductions
• Canonical partitions of universal structures
• Coloring subgraphs of the Rado graph
• Counting canonical partitions in the random graph
• Reverse mathematics, computability, and partitions of trees
• Coloring trees in reverse mathematics
• THE STRENGTH OF THE TREE THEOREM FOR PAIRS IN REVERSE MATHEMATICS
• Rainbow Ramsey simple structures
• Coloring the rationals in reverse mathematics
• Big Ramsey degrees and topological dynamics
• Weihrauch Complexity in Computable Analysis
• Thin set theorems and cone avoidance
• SEARCHING FOR AN ANALOGUE OF ATR₀ IN THE WEIHRAUCH LATTICE
• The strength of Ramsey’s theorem for pairs over trees: I. Weak König’s Lemma
• On the Independence of the Kinna Wagner Principle

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)