The hat guessing number of graphs

DOI10.1016/J.JCTB.2020.01.003MaRDI QIDQ777481zbMATH OpenOpenAlexFDO

Authors Noga Alon, Omri Ben-Eliezer, Chong Shangguan, Itzhak Tamo

Publication date 7 July 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.09752

zbMATH Keywords

combinatorial nullstellensatzcomplete bipartite graphhat guessing numberLovász local lemma

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: 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 $mHG(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 $K_{n,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 $K_{n,ldots,n}$ satisfies $mHG(K_{n,ldots,n})=Omega(n^{fracr-1r-o(1)})$. Our guessing strategy is based on a probabilistic construction and other combinatorial ideas, and can be extended to show that $mHG(vec{C}_{n,ldots,n})=Omega(n^{frac1r-o(1)})$, where $vec{C}_{n,ldots,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.

Recommendations

• On the hat guessing number of graphs
• A construction for the hat problem on a directed graph
• The Hats game. On maximum degree and diameter
• On optimal strategies for a hat game on graphs
• Hat Guessing Numbers of Strongly Degenerate Graphs

Cites work

• scientific article; zbMATH DE number 3745081 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• A modified hat problem
• A nowhere-zero point in linear mappings
• Combinatorial Nullstellensatz
• Derandomization of auctions
• Finite dynamical systems, hat games, and coding theory
• Fredman–Komlós bounds and information theory
• Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
• Hat Guessing Games
• Information flows, graphs and their guessing numbers
• New constructions and bounds for Winkler's hat game
• Nonlinear Index Coding Outperforming the Linear Optimum
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• On a problem of Spencer
• On the Autoreducibility of Random Sequences
• On the Size of Separating Systems and Families of Perfect Hash Functions
• On the hat problem on a graph
• Orthogonal representations over finite fields and the chromatic number of graphs
• Puzzlers' tribute. A feast for the mind
• Testing Equality in Communication Graphs
• The probabilistic method
• The three colour hat guessing game on cycle graphs
• Zero Error List-Decoding Capacity of the q/(q–1) Channel
• Zero error capacity under list decoding

Cited in

(24)

• Hat guessing numbers of degenerate graphs
• Hat problem: a new strategy based on quantum stabilizer codes
• On the hat guessing number of a planar graph class
• A note on marking lines in \([k]^n\)
• Guessing games on triangle-free graphs
• A construction for the hat problem on a directed graph
• The Hats game. On maximum degree and diameter
• Cliques and constructors in ``Hats game. I
• Cliques and constructors in ``Hats game. II
• The Hats game. The power of constructors
• Hat guessing number for the class of planar graphs is at least 22
• A New Variation of Hat Guessing Games
• Bears with hats and independence polynomials
• On the stability and instability of finite dynamical systems with prescribed interaction graphs
• The hat guessing game on cactus graphs and cycles
• Bears with hats and independence polynomials
• Hat Guessing Numbers of Strongly Degenerate Graphs
• scientific article; zbMATH DE number 5881230 (Why is no real title available?)
• Hat guessing on books and windmills
• On the hat guessing number of graphs
• On a conjecture of Butler and Graham
• Hat chromatic number of graphs
• New constructions and bounds for Winkler's hat game
• Hat Guessing Games

This page was built for publication: The hat guessing number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777481)