Minimal predictors in hat problems

Christopher S. Hardin, and Alan D. Taylor. "Minimal predictors in hat problems." Fundamenta Mathematicae 208.3 (2010): 273-285. <http://eudml.org/doc/282697>.

@article{ChristopherS2010,
abstract = {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 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 ω 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 ℵ₂ colors. For ℵ₀ 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.},
author = {Christopher S. Hardin, Alan D. Taylor},
journal = {Fundamenta Mathematicae},
keywords = {dependent choice; continuum hypothesis; Martin's axiom; combinatorial problem; cardinal invariants; meager sets of reals},
language = {eng},
number = {3},
pages = {273-285},
title = {Minimal predictors in hat problems},
url = {http://eudml.org/doc/282697},
volume = {208},
year = {2010},
}

TY - JOUR
AU - Christopher S. Hardin
AU - Alan D. Taylor
TI - Minimal predictors in hat problems
JO - Fundamenta Mathematicae
PY - 2010
VL - 208
IS - 3
SP - 273
EP - 285
AB - 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 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 ω 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 ℵ₂ colors. For ℵ₀ 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.
LA - eng
KW - dependent choice; continuum hypothesis; Martin's axiom; combinatorial problem; cardinal invariants; meager sets of reals
UR - http://eudml.org/doc/282697
ER -