Combinatorial Game Distributions of Steiner Systems

Abstract

The $\mathcal{P}$-position sets of some combinatorial games have special combinatorial structures. For example, the $\mathcal{P}$-position set of the hexad game, first investigated by Conway and Ryba, is the block set of the Steiner system $S(5,6,12)$ in the shuffle numbering, ${\mathcal{D}}_{\text{sh}}$. There were, however, few known games related to Steiner systems like the hexad game. For a given Steiner system, we construct a game whose $\mathcal{P}$-position set is its block set. By using constructed games, we obtain the following two results. First, we characterize ${\mathcal{D}}_{\text{sh}}$ among the 5040 isomorphic $S(5,6,12)$ with point set $\{0,1,\dots ,11\}$. For each $S(5,6,12)$, our construction produces a game whose $\mathcal{P}$-position set is its block set. From ${\mathcal{D}}_{\text{sh}}$, we obtain the hexad game, and this game is characterized as a unique game with the minimum number of positions among the obtained 5040 games. Second, we characterize projective Steiner triple systems by using game distributions. Here, the game distribution of a Steiner system $\mathcal{D}$ is the frequency distribution of the numbers of positions in games obtained from Steiner systems isomorphic to $\mathcal{D}$. We find that the game distribution of an $S(t,t+1,v)$ can be decomposed into symmetric components and that a Steiner triple system is projective if and only if its game distribution has a unique symmetric component.

19 pages, 8 figures