Sprague-Grundy function of symmetric hypergraphs

DOI10.1016/J.JCTA.2019.02.006MaRDI QIDQ2424909zbMATH OpenOpenAlexFDO

Authors Endre Boros, Nhan Bao Ho, Kazuhisa Makino, Vladimir Gurvich, Peter Mursic

Publication date 25 June 2019

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

impartial gameSprague-Grundy functionsymmetric hypergraph\textsc{Nim}hypergraph \textsc{Nim}JM hypergraphJM formulatransversal-free hypergraph

Mathematics Subject Classification ID

2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65) Games involving graphs (91A43)

Abstract: We consider a generalization of the classical game of $NIM$ called hypergraph $NIM$. Given a hypergraph $cH$ on the ground set $V=1,ldots,n$ of $n$ piles of stones, two players alternate in choosing a hyperedge $HincH$ and strictly decreasing all piles $iinH$. The player who makes the last move is the winner. Recently it was shown that for many classes of hypergraphs the Sprague-Grundy function of the corresponding game is given by the formula introduced originally by Jenkyns and Mayberry (1980). In this paper we characterize symmetric hypergraphs for which the Sprague-Grundy function is described by the same formula.

Recommendations

• Sprague-Grundy function of matroids and related hypergraphs
• On the Sprague-Grundy function of extensions of proper \textsc{nim}
• scientific article; zbMATH DE number 6438474
• A Nim game played on graphs. II.
• On the Sprague-Grundy function of \textsc{Exact} \(k\)-\textsc{Nim}

Cites work

• scientific article; zbMATH DE number 5145315 (Why is no real title available?)
• scientific article; zbMATH DE number 2115805 (Why is no real title available?)
• scientific article; zbMATH DE number 3027208 (Why is no real title available?)
• On the Sprague-Grundy function of \textsc{Exact} \(k\)-\textsc{Nim}
• The skeleton of an impartial game and the nim-function of Moore's \(\text{Nim}_2\)

Cited in

(8)

• Computational Hardness of Multidimensional Subtraction Games
• On the Sprague-Grundy function of compound games
• On the Sprague-Grundy function of extensions of proper \textsc{nim}
• Sprague-Grundy function of matroids and related hypergraphs
• Slow \(K\)-\textsc{Nim}
• Bachet's game with lottery moves
• Impartial hypergraph games
• On the Sprague-Grundy function of \textsc{Exact} \(k\)-\textsc{Nim}

This page was built for publication: Sprague-Grundy function of symmetric hypergraphs

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