Pith. sign in

REVIEW

Hat Guessing Numbers of Degenerate Graphs

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2003.04990 v1 pith:33YZOPBS submitted 2020-03-10 math.CO

Hat Guessing Numbers of Degenerate Graphs

classification math.CO
keywords textboundeddegeneratefarnikfunctiongraphguessingwhether
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Recently, Farnik asked whether the hat guessing number $\text{HG}(G)$ of a graph $G$ could be bounded as a function of its degeneracy $d$, and Bosek, Dudek, Farnik, Grytczuk and Mazur showed that $\text{HG}(G)\ge 2^d$ is possible. We show that for all $d\ge 1$ there exists a $d$-degenerate graph $G$ for which $\text{HG}(G) \ge 2^{2^{d-1}}$. We also give a new general method for obtaining upper bounds on $\text{HG}(G)$. The question of whether $\text{HG}(G)$ is bounded as a function of $d$ remains open.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.