Slavic Techniques for Hat Guessing Algorithms

Abstract

We study a deterministic hat game. Sages stand on the vertices of a “visibility (di)graph” D. A crafty Adversary assigns to each sage k a hat of color c(k) ∈ [h(k)], i.e. from among h(k) predetermined colors. Then each sage, based on the hat colors of her out-neighbors, guesses g(k) colors for her own hat. They can strategize beforehand but not communicate during. They win if they can guarantee that at least one correct guess occurs. For which games (D,g,h) can they guarantee victory? Parameters related to such questions have been well-studied, especially the “hat guessing number” μ(D). We open with a casual, riddle-based invitation to the topic and its motivation. Rigor enters with a game taxonomy and a survey of all previous work. After introduction and definitions, we prove warm-up propositions, including fundamental lemmata and the solution to most directed- cycle games. In the remaining chapters, we formalize, generalize, and utilize techniques from the literature. We take a “Hats as Hints” perspective and use the “admissible paths” of [Szc17] to prove the conjecture of [KLR21b] and go farther to settle all single-guess games on cycles. We generalize several “constructors,” central theorems that build games while preserving (un)winnableness. Basic ones simplify [KL19] and algorithmically solve single-guess games on trees (two ways). A “combinatorial prism” approach gives rules for strategy design, a characterization of deletable vertices, and packing/covering conditions for games on Kn,m. Then we apply the probabilistic method, defining “Ratio games” to crystallize work on dependency (di)graphs, graph polynomials, and unwinnable games. We show that the visibility digraph is dual to a dependency digraph and that Shearer’s Lemma probably can’t extend to digraphs. The final chapter collects open problems, including all that have been explicitly stated in the literature. Others are first posed here. It includes partial or minor results, such as curiosities about →− C k and some computational complexity facts.