On a conjecture of Butler and Graham

DOI10.1007/S10623-012-9656-8MaRDI QIDQ369429zbMATH OpenOpenAlexWikidataFDO

Authors Tengyu Ma, Xiaoming Sun, Huacheng Yu

Publication date 24 September 2013

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.2027

zbMATH Keywords

characteristic functionhat guessing gamesmarking coordinate lines

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Cooperative games (91A12) Linear codes (general theory) (94B05)

Abstract: Motivated by a hat guessing problem proposed by Iwasawa cite{Iwasawa10}, Butler and Graham cite{Butler11} made the following conjecture on the existence of certain way of marking the {em coordinate lines} in $[k{]}^n$: there exists a way to mark one point on each {em coordinate line} in $[k{]}^n$, so that every point in $[k{]}^n$ is marked exactly $a$ or $b$ times as long as the parameters $(a,b,n,k)$ satisfies that there are non-negative integers $s$ and $t$ such that $s+t=k^n$ and $as+bt=n{k}^{n-1}$. In this paper we prove this conjecture for any prime number $k$. Moreover, we prove the conjecture for the case when $a=0$ for general $k$.

Recommendations

• A note on marking lines in \([k]^n\)
• The hat guessing number of graphs
• scientific article; zbMATH DE number 3544151
• Concerning a conjecture of R. L. Graham
• On the hat guessing number of graphs

Cites work

• A New Variation of Hat Guessing Games
• Hat Guessing Games
• Hypercube orientations with only two in-degrees
• On optimal strategies for a hat game on graphs
• Yet another hat game

Cited in

(7)

• On a conjecture of R. L. Graham
• A note on marking lines in \([k]^n\)
• Concerning a conjecture of R. L. Graham
• On a Conjecture of Butler
• On Butler's unimodality result
• On a Conjecture of Graham
• On a theorem of Graham

This page was built for publication: On a conjecture of Butler and Graham

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q369429)