The combinatorial game Nofil played on Steiner triple systems. Issue 1 (18th October 2021)

• Record Type: Journal Article
• Authors: Huggan, Melissa A.; Huntemann, Svenja; Stevens, Brett
• Is Part Of: Journal of combinatorial designs. Volume 30:Issue 1(2022)
• Page Start: 19
• Page End: 47
• Publication Date: 2021-10-18
• Subjects: combinatorial game theory -- computational complexity -- graph embedding -- Steiner triple systems; Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21809
• Languages: English
• ISSNs: 1063-8539

Abstract

Abstract: We introduce an impartial combinatorial game on Steiner triple systems called N ext O ne to F ill I s the L oser (N ofil ) . Players move alternately, choosing points of the triple system. If a player is forced to fill a block on their turn, they lose. By computing nim‐values, we determine optimal strategies for N ofil on all Steiner triple systems up to order 15 and a sampling for orders 19, 21 and 25. The game N ofil can be thought of in terms of play on a corresponding hypergraph which will become a graph during play. At that point N ofil is equivalent to playing the game N ode K ayles on the graph. We prove necessary conditions and sufficient conditions for a graph to reached playing N ofil . We conclude that the complexity of determining the outcome of the game N ofil on Steiner triple systems is PSPACE‐complete for randomized reductions.