Hat problem on a graph
Krzywkowski, Marcin Piotr
Thesis or dissertation
University of Exeter
The topic of this thesis is the hat problem. In this problem, a team of n players enters a room, and a blue or red hat is randomly placed on the head of each player. Every player can see the hats of all of the other players but not his own. Then each player must simultaneously guess the color of his own hat or pass. The team wins if at least one player guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of winning. This thesis is based on publications, which form the second chapter. In the first chapter we give an overview of the published results. In Section 1.1 we introduce to the hat problem and the hat problem on a graph, where vertices correspond to players, and a player can see the adjacent players. To the hat problem on a graph we devote the next few sections. First, we give some fundamental theorems about the problem. Then we solve the hat problem on trees, cycles, and unicyclic graphs. Next we consider the hat problem on graphs with a universal vertex. We also investigate the problem on graphs with a neighborhood-dominated vertex. In addition, we consider the hat problem on disconnected graphs. Next we investigate the problem on graphs such that the only known information are degrees of vertices. We also present Nordhaus-Gaddum type inequalities for the hat problem on a graph. In Section 1.6 we investigate the hat problem on directed graphs. The topic of Section 1.7 is the generalized hat problem with q >= 2 colors. A modified hat problem is considered in Section 1.8. In this problem there are n >= 3 players and two colors. The players do not have to guess their hat colors simultaneously and we modify the way of making a guess. We give an optimal strategy for this problem which guarantees the win. Applications of the hat problem and its connections to different areas of science are presented in Section 1.9. We also give there a comprehensive list of variations of the hat problem considered in the literature.
M. Krzywkowski, Hat problem on a graph, Mathematica Pannonica 21 (2010), 1–19.
M. Krzywkowski, Hat problem on the cycle C4, International Mathematical Forum 5 (2010), 205–212.
M. Krzywkowski, The hat problem on cycles on at least nine vertices, Ars Combinatoria 101 (2011), 3–13.
M. Krzywkowski, On the hat problem on a graph, Opuscula Mathematica 32 (2012), 285–296.
M. Krzywkowski, The hat problem on a union of disjoint graphs, Commentationes Mathematicae 51 (2011), 167–176.
M. Krzywkowski, Hat problem on odd cycles, Houston Journal of Mathematics 37 (2011), 1063–1069.
R. Hod and M. Krzywkowski, A construction for the hat problem on a directed graph, Electronic Journal of Combinatorics 19 (2012), #P30.
M. Krzywkowski, A more colorful hat problem, Annales Universitatis Paedagogicae Cracoviensis Studia Mathematica 10 (2011), 67–77.
M. Krzywkowski, A modified hat problem, Commentationes Mathematicae 50 (2010), 121–126.
M. Krzywkowski, On the hat problem, its variations, and their applications, Annales Universitatis Paedagogicae Cracoviensis Studia Mathematica 9 (2010), 55–67.
PhD by Publication in Mathematics