The hat-guessing number is a graph invariant defined by Butler, Hajiaghayi, Kleinberg, and Leighton. We determine the hat-guessing number exactly for book graphs with sufficiently many pages, improving previously known lower bounds of He and Li and exactly matching an upper bound of Gadouleau. We prove that the hat-guessing number of $K_{3,3}$ is $3$, making this the first complete bipartite graph $K_{n,n}$ for which the hat-guessing number is known to be smaller than the upper bound of $n+1$ of Gadouleau and Georgiou. Finally, we determine the hat-guessing number of windmill graphs for most choices of parameters.
@article{10_37236_10098,
author = {Xiaoyu He and Yuzu Ido and Benjamin Przybocki},
title = {Hat guessing on books and windmills},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {1},
doi = {10.37236/10098},
zbl = {1481.05110},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10098/}
}
TY - JOUR
AU - Xiaoyu He
AU - Yuzu Ido
AU - Benjamin Przybocki
TI - Hat guessing on books and windmills
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/10098/
DO - 10.37236/10098
ID - 10_37236_10098
ER -
%0 Journal Article
%A Xiaoyu He
%A Yuzu Ido
%A Benjamin Przybocki
%T Hat guessing on books and windmills
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10098/
%R 10.37236/10098
%F 10_37236_10098
Xiaoyu He; Yuzu Ido; Benjamin Przybocki. Hat guessing on books and windmills. The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/10098
