List of sources used to create this summary can be found at the bottom of the page.

Problem statement

We are given a graph $G$ and number of colors $K$. Vertices of $G$ are occupied by players (called Bears) which can see all their neighbors but not themselves. Each of them will be given a hat in one of $K$ colors (multiple Bears can have the same color) and their task is to come up with a collective strategy such that at least one of them will guess his hat correctly. The guess may depend only on hat colors of Bear’s neighbors. The coloring of $G$ is chosen by an evil adversary (called Demon) who knows bears’ strategy. If the Bears are guaranteed that at least one correct guess in each coloring, then their strategy wins.

The hat chromatic number $\mu(G)$ is the maximum number of colors $K$ such that there is a strategy which wins.

Known results and conjectures

Classic version

Example: Let us have a graph containing a single edge between two vertices. Each vertex is occupied by a player, who sees only the other player (not himself). Each of them gets a hat which is either red or blue. How should they plan their guesses so that when guessing their hat color simultaneously at least one of them will be correct?

Observation (monotocity): If Bears win for $K$ then they win for each $K’<K$ by shrinking the strategy.

Lemma (number of correct guesses): Every Bear guesses exactly $1/k$ of all colorings correctly.

Proof: Fix all colors except for one Bear. The Bear’s guess is now fixed, and by changing his hat-color, we hit his guess exactly once out of $k$ cases. As the fixed coloring of the other vertices can be arbitrary, this covers all possible colorings.

Observation (general upper bound): $\mu(G) \le |G|$

Proof: By the previous lemma, one Bear guesses correctly exactly $1/k$ times. Using union bound we get that the chance for “at least one Bear has correct guess” does not exceed $|G|/k$. If the strategy is winning, then the sum over the ratios of correct guesses must give at least $1$. So for any $k \le \mu(G)$ it holds that $1 \le |G|/k$, which is eqvivalent to $k \le |G|$. In particular, that inequality is true for $k=\mu(G)$ as well, hence $\mu(G) \le |G|$.

Theorem (cliques): $\mu(K_n) = n$

Proof: The strategy for $i$-th bear is $S_i = (i - \sum\text{(colors of other Bears)}) \bmod n$. Let $M$ be the sum of all bears’ colors. We see that if $M=i$ then the $i$-th bear guesses correctly. As $0 \le M < n$ we have that exactly one bear guesses correctly in every coloring.

Theorem (non-cliques upperbound): $\mu(G) < |G|$ if G is not a clique

Proof: Recall the proof of “general upper bound”. If two vertices A and B are not connected then we can watch coloring from their (independent) point of view. There is a chance $1/k^2$ that their are both right. Hence the union bound of $1/k$ for all vertices except A and B and their contribution $2/k - 1/k^2$ gives $1\le|G|/k-1/k^2$, hence $k<|G|$, therefore $\mu(G) < |G|$.

Observation (subgraphs): $\mu(G’) \le \mu(G)$ for $G’$ subgraph of $G$

Theorem (cycle, Szczechla 2010, CONF ↗, PDF ↗): $\mu(C_n)=3$ for $n=4$ or $n=3 k$, otherwise $\mu(C_n)=2$.

We shall not prove the Theorem in its entirety as it is rather complex.

Proof (only for $C_4$): $\mu(C_4) < 4$ by “non-cliques upperbound”. Bears guess (in order) G1=(X2+X4), G2=(-X1+X3), G3=(-X2+X4), G4=(-X1-X3). The correctness can be checked by brute-force.

Theorem (paths): $\mu(P_N)=2$ for $N \ge 2$

Proof: $\mu(P_N) \ge 2$ by $K_2 \subseteq P_N$, and $\mu(P_N)<3$ by “loosing path” theorem.

Theorem (trees, Butler, et al., PDF ↗): $\mu(T) \le 2$

Conjecture (strong coloring number) : $\mu(G) \le col(G)$

Conjecture (weak coloring number): $\mu(G) \le f(col(G))$ for some function f

Conjecture (strong planar): $\mu(G) \le 4$ for planar graphs

Conjecture (weak planar): $\mu(G) \le C$ for planar graph for some constant C

Theorem (planar, TODO REF): $\mu(G) \le 6$ for planar graphs G with girth at least 14

Theorem (max degree): $\mu(G) \le e(\Delta + 1)$

Proof: In random coloring each vertex has chance of 1/k to guess its color. Apply LLL $ep(d+1) \le 1$ where $p=1/k$, $d \le \Delta$, and get that if $k \ge e (\Delta +1)$, then noone guesses his color correctly, i.e., $\mu(G) \le e(\Delta + 1)$.

Conjecture (max degree): $\mu(G) \le \Delta + 1$

Observation (max clique): By the subgraph observation, we have that $\omega(G) \le \mu(G)$.

Conjecture (max clique): $\chi(G) \le \mu(G)+1$

Conjecture (Hadwiger number ↗): $\mu(G) \le h(G)$

Theorem (vertex addition lowerbound): If we can win on a graph G then we can win on a graph G’ = G \cup V where V is a new vertex which is arbitrarily connected to G, by V guessing 2, neighbors of V adding 1 to their guess and rest stays the same.

Proof: TODO

List version

If each Bear has a list of colors from which the color is chosen (similarly to list coloring), we get a different, more configurable, version of hat chromatic number problem. We will denote the order of list by a simple number, and represent order of all Bear lists as (A1,A2,…,AN). Note that it does not matter which colors are in the lists.

Observation (monotocity): If every Bear has list of smaller or same order, then the list hat chromatic number cannot increase.

Theorem (loosing path): On a path $P_N$ with lists of orders (3,3,…,3,2) Bears lose.

Proof: For N=1 the claim is trivial. For all N>1 we note that the last Bear A guess is based on second to last Bear B. B’s list has 3 elements, so A guesses the same color twice, say he guesses 1 when he sees 1 or 2 on B. We put color 2 on A and restrict ourselvest to colors 1 and 2 for B, diregard A which cannot win, and use induction on path shorter by one.

Theorem (losing cycle): On a cycle $C_N$ with list of orders (4,3,…,3) Bears lose.

Proof: TODO Let us focus on Bear B with list of 4 colors in $C_N$ who has neighbors A and C. We will show that he can be colored so that he does not guess his color and reduce the rest to path and use ’losing path’ theorem. … TODO

Sources

todos