Department of Mathematical Sciences
Discrete Math Seminar
Tuesday, August 26th, 2025
Olin Hall 126, 4:00PM- 4:50 PM
Speaker: Sam Adriaensen, WPI and Vrije Universiteit Brussel
Title: Hat guessing games on graphs
Abstract: Many games in recreational mathematics involve a warden playing a sadistic game on a group of smart prisoners. In this talk we will analyze one such type of game. Imagine the warden assigns a hat to each prisoner, and every hat has a color from a pre-determined set of colors. Each prisoner sees the hats of all other prisoners, but not themself. Then all prisoners make simultaneous guesses as to which color of hat they have. If at least one prisoner guesses correctly, the prisoners win the game and regain their freedom. The question we ask is:
Given the number of prisoners, say n, what is the largest number of hat colors, say q, such that the prisoners can devise a strategy that guarantees victory?
This question is not too hard to answer. (You might try it yourself, or see the answer in the beginning of the talk.) The question becomes more interesting if we restrict which prisoners can see each other. A graph is the perfect tool to describe this setting. The hat guessing number of a graph G is then defined to be the largest number q of colors for which the prisoners can guarantee a winning strategy, when G describes visibility between prisoners.
In this talk, we will discuss some of the known results concerning hat guessing. I might also discuss some new results obtained during a Polymath Jr project co-mentored with Anurag Bishnoi and Jame Tuite.