Constructing All Birthday 3 Games as Digraphs
Alexander Clow ✉ {}^{\textrm{\hrefmailto:[email protected]}\,\,\raisebox{-0.60275pt}{\lx@orcidlink{0000-0001-7568-9787}{\orcidlogo}}\,}, Alfie Davies ✉ {}^{\textrm{\hrefmailto:[email protected]}\,\,\raisebox{-0.60275pt}{\lx@orcidlink{0000-0002-4215-7343}{\orcidlogo}}\,}, Neil Anderson McKa · 2025
Read Constructing All Birthday 3 Games as Digraphs by Alexander Clow ✉ {}^{\textrm{\hrefmailto:[email protected]}\,\,\raisebox{-0.60275pt}{\lx@orcidlink{0000-0001-7568-9787}{\orcidlogo}}\,}, Alfie Davies ✉ {}^{\textrm{\hrefmailto:[email protected]}\,\,\raisebox{-0.60275pt}{\lx@orcidlink{0000-0002-4215-7343}{\orcidlogo}}\,}, Neil Anderson McKa (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06206.txt.
Introduction
Alexander Clow, Alfie Davies, and Neil Anderson McKay extend a game result in a 2025 combinatorics paper. A placement game on directed graphs was lately proved able to mirror any normal-play game. Games are classed by the day their values first appear, and past work built all day-two values on at most four graph points.
The team combined exhaustive and random computer searches to build all one thousand four hundred seventy-four day-three values. Each needed at most eight points, and the authors prove eight is sometimes required. They also improve bounds for day-four and day-five values. The work tightens the link between abstract game values and concrete graph constructions.
Catalog record
| CREATOR | Alexander Clow ✉ {}^{\textrm{\hrefmailto:[email protected]}\,\,\raisebox{-0.60275pt}{\lx@orcidlink{0000-0001-7568-9787}{\orcidlogo}}\,}, Alfie Davies ✉ {}^{\textrm{\hrefmailto:[email protected]}\,\,\raisebox{-0.60275pt}{\lx@orcidlink{0000-0002-4215-7343}{\orcidlogo}}\,}, Neil Anderson McKa |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-06206
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Constructing All Birthday 3 Games as Digraphs Alexander Clow ✉ {}^{\textrm{\hrefmailto:[email protected]}\,\,\raisebox{-0.60275pt}{\lx@orcidlink{0000-0001-7568-9787}{\orcidlogo}}\,}, Alfie Davies ✉ {}^{\textrm{\hrefmailto:[email protected]}\,\,\raisebox{-0.60275pt}{\lx@orcidlink{0000-0002-4215-7343}{\orcidlogo}}\,}, Neil Anderson McKay ✉ Abstract Recently, Clow and McKay proved that the digraph placement ruleset is universal for normal play: for all normal play combinatorial games X X , there is a digraph placement game G G with G = X G=X . Clow and McKay also showed that the 22 game values born by day 2 correspond to digraph placement games with at most 4 vertices. This bound is best possible. We extend this work using a combination of exhaustive and random searches to demonstrate all 1474 values born by day 3 correspond to digraph placement games on at most 8 8 vertices. We provide a combinatorial proof that this bound is best possible. We conclude by giving improved bounds on the number of vertices required to construct all game values born by days 4 and 5. 1 Introduction Let G=(V,E) be a directed graph and let \phi:V\to\{\text{blue},\text{red}\} be a (not necessarily proper) 2 -colouring of G . The digraph placement game played on (G,\phi) , which we write simply as G when \phi is clear from context, is described as follows: there are two players who play alternately, Left (blue) and Right (red); on her turn, Left chooses a blue vertex u and deletes N^{+}[u] from G ; on his turn, Right chooses a red vertex v and deletes N^{+}[v] from G . The digraph placement game resulting from a player choosing the vertex v (i.e. from the deletion of a vertex v and its out-neighbours) in a digraph placement game G is denoted G/v . When a sequence of vertices v_{1},\dots,v_{k} and their out-neighbours are deleted, we write the resulting game G/[v_{1},\dots,v_{k}] . If, at the beginning of a player’s turn, there are no vertices of that player’s colour remaining, then that player is unable to move and thus loses (as is the normal play convention). The set of all digraph placement games is the ruleset digraph placement . Figure 1: A digraph placement game equal to \mathord{\uparrow} (left) and another equal to \{2\mathrel{|}-2\} (right). Blue vertices are circles, red vertices are squares, and pairs of arcs (u,v),(v,u) are shown with a bolded edge. digraph placement is an example of a (normal play) combinatorial game theory ruleset as introduced by Conway in [ 7 ] . A normal play ruleset is one where there are two players who alternate turns, both players have perfect information about the game state and moves (the game involves no randomness), and if on a player’s turn they cannot move then they lose. For the rest of the paper we take game to mean an instance of a normal play ruleset. All games considered have finite numbers of options and end in finitely many turns, regardless of how the players move. It is customary to call the players of a game Left and Right. A game X can be written as X=\{X_{1},\dots,X_{k}\mathrel{|}Y_{1},\dots,Y_{t}\} where L(X)\coloneq\{X_{1},\dots,X_{k}\} is the set of all games Left can move to from X (i.e. Left’s options), and R(X)\coloneq\{Y_{1},\dots,Y_{t}\} is the analogous set for Right (i.e. Right’s options). It is a fundamental theorem of CGT that every game X has one of the following four outcomes: Left wins (playing first or second), Right wins (playing first or second), the first player wins, or the second player wins. digraph placement was introduced in 2024 by Clow and McKay [ 6 ] as a means of generalising some well-studied combinatorial game rulesets. Rulesets that were generalised include, but are not limited to, nim , col , snort , poset games , node kayles , arc kayles , domineering , and teetering towers . For more on these rulesets, see [ 2 , 3 , 5 , 13 ] . Like all of these rulesets, digraph placement is a placement game. Placement games are a special class of rulesets introduced by Brown et al. [ 4 ] . The digraph placement ruleset is a natural instance of a placement game played on digraphs, and it is interesting because, as Clow and McKay [ 6 ] demonstrated, it is the first known universal ruleset that is a placement game (ruleset). That is, for all normal play combinatorial games X , there is a digraph placement game G such that G=X . Two games X and Y are equal, written X=Y , if for all games Z , the outcome of X+Z is the same as the outcome of Y+Z . The equivalence classes under this notion of equality are called values . Addition here is the disjunctive sum of games (see [ 14 ] ). The birthday of a game X , denoted by b(X) , is the least (non-negative) integer strictly greater than the birthday of all the options of X . As we consider finite games, birthdays are well defined. For more on the basic theory of disjunctive sums and equality we refer the reader to Siegel’s textbook [ 14 ] . The birthday of a value is the minimum birthday of all games with that value. Note, b(X) is sometime called the formal birthday of X to distinguish the birthday of X from the birthday of the value of X . We consider the following problem: given a game X , what is the least integer f(X) such that there exists a digraph placement game G=X on f(X) vertices. We focus on bounding the function F(b) , which is the maximum of f(X) over all games X born by day b . Clow and McKay [ 6 ] proved F(2)=4 and posed determining F(3) as an open problem. The main contribution of this paper is proving F(3)=8 . Theorem 1.1 . For all games X born by day 3, there exists a digraph placement game G with at most 8 vertices such that G=X . Furthermore, there exists a game X with birthday 3 such that H\neq X for all digraph placement games H with at most 7 vertices. The paper is structured as follows. In Section 2 we explain our proof that F(3)\leq 8 which uses both exhaustive and random searches. The relevant output of these searches can be found in the ancillary files and acts as a certificate that F(3)\leq 8 . In Section 3 , we prove F(3)\geq 8 via a combinatorial argument, which demonstrates an explicit construction of a game requiring 8 vertices. In Section 4 we provide improved bounds on F(4) and F(5) . 2 Constructing all Day 3 Games Among its many uses, the nauty package [ 11 ] provides a suite of programs called gtools for generating non-isomorphic graphs. OEIS sequence A00059 [ 12 ] reports that there are 112\,282\,908\,928 non-isomorphic digraphs on 7 unlabelled vertices with loops allowed but not multiple arcs. Using gtools, we generated all of these 7 -vertex digraphs up to isomorphism, as well as all of those on at most 6 vertices. There is a bijection between the set of digraphs on n unlabelled vertices with loops allowed but not multiple arcs, and the set of (not necessarily properly) 2 -coloured digraphs on n unlabelled vertices with no loops and no multiple