In this thesis, we study the hat guessing game on graphs. The players are represented by the vertices of a graph, and the edges determine which players can see each other. Before the game starts, the players agree on a deterministic strategy. Then an adversary, who knows the strategy, assigns each player a hat of one of the possible colors. Each player sees the colors of the hats worn by their neighbors, but not the color of their own hat. The players try to guess their own hat color. We measure the performance of strategies by the parameters $H_k$ and $HG$. $H_k$ gives the number of correct guesses the players can guarantee with $k$ colors, while $HG$ is the largest number of colors for which they can still guarantee at least one correct guess.
We show that for the complete graph $K_n$ we have $H_k(K_n)=\lfloor \frac{n}{k} \rfloor$ and $HG(K_n)=n$. For arbitrary undirected graphs with two colors, we present a theorem stating that $H_2(G)$ is equal to the size of a maximum matching in the graph. We then derive some basic lower and upper bounds for the parameter $HG$ and present known classifications for selected families of graphs. For trees, we have $HG(T)=2$. For cycles, $HG(C_n)=3$ if and only if $n=4$ or $3 \mid n$; otherwise, $HG(C_n)=2$. We also discuss cactus graphs and windmill graphs, where the parameter $HG$ can take larger values. Finally, we describe a few variants of the game and list some selected open problems.
|
