Sprague–Grundy function of symmetric hypergraphs

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

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We consider a generalization of the classical game of NIM called hypergraph NIM. Given a hypergraph H on the ground set V={1,…,n} of n piles of stones, two players alternate in choosing a hyperedge H∈H and strictly decreasing all piles i∈H. The player who makes the last move is the winner. In 1980 Jenkyns and Mayberry obtained an explicit formula for the Sprague–Grundy function of the hypergraph NIM whose hypergraph contains as the hyperedges all proper subsets of V (that is, all except ∅ and V itself). Somewhat surprisingly, the same formula works for a very wide family of hypergraphs. In this paper we characterize symmetric hypergraphs in this family.

Original languageEnglish (US)
Pages (from-to)176-186
Number of pages11
JournalJournal of Combinatorial Theory. Series A
Volume165
DOIs
StatePublished - Jul 2019

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Hypergraph NIM
  • Impartial game
  • JM formula
  • JM hypergraph
  • NIM
  • Sprague–Grundy function
  • Symmetric hypergraph
  • Transversal-free hypergraph

Fingerprint

Dive into the research topics of 'Sprague–Grundy function of symmetric hypergraphs'. Together they form a unique fingerprint.

Cite this