• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Sprague-Grundy function of matroids and related hypergraphs

Theoretical Computer Science. 2019. Vol. 799. P. 40-58.
Boros E., Gurvich V., Bao Ho N., Makino K., Mursic P.

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 this paper we give an explicit formula that describes the Sprague-Grundy function of hypergraph Nim for several classes of hypergraphs. In particular we characterize all 2-uniform hypergraphs (that is graphs) and all matroids for which the formula works. We show that all self-dual matroids are included in this class.