Hat guessing with proper colorings

arXiv (Cornell University)

Abstract

We initiate the study of the hat guessing number of a graph where the adversary is only allowed to provide a proper coloring of the graph. This is the largest number $q$ for which there is a guessing strategy on each vertex that only depends on its neighborhood, such that for every proper coloring of the graph with $q$ colors at least one vertex guesses its color correctly. In this variation, we prove that the hat guessing number of the complete graphs on $n$ vertices is $2n - 1$, which is roughly twice the classical hat guessing number of the complete graph. Our winning strategy is related to finding perfect matchings between the middle layers of the boolean poset of dimension $2n - 1$. We prove that the hat guessing number of all trees on $n \geq 3$ vertices is equal to $4$. We derive general upper bounds in terms of the number of vertices, chromatic number, and maximum degree, and obtain improved bounds for book graphs. Using our results and an ILP formulation of the problem, we determine the exact hat guessing number for all graphs on at most $4$ vertices, give bounds on graphs on $5$ vertices, and suggest some open problems.

Authors 9

1. Sam Adriaensen

   Vrije Universiteit Brussel

   Affiliation as printed

   Department of Mathematics and Data Science , Vrije Universiteit Brussel , Belgium

2. Peter Bentley

   William & Mary

   Affiliation as printed

   Department of Mathematics , William & Mary , Virginia , United States

3. Anurag Bishnoi

   Delft University of Technology

   Affiliation as printed

   Delft Institute of Applied Mathematics , Delft University of Technology , Netherlands

4. Wouter Cames van Batenburg
5. Michael Kreiger

   University of Illinois Urbana-Champaign

   Affiliation as printed

   Department of Mathematics , University of Illinois Urbana-Champaign , Illinois , United States

6. Lars van der Kuil Aachen Leiden Institute of Advanced Computer Science

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science , Leiden University , Netherlands

7. Saptarshi Mandal

   Indian Institute of Technology Kanpur

   Affiliation as printed

   Theoretical Statistics and Department of Mathematics and Statistics , IIT Kanpur , India

8. Anurag Ramachandran

   Indian Statistical Institute

   Affiliation as printed

   Theoretical Statistics and Mathematics Unit , Indian Statistical Institute , Bangalore , India

9. James Tuite

   The Open University · Lithuania Business University of Applied Science

   Affiliation as printed

   Department of Informatics and Statistics , Klaip ėda University , Klaip ėda , Lithuania

   School of Mathematics and Statistics , Open University , Milton Keynes , UK