The hat guessing number of graphs

DOI10.1016/j.jctb.2020.01.003zbMath1443.05123arXiv1812.09752OpenAlexW3000929545MaRDI QIDQ777481

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

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

complete bipartite graphcombinatorial nullstellensatzLovász local lemmahat guessing number

Mathematics Subject Classification ID

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

Related Items (14)

The Hats game. On maximum degree and diameter ⋮ Bears with hats and independence polynomials ⋮ On the hat guessing number of a planar graph class ⋮ Hat Guessing Numbers of Strongly Degenerate Graphs ⋮ Hat guessing number for the class of planar graphs is at least 22 ⋮ Hat guessing numbers of degenerate graphs ⋮ Hat chromatic number of graphs ⋮ Cliques and constructors in ``Hats game. I ⋮ Cliques and constructors in ``Hats game. II ⋮ The Hats game. The power of constructors ⋮ On the stability and instability of finite dynamical systems with prescribed interaction graphs ⋮ Hat guessing on books and windmills ⋮ On the hat guessing number of graphs ⋮ Hat problem: a new strategy based on quantum stabilizer codes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The three colour hat guessing game on cycle graphs
• A nowhere-zero point in linear mappings
• On a problem of Spencer
• Information flows, graphs and their guessing numbers
• Orthogonal representations over finite fields and the chromatic number of graphs
• On the hat problem on a graph
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Fredman–Komlós bounds and information theory
• Zero error capacity under list decoding
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• Combinatorial Nullstellensatz
• 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
• Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
• Zero Error List-Decoding Capacity of the q/(q–1) Channel
• Derandomization of auctions
• Hat Guessing Games

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