Hat guessing with proper colorings

This paper initiates the study of the hat guessing number under the constraint that the adversary must provide a proper coloring, establishing that complete graphs have a guessing number of $2n-1$, all trees on$n \geq 3$vertices have a guessing number of$4$, and providing general bounds, exact results for small graphs, and new conjectures for this variation.

The Gist

Imagine a game of "Hat Guessing" played by a group of friends sitting in a circle (or any shape) where everyone can see their friends' hats but not their own.

In the classic version of this game, an evil villain (the "adversary") can put any color hat on anyone, even if two best friends sitting next to each other get the exact same color. The goal is for the group to agree on a secret strategy beforehand so that at least one person guesses their own hat color correctly, no matter how the villain tries to trick them.

In this new paper, the authors introduce a twist: The villain is now forced to play by the rules of a "Proper Coloring." This means no two friends sitting next to each other can have the same color hat. It's like a strict dress code for the game. The question becomes: How many different hat colors can the villain use before the group is guaranteed to lose?

Here is a breakdown of their findings using simple analogies:

1. The "All-Connected" Group (Complete Graphs)

Imagine a group where everyone is friends with everyone else (a complete clique).

• The Old Rule: If there are $n$ people, the group can handle up to $n$ colors.
• The New Rule (Proper): Because neighbors can't match, the villain is more restricted. Surprisingly, this restriction actually helps the players! The authors proved that for a group of $n$ people, they can now handle up to $2n - 1$ colors.
• The Analogy: Think of it like a puzzle. In the old game, the villain could throw a chaotic mess of colors at you. In the new game, the villain has to arrange the colors in a specific pattern (no neighbors matching). The players realized they can use this pattern to their advantage.
• How they did it: They used a mathematical trick involving "perfect matchings." Imagine a dance floor with two groups of people. The players found a way to pair every possible "view" of the neighbors with a specific guess, ensuring that for every valid pattern the villain creates, someone in the group is dancing to the right beat.

2. The "Tree" Family (Trees)

Now imagine the friends are arranged in a family tree structure (one person at the top, branching out, no loops).

• The Finding: No matter how big the tree gets (as long as it has at least 3 people), the group can only guarantee a win if the villain uses 4 colors.
• The Analogy: Think of a tree as a chain of command. If the villain tries to use 5 or more colors, the "branches" get too complex, and the players can't coordinate a strategy that covers every possibility. But with 4 colors, they have just enough room to maneuver.
• The Logic: They proved that if you have a winning strategy for a big tree, you can "chop off" the leaves (the ends of the branches) without losing your ability to win. Eventually, you are left with a tiny 3-person tree, which they proved can handle exactly 4 colors.

3. The "Book" Graphs

Imagine a "book" where the spine is a tight group of friends (a clique), and the pages are a group of friends who only talk to the spine, not to each other.

• The Finding: If the "pages" (the independent set) are very numerous compared to the "spine," the number of colors the group can handle drops significantly.
• The Analogy: Imagine a loud party (the spine) surrounded by a huge crowd of quiet observers (the pages). If the crowd gets too big, the noise from the spine drowns out the observers' ability to coordinate. The authors calculated exactly how big the crowd can get before the strategy breaks down.

4. The "Small Graph" Detective Work

For very small groups (3, 4, or 5 people), the authors acted like detectives. They used a computer program (an "Integer Linear Programming" solver) to test every single possible arrangement of friends and hats.

• They created a "cheat sheet" (Table 1 in the paper) that lists the exact maximum number of colors for every possible shape of a small group.
• For example, a square of 4 friends ($C_4$) can handle 4 colors, but a square with one extra connection ($K_4 - e$) can handle 6.

Why Does This Matter?

This isn't just a party game. These hat-guessing problems are actually deep mathematical puzzles related to coding theory and network security.

• Coding: If you can guess a hat color correctly, you are essentially correcting an error in a message.
• Security: The "adversary" represents a hacker trying to break a code. Understanding how many "colors" (variables) a system can handle before it fails helps engineers build stronger, more secure networks.

The Big Takeaway

The paper shows that restricting the enemy (the villain) actually makes the game harder for the enemy, not the players. By forcing the villain to follow the "no matching neighbors" rule, the players gain more information and can handle nearly twice as many colors as they could in the chaotic, unrestricted version of the game.

The authors have solved the puzzle for perfect groups (cliques) and tree-like groups, but they are still working on the "Book" shapes and other complex structures, inviting future mathematicians to join the hunt!

Technical Summary

Here is a detailed technical summary of the paper "Hat guessing with proper colorings" by Adriaensen et al.

1. Problem Definition

The paper investigates a variant of the classical hat guessing game on graphs.

• The Game: A graph $G=(V, E)$ represents players (vertices) and their visibility (edges). An adversary assigns a hat color from a set $[q] = \{1, \dots, q\}$ to each player.
• The Constraint (Proper Coloring): Unlike the classical game where any assignment of colors is allowed, the adversary is restricted to assigning colors that form a proper coloring of $G$. That is, no two adjacent vertices share the same color.
• The Goal: Players must simultaneously guess their own hat color based only on the colors of their neighbors. A strategy is "winning" if, for every possible proper coloring of $G$ with $q$ colors, at least one player guesses correctly.
• The Parameter: The proper hat guessing number, denoted $HGP(G)$, is the largest integer $q$ for which a winning strategy exists.
• Relation to Classical: Since the set of proper colorings is a subset of all colorings, $HG(G) \leq HGP(G)$. The paper explores how much larger $HGP(G)$ can be compared to the classical $HG(G)$.

2. Methodology and Tools

The authors employ a mix of combinatorial constructions, graph theory, and optimization techniques:

• Combinatorial Matching: For complete graphs, the strategy relies on constructing perfect matchings between layers of the Boolean poset (specifically between sets of size $n-1$ and $n$ from a set of size $2n-1$). This utilizes Hall's Marriage Theorem.
• Probabilistic Bounds: Upper bounds are derived using expectation arguments. By analyzing the probability of a correct guess under a uniform random proper coloring, the authors derive inequalities relating $HGP(G)$ to the number of vertices $n$ and the chromatic number $\chi(G)$.
• Inductive Reduction: For trees, the authors use a "leaf removal" lemma. They prove that if a graph has a vertex of degree 1 and a sufficiently high guessing number, removing that vertex does not change the guessing number.
• Integer Linear Programming (ILP): To determine exact values for small graphs (up to 5 vertices), the authors formulate the existence of a winning strategy as a feasibility problem in ILP. Variables represent whether a player guesses a specific color given a specific neighbor pattern.
• Counting Arguments: For book graphs, the authors count the number of proper colorings where specific vertices guess correctly versus incorrectly to derive upper bounds.

3. Key Contributions and Results

A. Complete Graphs ($K_n$)

• Result: $HGP(K_n) = 2n - 1$.
• Significance: This is roughly twice the classical hat guessing number of a complete graph (which is $n$).
• Proof Strategy:
  • Upper Bound: Derived from a general lemma $HGP(G) \leq n + \chi(G) - 1$. Since $\chi(K_n) = n$, this yields $2n-1$.
  • Lower Bound: Constructed using a bijection between strings of length $n$ and pairs of (index, string of length $n-1$). This corresponds to finding a perfect matching between the $(n-1)$-th and $n$-th layers of the Boolean lattice of dimension $2n-1$. The strategy involves players guessing the color corresponding to the "left-most unmatched left parenthesis" in a specific ordering of colors.

B. Trees

• Result: For any tree $T$ with $n \geq 3$ vertices, $HGP(T) = 4$.
• Significance: This is a sharp contrast to the classical hat guessing number for trees, which is generally 2 (or 3 for small cases). The restriction to proper colorings significantly increases the difficulty for the players (allowing more colors) but the structural constraints of trees limit the number to a constant.
• Proof Strategy:
  • Base case: Proven for $P_3$ (path of 3 vertices) using a strategy over $\mathbb{Z}_2 \times \mathbb{Z}_2$.
  • Induction: Proved that removing a leaf (degree 1 vertex) preserves the guessing number if it is $\geq 5$. Since all trees have leaves, the number reduces to the base case $P_3$.

C. Book Graphs ($B_{k,n}$)

• Definition: A clique of size $k$ (spine) connected to an independent set of size $n$ (pages).
• Result: If $n > e^{2k}$, then $HGP(B_{k,n}) < \left(\frac{e^{2k}}{n}\right)^{1/n} (n + k + 1)$.
• Asymptotic Behavior: If $k = O(n^{1-\epsilon})$, then $HGP(B_{k,n}) = O(n / \ln n)$.
• Significance: This provides improved bounds over the general $n + \chi(G) - 1$ bound when the number of pages is large relative to the spine.

D. General Bounds

• Upper Bound: $HGP(G) \leq n + \chi(G) - 1$.
• Relation to Classical: $HGP(G) < \chi(G)(HG(G) + 1)$.
• Degree Bound: $HGP(G) < \lceil e\Delta(G) \rceil (\Delta(G) + 1)$, where $\Delta(G)$ is the maximum degree.

E. Small Graphs (Exact Values)

Using ILP and theoretical bounds, the authors determined exact values or tight bounds for all connected graphs with $\leq 5$ vertices (excluding those reducible to smaller graphs). Notable results include:

• $K_4$: $HGP(K_4) = 7$.
• $C_4$ (Cycle): $HGP(C_4) = 4$.
• $K_5$: $HGP(K_5) = 9$.
• Various other graphs (e.g., House, Wheel, Hourglass) have bounds established (e.g., $5 \leq HGP \leq 7$).

4. Significance and Future Directions

• Theoretical Gap: The paper establishes that the "proper coloring" constraint fundamentally changes the hat guessing landscape, often allowing for significantly more colors than the classical game (e.g., doubling the capacity for cliques).
• Methodological Innovation: The connection between hat guessing strategies and perfect matchings in Boolean lattices provides a new combinatorial tool for the field.
• Open Problems: The authors propose several future research directions:
  1. Variations allowing multiple guesses per player.
  2. Determining if $HGP(G)$ is linearly bounded by the maximum degree $\Delta(G)$ (currently known to be quadratic).
  3. Exact values for cycles, wheels, and windmills.
  4. The asymptotic behavior of $HGP(B_{k,n})$ as $n \to \infty$ for fixed $k$.
  5. How the guessing number degrades as edges are removed from a complete graph.

In summary, this paper initiates the systematic study of hat guessing under proper coloring constraints, providing exact solutions for fundamental graph families (cliques, trees) and establishing a framework for analyzing more complex structures.