Coding in the universal $n$-clique free graph, $H_{n+1}$: Part I.

Peter Cholak (Notre Dame du Lac)

Aug 04. 2025, 10:00 — 11:00

Color a finite graph $G$ in $H_{n+1}$ with finitely many colors.  By a result of Dobrinen there is another copy $H_{n+1}$ inside our original copy of $H_{n+1}$ where $G$ takes on some minimal number of colors (the number is determined by $G$ and $n$).  Call this the minimal heterogeneous copy. The question we will address in this talk is how difficult it is to compute this copy.  Mostly we will provide lower bounds but we will include one upper bound and some appealing questions.   These results depend on understanding  the structure of copies of  $H_ {n+1}$  and using the work of Jockusch [72] on lower bounds for homogenous sets.  This work is joint with Dobrinen and McCoy. 

 

Further Information
Venue:
ESI Schrödinger and Boltzmann Lecture Hall
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)