TY - JOUR

T1 - The hat guessing number of graphs

AU - Alon, Noga

AU - Ben-Eliezer, Omri

AU - Shangguan, Chong

AU - Tamo, Itzhak

N1 - Funding Information:
The research of Noga Alon was supported by NSF grant DMS-1855464 , ISF grant 281/17 , BSF grant 2018267 and the Simons Foundation . The research of Chong Shangguan and Itzhak Tamo was supported by ISF grant No. 1030/15 and NSF-BSF grant No. 2015814 .
Publisher Copyright:
© 2020 Elsevier Inc.

PY - 2020/9

Y1 - 2020/9

N2 - Consider the following hat guessing game: n players are placed on n vertices of a graph, 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. Given a graph G, its 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 2008, Butler et al. asked whether the hat guessing number of the complete bipartite graph Kn,n is at least some fixed positive (fractional) power of n. We answer this question affirmatively, showing that for sufficiently large n, the complete r-partite graph Kn,…,n satisfies HG(Kn,…,n)=Ω(n[Formula presented]−o(1)). Our guessing strategy is based on a probabilistic construction and other combinatorial ideas, and can be extended to show that HG(C→n,…,n)=Ω(n[Formula presented]−o(1)), where C→n,…,n is the blow-up of a directed r-cycle, and where for directed graphs each player sees only the hat colors of his outneighbors. Additionally, we consider related problems like the relation between the hat guessing number and other graph parameters, and the linear hat guessing number, where the players are only allowed to use affine linear guessing strategies. Several nonexistence results are obtained by using well-known combinatorial tools, including the Lovász Local Lemma and the Combinatorial Nullstellensatz. Among other results, it is shown that under certain conditions, the linear hat guessing number of Kn,n is at most 3, exhibiting a huge gap from the Ω(n[Formula presented]−o(1)) (nonlinear) hat guessing number of this graph.

AB - Consider the following hat guessing game: n players are placed on n vertices of a graph, 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. Given a graph G, its 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 2008, Butler et al. asked whether the hat guessing number of the complete bipartite graph Kn,n is at least some fixed positive (fractional) power of n. We answer this question affirmatively, showing that for sufficiently large n, the complete r-partite graph Kn,…,n satisfies HG(Kn,…,n)=Ω(n[Formula presented]−o(1)). Our guessing strategy is based on a probabilistic construction and other combinatorial ideas, and can be extended to show that HG(C→n,…,n)=Ω(n[Formula presented]−o(1)), where C→n,…,n is the blow-up of a directed r-cycle, and where for directed graphs each player sees only the hat colors of his outneighbors. Additionally, we consider related problems like the relation between the hat guessing number and other graph parameters, and the linear hat guessing number, where the players are only allowed to use affine linear guessing strategies. Several nonexistence results are obtained by using well-known combinatorial tools, including the Lovász Local Lemma and the Combinatorial Nullstellensatz. Among other results, it is shown that under certain conditions, the linear hat guessing number of Kn,n is at most 3, exhibiting a huge gap from the Ω(n[Formula presented]−o(1)) (nonlinear) hat guessing number of this graph.

KW - Combinatorial Nullstellensatz

KW - Complete bipartite graph

KW - Hat guessing number

KW - Lovász Local Lemma

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

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

U2 - 10.1016/j.jctb.2020.01.003

DO - 10.1016/j.jctb.2020.01.003

M3 - Article

AN - SCOPUS:85078363654

SN - 0095-8956

VL - 144

SP - 119

EP - 149

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -