The computability of some problems in Borel combinatorics

Su Gao (Nankai U)

Jun 30. 2025, 11:30 — 12:15

Many problems of Borel combinatorics can be formulated as the existence of Borel equivariant maps from the Bernoulli shifts to some subshifts of finite type. We consider the case in which the acting group is a finitely generated free abelian group. We show that in the one-dimensional case the problem is computable, and in the two-dimensional case, the continuous problem is c.e.-complete.

Further Information
Venue:
ESI 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)