The computable strength of Milliken's Tree Theorem and applications

Abstract: Devlin's theorem and the Rado graph theorem are both variants of Ramsey's theorem, where a structure is added but more colors are allowed: Devlin's theorem (respectively the Rado graph theorem) states if S is ℚ (respectively G, the Rado graph), then for any size of tuple n, there exists a number of colors l such that for any coloring of [S]^n into finitely many colors, there exists a subcopy of S on which the coloring takes at most l colors. Moreover, given n, the optimal l is specified.

The key combinatorial theorem used in both the proof of Devlin's theorem and the Rado graph theorem is Milliken's tree theorem. Milliken's tree theorem is also a variant of Ramsey's theorem, but this time for trees and strong subtrees: it states that given a coloring of the strong subtrees of height n of a tree T, there exists a strong subtree of height ω of T on which the coloring is constant.

In this talk, we review the links between those theorems, and present the recent results on the computable strength of Milliken's tree theorem and its applications Devlin and the Rado graph theorem, obtained with Cholak, Dzhafarov, Monin and Patey.

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.