Poset Game Periodicity
Steven Byrnes · Zenodo (CERN European Organization for Nuclear Research) · 2003
Poset games are two-player impartial combinatorial games, with normal play convention. Starting with any poset, the players take turns picking an element of the poset, and removing that and all larger elements from the poset. Examples of poset games include Chomp, Nim, Hackendot, Subset-Takeaway, and others. We prove a general theorem about poset games, which we call the Poset Game Perioidicity Theorem: as a poset expands along two chains, positions of the associated poset games with any fixed g-value have a regular, periodic structure. We also prove several corollaries, including applications to Chomp, and results concerning the computational complexity of calculating g-values in poset games.