The Lovász Local Lemma Is Sharp for the Hat Guessing Number
Source: arxiv.org/abs/2611.04577
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.04577
curl -X POST /api/v1/records/arxiv/2611.04577/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.04577/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'