The hat guessing number of graphs

DOI10.1016/J.JCTB.2020.01.003zbMATH Open1443.05123arXiv1812.09752OpenAlexW3000929545MaRDI QIDQ777481FDOQ777481

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)

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)