Metraipolis › archive › dc_26a2dc1de41b
An upper bound on the proper hat guessing number of graphs — arXiv:2610.04124
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.04124
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T13:49:09.972Z
- SHA-256 of the archived text
28016b033a6decdc6cb0a566f35b758ca725d8196ecd06eb615d2ecceb9d7601- Stable URL of this page
https://metraipolis.com/documento/dc_26a2dc1de41b
How to cite
An upper bound on the proper hat guessing number of graphs — arXiv:2610.04124 — arXiv (en), https://arxiv.org/abs/2610.04124 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_26a2dc1de41b (Metraipolis archive dc_26a2dc1de41b, sha256 28016b033a6decdc6cb0a566f35b758ca725d8196ecd06eb615d2ecceb9d7601)
BibTeX
@misc{dc26a2dc1de41b,
title = {An upper bound on the proper hat guessing number of graphs — arXiv:2610.04124},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.04124},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_26a2dc1de41b; sha256 28016b033a6decdc6cb0a566f35b758ca725d8196ecd06eb615d2ecceb9d7601},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.04124. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the proper hat guessing game on graphs, introduced by Adriaensen et al. \cite{adriaensen2026hatguessingpropercolorings}. In this game, the players are seated on the vertices of a graph $G$ and assigned hats from a set of $k$ colors such that the resulting assignment forms a proper coloring. The visibility of each vertex is limited to the hat colors of their neighborhood. Then they must simultaneously output a guess about the color of their own hat. The players win if at least one guess is correct. A parameter related to this problem is the proper hat guessing number $\operatorname{HG}_{P}(G)$ that is the maximum number of colors $m$ such that the players can guarantee a winning strategy. Motivated by the work of Shurman et al. \cite{shurman2026upper}, we establish the first upper bound that depends both on the number of vertices $n$ and the maximum degree $\Delta$ in the case where $\Delta \geq \frac{n}{e+1}$. This result leads us to show that the proper hat guessing number of the binomial random graph $G_{n,1/2}$ is bounded above by $cn$, where $c \approx 1.366$. Finally, we prove that graphs of maximum degree $(1-\gamma)n$ for some fixed $\gamma \in (0,1]$ cannot have $\operatorname{HG}_{P}(G) = (2-o(1))n$.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2610.04124 — 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-10-06T12:06:32.211Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).