Proper Hat-Guessing on Two-Spine Book Graphs

Abstract

In the proper variant of the classical hat-guessing game on a graph, an adversary properly colors the vertices from a palette of $q$ colors. Each vertex sees only its neighbors' colors and all vertices simultaneously guess their own color. The players win if at least one guess is correct. We study this game on the book graph $B_{k,n}=K_k\vee \overline{K_n}$, with $k$ mutually adjacent spine vertices and $n$ independent pages. We first give a coverability characterization valid for every fixed spine size. Write $\mathrm{HGP}(G)$ for the proper hat-guessing number of $G$. For a finite configuration $P$, let $\mathrm{supp}(P)$ denote the set of colors appearing in its tuples. Let $C_k$ be the minimum of $|P|+|\mathrm{supp}(P)|$ over all non-coverable finite configurations $P$ of proper $k$-tuples. We prove ${\sup }_{n\ge 1}\mathrm{HGP}(B_{k,n})=C_k$ and that $\mathrm{HGP}(B_{k,n})=C_k$ for all sufficiently large $n$. Thus, the asymptotic problem for every fixed $k$ reduces to a finite extremal invariant. In particular, coverability of two-spine configurations is equivalent to pseudoforestness, and we determine the associated extremal problem exactly: $C_2=11$, with precisely two types of extremal obstruction. Consequently, $\mathrm{HGP}(B_{2,n})\le 11$ for every $n$, with equality for all sufficiently large $n$; we give an explicit probabilistic estimate with a stabilization threshold of at most $4\times 10^8$. We also resolve the first previously open finite cases. An explicit seven-color construction with affine symmetry proves $\mathrm{HGP}(B_{2,3})=7$. A counting-rigidity argument establishes the linear upper bound $\mathrm{HGP}(B_{2,n})\le n+3$ for all $n\ge 4$, which together with monotonicity yields $\mathrm{HGP}(B_{2,4})=7$. Finally, a general box obstruction gives explicit uniform bounds on $C_k$.

20 pages, no figures; ancillary verification code included

Topics & keywords