Computability Seminar MSRI program on DDC-The big Ramsey degree of the rationals and the Rado graph and computability theory

Organizer: V. Harizanov

For link contact [email protected]

Friday, December 11, 12:00-1:00 ET on Zoom

Speaker: Peter Cholak, University of Notre Dame

Title: The big Ramsey degree of the rationals and the Rado graph and computability theory

Abstract: Milliken’s tree theorem is used to prove that the rationals and the Rado graph have big Ramsey degree.  It turns out that there is the complicated dichotomy between coding the halting problem or not based on the size of instance.  We will explore what this all means. 

This is joint work with Angles d’Auriac, Dzhafarov, Monin, and Patey.