Hat problems and small cardinals

11 June 2014
Robert Leek
"Show that there is a function $f$ such that for any sequence $(x_1, x_2, \dots)$ we have $x_n = f(x_{n + 1}, x_{n + 2}, \dots)$ for all but finitely many $n$." Fred Galvin. Problem 5348. The American Mathematical Monthly, 72(10):p. 1135, 1965.\\ This quote is one of the earliest examples of an infinite hat problem, although it's not phrased this way. A hat problem is a non-empty set of colours together with a directed graph, where the nodes correspond to "agents" or "players" and the edges determine what the players "see". The goal is to find a collective strategy for the players which ensures that no matter what "hats" (= colours) are placed on their heads, they will ensure that a "sufficient" amount guess correctly.\\ In this talk I will discuss hat problems on countable sets and show that in a non-transitive setting, the relationship between existence of infinitely-correct strategies and Ramsey properties of the graph breakdown, in the particular case of the parity game. I will then introduce some small cardinals (uncountable cardinals no larger than continuum) that will be useful in analysing the parity game. Finally, I will present some new results on the sigma-ideal of meagre sets of reals that arise from this analysis.