Minimal predictors in hat problems
Tom 208 / 2010
Streszczenie
We consider a combinatorial problem related to guessing the values of a function at various points based on its values at certain other points, often presented by way of a hat-problem metaphor: there are a number of players who will have colored hats placed on their heads, and they wish to guess the colors of their own hats. A {\it visibility relation} specifies who can see which hats. This paper focuses on the existence of minimal predictors: strategies guaranteeing at least one player guesses correctly, regardless of how the hats are colored. We first present some general results, in particular showing that transitive visibility relations admit a minimal predictor exactly when they contain an infinite chain, regardless of the number of colors. In the more interesting nontransitive case, we focus on a particular nontransitive relation on $\omega$ that is elementary, yet reveals unexpected phenomena not seen in the transitive case. For this relation, minimal predictors always exist for two colors but never for $\aleph_2$ colors. For $\aleph_0$ colors, the existence of minimal predictors is independent of ZFC plus a fixed value of the continuum, and turns out to be closely related to certain cardinal invariants involving meager sets of reals.
