TY - JOUR
T1 - On the hat guessing number of graphs
AU - Alon, Noga
AU - Chizewer, Jeremy
N1 - Funding Information:
This research was supported in part by National Science Foundation Grant DMS-1855464 , and U.S.-Israel Binational Science Foundation Grant 2018267 . We thank Ben Przybocki for telling us about [12] .
Publisher Copyright:
© 2021 Elsevier B.V.
PY - 2022/4
Y1 - 2022/4
N2 - The hat guessing number HG(G) of a graph G on n vertices is defined in terms of the following game: n players are placed on the n vertices of G, each wearing a hat whose color is arbitrarily chosen from a set of q possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players 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 hat guessing number HG(G) is the largest integer q such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of q possible colors. In this note we construct a planar graph G satisfying HG(G)=12, settling a problem raised in Bosek et al. ((2021) [4]). We also improve the known lower bound of (2−o(1))log2n for the typical hat guessing number of the random graph G=G(n,1/2), showing that it is at least n1−o(1) with probability tending to 1 as n tends to infinity. Finally, we consider the linear hat guessing number of complete multipartite graphs.
AB - The hat guessing number HG(G) of a graph G on n vertices is defined in terms of the following game: n players are placed on the n vertices of G, each wearing a hat whose color is arbitrarily chosen from a set of q possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players 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 hat guessing number HG(G) is the largest integer q such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of q possible colors. In this note we construct a planar graph G satisfying HG(G)=12, settling a problem raised in Bosek et al. ((2021) [4]). We also improve the known lower bound of (2−o(1))log2n for the typical hat guessing number of the random graph G=G(n,1/2), showing that it is at least n1−o(1) with probability tending to 1 as n tends to infinity. Finally, we consider the linear hat guessing number of complete multipartite graphs.
KW - Hat-guessing number
KW - Planar graph
KW - Random graph
UR - http://www.scopus.com/inward/record.url?scp=85123200014&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85123200014&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2021.112785
DO - 10.1016/j.disc.2021.112785
M3 - Article
AN - SCOPUS:85123200014
SN - 0012-365X
VL - 345
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 4
M1 - 112785
ER -