TY - JOUR

T1 - The Hats game. On maximum degree and diameter

AU - Latyshev, Aleksei

AU - Kokhas, Konstantin

N1 - Publisher Copyright: © 2022 Elsevier B.V.

PY - 2022/7/1

Y1 - 2022/7/1

N2 - We analyze the following version of the deterministic HATS game. We have a graph G, and a sage resides at each vertex of G. When the game starts, an adversary puts on the head of each sage a hat of a color arbitrarily chosen from a set of k possible colors. Each sage can see the hat colors of his neighbors but not his own hat color. All of sages are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. The strategy is winning if it guarantees at least one correct individual guess for every assignment of colors. Given a graph G, its hat guessing number HG(G) is the maximal number k such that there exists a winning strategy. We disprove the hypothesis that HG(G)≤Δ+1 and demonstrate that diameter of graph and HG(G) are independent.

AB - We analyze the following version of the deterministic HATS game. We have a graph G, and a sage resides at each vertex of G. When the game starts, an adversary puts on the head of each sage a hat of a color arbitrarily chosen from a set of k possible colors. Each sage can see the hat colors of his neighbors but not his own hat color. All of sages are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. The strategy is winning if it guarantees at least one correct individual guess for every assignment of colors. Given a graph G, its hat guessing number HG(G) is the maximal number k such that there exists a winning strategy. We disprove the hypothesis that HG(G)≤Δ+1 and demonstrate that diameter of graph and HG(G) are independent.

KW - Deterministic strategy

KW - Graphs

KW - Hat guessing game

KW - Hat guessing number

UR - http://www.scopus.com/inward/record.url?scp=85125737127&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/d8ed9807-536e-35a6-b6ec-cd5c8ece8c5e/

U2 - 10.1016/j.disc.2022.112868

DO - 10.1016/j.disc.2022.112868

M3 - Article

AN - SCOPUS:85125737127

VL - 345

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 7

M1 - 112868

ER -