Sprague-Grundy function of matroids and related hypergraphs

DOI10.1016/J.TCS.2019.09.041MaRDI QIDQ2333808zbMATH OpenOpenAlexWikidataFDO

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

Publication date 13 November 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

\textsc{Nim}hypergraph \textsc{Nim}impartial gameJM hypergraphmatroidself-dual matroidSprague-Grundy function

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) 2-person games (91A05) Games involving graphs (91A43) Combinatorial games (91A46)

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. 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.

Recommendations

• Sprague-Grundy function of symmetric hypergraphs
• scientific article; zbMATH DE number 3943834
• Spectral hypergraph theory of the adjacency hypermatrix and matroids
• scientific article; zbMATH DE number 5953778
• Hypergraphs and a functional equation of Bouwkamp and de Bruijn
• Strong Tutte Functions of Matroids and Graphs
• On the connectivity function of a matroid
• On some algorithmic aspects of hypergraphic matroids
• Grassmann-Plücker relations and matroids with coefficients

Cites work

• Characterizations of derived graphs
• Combinatorial game theory
• scientific article; zbMATH DE number 5145315 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 2115805 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• On generalized graphs
• On the Sprague-Grundy function of \textsc{Exact} \(k\)-\textsc{Nim}
• On the Sprague-Grundy function of extensions of proper \textsc{nim}
• Playing Nim on a simplicial complex
• SOME RESULTS ON TRANSVERSAL MATROIDS AND CONSTRUCTIONS FOR IDENTICALLY SELF-DUAL MATROIDS
• The skeleton of an impartial game and the nim-function of Moore's \(\text{Nim}_2\)

Cited in

(12)

• Playing Nim on a simplicial complex
• On the Sprague-Grundy function of extensions of proper \textsc{nim}
• Sprague-Grundy function of symmetric hypergraphs
• Computational Hardness of Multidimensional Subtraction Games
• Slow \(K\)-\textsc{Nim}
• Impartial hypergraph games
• On the Sprague-Grundy function of compound games
• Screw discrete dynamical systems and their applications to exact slow NIM
• On remoteness functions of k-NIM with k + 1 piles in normal and in Misère versions
• Computing remoteness functions of Moore, Wythoff, and Euclid's games
• Impartial games with decreasing Sprague-Grundy function and their hypergraph compound
• A deletion game on hypergraphs

This page was built for publication: Sprague-Grundy function of matroids and related hypergraphs

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