Proper hat-guessing numbers of Kₙ minus one edge
Follow the latest progress by email.
In proper hat guessing, hat colors form a proper vertex coloring and each player guesses from the colors visible at neighboring vertices. For Kₙ with one edge removed, is the proper hat-guessing number 2n−3 or 2n−2?
Why it matters and what counts as progress
Why it matters: Exact endpoint cases test whether the general upper bound can be attained in this near-complete family.
What counts as progress: A winning strategy and matching obstruction determining a previously unsettled n, or a uniform construction or bound resolving the family.
How the problem developed
Adriaensen et al. Introduced the proper hat-guessing parameter and showed that for Kₙ−e its value is one of 2n−3 or 2n−2.
- 2 Sept 2026 · Exact value [2]
Matthew Protti Proved HGₚ(K₅−e)=8 using an explicit strategy and finite checks; this settles only the five-vertex instance.
- 3 Sept 2026 · Exact value [3]
Matthew Protti Proved HGₚ(K₆−e)=10 with a repaired permutation strategy and a finite verifier.
- 4 Sept 2026 · Exact value [4]
Matthew Protti Proved HGₚ(K₇−e)=12 using two explicit constructions and finite checks.
Matthew Protti Reported HGₚ(K₈−e)=14 with a finite strategy certificate checked on all proper fourteen-colourings.
AI contributions 4
AI-assisted certificate gives the proper hat-guessing number of K₈−e
The proper hat-guessing number of K₈−e is 14. A PGL(2,13)-equivariant fourteen-colour strategy uses 990 normalized twin decisions and a 48,510-edge residual-orbit matching; exhaustive checking covers all 138,378,240 proper colourings, and a general upper bound gives equality.
The Proper Hat-Guessing Number of K₇−e
The proper hat-guessing number of K7−e is 12. Either two disjoint S(5,6,12) completion designs or a sharply five-transitive orbit-map construction meets the twin-completion criterion; the general upper bound gives equality.
The Proper Hat-Guessing Number of K₆−e
The proper hat-guessing number of K6−e is 10. Two order-sensitive twin rules from a sharply four-transitive action on 11 points satisfy the coordinate-line criterion; Hall completion gives a winning ten-color strategy, matching the general upper bound.
The Proper Hat-Guessing Number of K₅−e
The proper hat-guessing number of K5−e is 8. An F₂³ construction and Hall-completion argument give a winning eight-color strategy, matching the prior general upper bound.
Sources
- Adriaensen et al., Hat Guessing with Proper Colorings
- Protti, K5−e result and exact verifier
- Protti, K6−e preprint and certificate
- Protti, K7−e preprint
- Protti, K₈−e theorem and certificate
- VibeMathed, The Proper Hat-Guessing Number of K₈−e
- Protti, AI contribution and review status
- Public draft and finite checks
- Adriaensen and coauthors, proper hat-guessing bound
- K7−e adversarial review and exact checks
- K7−e public review record
- K6−e public review record
- Protti, K5−e AI provenance
Website timeline
Publication dates and editorial changes.
Two AI-assisted constructions settle proper hat guessing for K7−e
AI-assisted construction settles proper hat guessing for K5−e
AI-assisted construction settles proper hat guessing for K6−e
AI-assisted certificate gives the proper hat-guessing number of K₈−e