Name
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 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.tcs.2019.09.041 | Theoretical Computer Science |
Keywords | Field | DocType |
Matroid,Self-dual matroid,Impartial game,Sprague-Grundy function,Nim,Hypergraph Nim,JM hypergraph | Matroid,Graph,Discrete mathematics,Combinatorics,Hypergraph,Constraint graph,Mathematics | Journal |
Volume | ISSN | Citations |
799 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Endre Boros | 1 | 1779 | 155.63 |
| Vladimir Gurvich | 2 | 688 | 68.89 |
| Nhan Bao Ho | 3 | 8 | 3.74 |
| Kazuhisa Makino | 4 | 1088 | 102.74 |
| Peter Mursic | 5 | 0 | 0.68 |