The Hats game. On max degree and diameter
Aleksei Latyshev, K. P. Kokhas · arXiv (Cornell University) · 2021
We analyze the following version of the deterministic Hats game. Several sages wearing colored hats occupy the vertices of a graph. Each sage can have a hat of one of $k$ colors. Each sage tries to guess the color of his own hat merely on the basis of observing the hats of his neighbors without exchanging any information. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colors. The maximal number $k$ for which the specific graph $G$ is winning called hat guessing number (or $HG(G)$). We contradicted the famous hypothesis that $HG(G) \le \Delta + 1$ and proved that diameter of graph and $HG(G)$ are independent.