Sprague-Grundy function of symmetric hypergraphs

DOI10.1016/J.JCTA.2019.02.006zbMATH Open1414.05191arXiv1804.01859OpenAlexW2962794564MaRDI QIDQ2424909FDOQ2424909

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)

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.

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

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}

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The skeleton of an impartial game and the nim-function of Moore's \(\text{Nim}_2\)
• Title not available (Why is that?)
• On the Sprague-Grundy function of \textsc{Exact} \(k\)-\textsc{Nim}

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)