Minimal predictors in hat problems

• Autorzy: Christopher S. Hardin , Alan D. Taylor
• Języki publikacji: EN

Abstrakty

EN

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.

Kategorie tematyczne

• 03E17: Cardinal characteristics of the continuum
• 03E05: Other combinatorial set theory

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 2010
• Tom: 208
• Numer: 3
• Strony: 273-285

Daty

wydano

2010

Twórcy

autor

Christopher S. Hardin

• Department of Mathematics, Union College, Schenectady, NY 12308, U.S.A.

autor

Alan D. Taylor

• Department of Mathematics, Union College, Schenectady, NY 12308, U.S.A.

Identyfikatory

DOI

10.4064/fm208-3-4