Metraipolis › archive › dc_34db316228be

The Lovász Local Lemma Is Sharp for the Hat Guessing Number — arXiv:2611.04577

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04577
License (as archived)
CC0-1.0
Archived
2026-11-04T19:00:19.284Z
SHA-256 of the archived text
fcd6d75007cc6be6e3cb50b658b5d13cd18cd6f657fcf253a056526077807dc0
Stable URL of this page
https://metraipolis.com/documento/dc_34db316228be

How to cite

The Lovász Local Lemma Is Sharp for the Hat Guessing Number — arXiv:2611.04577 — arXiv (en), https://arxiv.org/abs/2611.04577 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_34db316228be (Metraipolis archive dc_34db316228be, sha256 fcd6d75007cc6be6e3cb50b658b5d13cd18cd6f657fcf253a056526077807dc0)
BibTeX
@misc{dc34db316228be,
  title = {The Lovász Local Lemma Is Sharp for the Hat Guessing Number — arXiv:2611.04577},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04577},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_34db316228be; sha256 fcd6d75007cc6be6e3cb50b658b5d13cd18cd6f657fcf253a056526077807dc0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04577. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\Delta$ for every graph $G$ of maximum degree at most $\Delta \ge 1$. We prove that this bound is asymptotically sharp: for every $\varepsilon > 0$ and every sufficiently large $\Delta$, there exists a graph $G$ of maximum degree at most $\Delta$ with $\textrm{HG}(G) \ge (e - \varepsilon)\Delta$. This answers a question of Alon et al., disproves the conjecture $\textrm{HG}(G) \le 2\Delta(G)$ of Bosek et al., and improves on the construction of Latyshev and Kokhas, which achieves $\textrm{HG}(G) = 4\Delta(G)/3$. The hat guessing number thus provides a natural combinatorial problem in which the Lovász Local Lemma is asymptotically tight.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2611.04577 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:38:22.313Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).