Hat guessing game limits match Lovász Local Lemma predictions
The Lovász Local Lemma Is Sharp for the Hat Guessing Number
Discrete Mathematics
Summary
The paper studies a hat guessing game played on a network where each player can only see their neighbors' hat colors. The main question is how many colors can be used while still guaranteeing that someone guesses correctly every time. The authors prove that a known mathematical bound called the Lovász Local Lemma is nearly exact in this setting. This resolves a previous open question and disproves a prior guess about the game's limits. Their result shows the hat guessing number can be as large as nearly e times the maximum number of neighbors.
What this means in practice
- •For network protocol designers: Use tight bounds on guessing strategies in networks constrained by local information to design protocols with guaranteed detection capabilities.
- •For distributed system engineers: Incorporate limits on local guessing accuracy into fault-tolerant system designs where nodes must make decisions based on neighbors.
A theory result. No direct application yet.
Authors
Thomas Delépine, Matthieu Rosenfeld
Abstract
In the hat guessing game on a graph $G$, each vertex is occupied by a player wearing a hat whose color is chosen from a set of $q$ colors. Each player knows the graph and their position in it and sees only the hat colors of their neighbors. The players may agree on a strategy beforehand but must simultaneously try to guess their own hat colors without communicating. They win if at least one player guesses their own hat color correctly. The hat guessing number of $G$, denoted by $\textrm{HG}(G)$, is the largest integer $q$ for which the players have a strategy that guarantees a win for every assignment of hat colors. A direct application of the symmetric Lovász Local Lemma shows that $\textrm{HG}(G) < eΔ$ for every graph $G$ of maximum degree at most $Δ\ge 1$. We prove that this bound is asymptotically sharp: for every $\varepsilon > 0$ and every sufficiently large $Δ$, there exists a graph $G$ of maximum degree at most $Δ$ with $\textrm{HG}(G) \ge (e - \varepsilon)Δ$. This answers a question of Alon et al., disproves the conjecture $\textrm{HG}(G) \le 2Δ(G)$ of Bosek et al., and improves on the construction of Latyshev and Kokhas, which achieves $\textrm{HG}(G) = 4Δ(G)/3$. The hat guessing number thus provides a natural combinatorial problem in which the Lovász Local Lemma is asymptotically tight.