On the hat guessing number of graphs

Noga Alon, Jeremy Chizewer

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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))log2⁡n 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.

Original languageEnglish (US)
Article number112785
JournalDiscrete Mathematics
Volume345
Issue number4
DOIs
StatePublished - Apr 2022

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Hat-guessing number
  • Planar graph
  • Random graph

Fingerprint

Dive into the research topics of 'On the hat guessing number of graphs'. Together they form a unique fingerprint.

Cite this