The Lovász Local Lemma Is Sharp for the Hat Guessing Number
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 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 HG(G) < eΔ for every graph G of maximum degree at most Δ≥ 1. We prove that this bound is asymptotically sharp: for every ε > 0 and every sufficiently large Δ, there exists a graph G of maximum degree at most Δ with HG(G) ≥ (e − ε)Δ. This answers a question of Alon et al., disproves the conjecture HG(G) ≤ 2Δ(G) of Bosek et al., and improves on the construction of Latyshev and Kokhas, which achieves 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.
Related
BibTeX
@misc{delepine2026lovász,
title = {{The Lovász Local Lemma Is Sharp for the Hat Guessing Number}},
author = {Thomas Delépine and Matthieu Rosenfeld},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04577},
eprint = {2611.04577},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04577},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Lovász Local Lemma Is Sharp for the Hat Guessing Number
AU - Thomas Delépine
AU - Matthieu Rosenfeld
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04577
UR - https://arxiv.org/abs/2611.04577
AB - 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 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 HG(G) < eΔ for every graph G of maximum degree at most Δ≥ 1. We prove that this bound is asymptotically sharp: for every ε > 0 and every sufficiently large Δ, there exists a graph G of maximum degree at most Δ with HG(G) ≥ (e − ε)Δ. This answers a question of Alon et al., disproves the conjecture HG(G) ≤ 2Δ(G) of Bosek et al., and improves on the construction of Latyshev and Kokhas, which achieves 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.
ER -