Hat Guessing
L. van der Kuil (TU Delft - Electrical Engineering, Mathematics and Computer Science)
A. Bishnoi – Mentor (TU Delft - Discrete Mathematics and Optimization)
Dion Gijswijt – Graduation committee member (TU Delft - Discrete Mathematics and Optimization)
R.J. Fokkink – Graduation committee member (TU Delft - Applied Probability)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This thesis is about the following hat guessing game first described by Winkler. Consider a group of n players situated at the vertices of a graph G. An adversary gives each player a hat coloured one of q possible colours. The players are unable to see the colour of their own hat, but each player can see the hat colour of their neighbours in G. The players are asked to simultaneously make a guess on the colour of their own hat, according to a predetermined guessing strategy based solely on the hat colours each player can see. The players win if at least one of them correctly guesses their hat colour, otherwise the adversary wins. Is it possible for the players to devise a strategy which guarantees they win regardless of how the adversary places the hats? Clearly, if the players have a winning strategy on the graph G for q colours, then the same strategy must also be winning for any number of colours less than q. This motivates us to define the hat guessing number HG(G) of G, a parameter first introduced by Farnik.
Definition: Let HG(G) be the maximum q such that the players have a winning strategy when playing the hat guessing game on the graph G with q colours.
Bosek et al. showed an upper bound on the hat guessing number using a partition into independent sets. We show that the same bound holds when V1, ..., Vl partition the vertices into sets that induce directed acyclic graphs. This implies that for any arc a of the complete graph Kn we have that HG(Kn-a) = n-1, whereas HG(Kn) = n. Furthermore, we give a family of graphs for which choosing a partition into the minimum number of independent sets may be arbitrarily worse than choosing a different partition into independent sets, when applying the bound.
Szczechla have shown the hat guessing number for cycles. They formulate strategies to show that HG(C4) ≥ 3 and HG(C3n) ≥ 3 in a complex coordinate system. We reformulate those same strategies and show that they are winning without using this coordinate system.
The winning strategy for C4 can be generalised to obtain the following result. For an odd prime power q, let M a maximum matching in the complete graph Kq+1. Then HG(Kq+1-M) = q.
On a more general and technical note, we define a notion of equivalence of strategies to try revealing some of the inherent symmetries of the problem. For example, reassigning individual strategies according to an automorphism of the graph does not change whether the collective strategy is winning. We also obtain a notion of uniqueness of a winning strategy, which we conjecture to be a strong, but rare, property.