Computability theoretic aspects of big Ramsey degrees

Natasha Dobrinen (Notre Dame du Lac)

Jul 02. 2025, 09:30 — 10:15

We will give an introduction to big Ramsey degrees of homogeneous structures.  Then we will concentrate on computability theoretic aspects and discuss work done in the area by various logicians, including work by Cholak, Dobrinen, and McCoy on the $n$-clique free Henson graphs.  We prove that the statement ``Far anticliques with $k$ many nodes have the Ramsey Property" implies ACA over RCA$_0$.  We also prove that for each finite $n$-clique free graph G with $k\ge 2$ vertices, there is a computable 2-coloring of the copies of G in a computable copy of the Henson graph $H$ so that a) there is a monochromatic subcopy of $H$, and b) any such subcopy computes $\mathbf{0}^{(k-1)}$

 

Further Information
Venue:
ESI Schrödinger and Boltzmann Lecture Hall
Recordings:
Recording
Associated Event:
Reverse Mathematics (Thematic Programme)
Organizer(s):
Juan Aguilera (TU Vienna)
Linda Brown Westrick (Penn State U)
Noam Greenberg (Victoria U of Wellington)
Denis Hirschfeldt (U of Chicago)