Hat guessing number of complete bipartite graphs
Open question: exact value of $HG(K_{n,n})$ · arXiv:1812.09752
Status open high confidence
The exact value of $HG(K_{n,n})$ remains unknown. The source paper established $\Omega(n^{1/2-o(1)}) = HG(K_{n,n}) \leq n+1$, with a substantial gap between the bounds. A 2021 follow-up by Alon and Chizewer (arXiv:2107.05995) studies the linear hat guessing number of complete multipartite graphs and restates the question as open, noting a positive answer seems plausible. No subsequent paper resolving the exact value was found in the indexed literature.
Cited literature (1)
-
Considers the linear hat guessing number of complete multipartite graphs and restates the question of the exact value of $HG(K_{n,n})$ as open, noting a positive answer seems plausible without proving it.
Reviewer notes. The gap between the lower bound $\Omega(n^{1/2-o(1)})$ and the upper bound $n+1$ remains unresolved. The internal reference 2409.01513 (Bradshaw, Mohar, Stacho on choosability) appears to be a corpus match on bipartite graphs generally, not on hat guessing numbers specifically, and was not verified as relevant.
Context
After establishing $\Omega\!\left(n^{\frac{1}{2}-o(1)}\right) = HG(K_{n,n}) \leq n+1$ by combining results of Gadouleau–Georgiou with Theorem 1.2, the authors note that the determination of the exact value of $HG(K_{n,n})$ is left as an interesting open question.
Notes. No labelled environment; stated as an open question in running prose immediately after Theorem 1.2.
Source paper
The hat guessing number of graphs
Noga Alon, Omri Ben-Eliezer, Chong Shangguan, Itzhak Tamo · 2020-01-15
https://arxiv.org/abs/1812.09752
PDF source