Computability Seminar MSRI program on DDC-Milliken's tree theorem and computability theory

Organizer: V. Harizanov

For link contact harizanvgwu [dot] edu

Thursday, October 8, 12:00-1:00 on Zoom

Speaker:  Damir Dzhafarov, University of Connecticut

Title: Milliken's tree theorem and computability theory

Abstract: Milliken's tree theorem is a powerful combinatorial result that generalizes Ramsey's theorem and many other familiar partition results. I will present recent work on the effective and proof-theoretic strength of this theorem, which was originally motivated by a question of Dobrinen. The main result is a complete characterization of Milliken's tree theorem in terms of reverse mathematics and the usual computability-theoretic hierarchies, along with several applications to other combinatorial problems. Key to this is a new inductive proof of Milliken's tree theorem, employing an effective version of the Halpern-Lauchli theorem. This is joint work with Angles d'Auriac, Cholak, Monin, and Patey.