Hat guessing number graph parameter bounds

Problem 1.4 · arXiv:1812.09752

arXiv Problem high confidence— first stated 2020-01-15

Authors: Noga Alon, Omri Ben-Eliezer, Chong Shangguan, Itzhak Tamo

Status partial medium confidence

Problem 1.4 remains largely open. Part (i) (HG(G) bounded by a function of maximum degree) was already settled before the problem was stated via the Lovász Local Lemma. Parts (ii) and (iii) are unresolved: for part (ii), several papers have studied hat guessing numbers of degenerate and strongly degenerate graphs and shown that HG can grow at least as fast as $2^{2^{d-1}}$ for $d$-degenerate graphs, but whether an upper bound $f_2(d)$ exists is still open; for part (iii), no evidence of a minimum-degree lower bound was found.

Cited literature (1)

partial On the Hat Guessing Number of Graphs (2021)

Noga Alon, Jeremy Chizewer · arXiv preprint · arXiv:2107.05995

Restates Problem 1.4 and notes a positive answer seems plausible but does not prove it; constructs a planar graph with HG(G)=12 and analyzes random and complete multipartite graphs.

Reviewer notes. Web search found two further highly relevant papers not verified by WebFetch due to the 5-call cap: arXiv:2003.04990 (Xiaoyu He, 'Hat Guessing Numbers of Degenerate Graphs', Electronic Journal of Combinatorics 2020) showing HG(G) >= 2^{2^{d-1}} for some d-degenerate G and giving new upper-bound methods, and arXiv:2112.09619 ('Hat guessing numbers of strongly degenerate graphs', SIAM J. Discrete Math. ~2023); search summaries indicate that the general degeneracy-bound question of part (ii) remains open as of those papers. Part (iii) (minimum-degree lower bound) has no follow-up evidence in indexed literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Do there exist functions $f_i : \mathbb{N} \to \mathbb{N}$, $1 \leq i \leq 3$ such that (i) if the maximum degree of $G$ is $\Delta$, then $HG(G) \leq f_1(\Delta)$; (ii) if $G$ is $d$-degenerate, then $HG(G) \leq f_2(d)$; (iii) if the minimum degree of $G$ is $\delta$, then $HG(G) \geq f_3(\delta)$, and $f_3(\delta)$ tends to infinity when $\delta$ tends to infinity.

Context

The authors seek to understand how basic graph parameters control the hat guessing number. The existence of $f_1$ is already known via the Lovász Local Lemma ($HG(G) < e^\Delta$), but whether $f_2$ (degeneracy bound) or $f_3$ (minimum-degree lower bound) exist is unclear. Theorems 1.6 and 1.8 provide partial progress toward part (ii).

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