In a paper I am working on, a puzzling "game" has arisen. In this problem, I am trying to canonically enumerate all ways of traversing a specific labelled directed graph. However, this is not your typical graph traversal, as there are a few curiosities.
The Graph
We have within our set of vertices, four main vertices $A,B,C,D\in V$, which are connected by arcs in the following fashion.
As shown, for all $v\in\{A,B,C\}$ and $w\in\{A,B,C,D\}$, we have $(v,w)\in E$. Where $E$ is our set of arcs.
What is not shown is a countably infinite set of vertices $D_n\in V$ such that $(D,D_n)\in E$ for all $n\in\mathbb{N}_0$. Note that $D$ is distinct and not the same vertex as $D_n$ for any $n\in\mathbb{N}_0$.
When traversing our graph, there are a few rules.
-
Rule 1: We must start with one traveler at $A, B$ or $C$.
-
Rule 2: As standard, we may only traverse along the direction of the arcs and if we traverse to a sink, our travel comes to an end.
-
Rule 3: If possible, we can only traverse to $D$ if we are traversing from $A$, or if our traveler had been to $A$ at any point in the game.
-
Rule 4: If possible, we can only traverse to $D_n$ if our traveler had been at $A$ strictly more than $n$ times.
You may have noticed that in the figure above, $A$ and $B$ are coloured black, meanwhile $C$ and $D$ are coloured white. For lack of a better term, we will call some vertices split-vertices. The vertices which are filled in black and white are regular and split vertices, respectively. Note that $C$ and $D$ are the only split-vertices.
- Rule 5: When traversing from a split-vertex, our "traveler" splits into two travelers, not necessarily taking distinct paths. These two daughter travelers inherit the history of previously traversed vertices of their parent traveler, then keep track of their own histories of traversal individually. You can think of this as mitosis. The traveler does not split when traversing from a non-split-vertex.
As these are all the rules, you may notice that we are allowed to visit a vertex more than once, even consecutively.
The Game
Let's call a traversal that satisfies these rules, a game, and a traversal whose travelers all end at sinks after a finite number of iterations, a finite game.
One such game might look like this:
In this gif, I've only shown the vertices $D_n$ that are possible to be traversed to for at least one traveler (that is, $D_n$ is shown if some traveler has visited $A$ more than $n$ times). In this game, we may notate our traveler's journey as a tree.
$$
\begin{align*}
B\to B\to A\to A\to A\to &C\to A\to D\to D_0\\
&\downarrow\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \searrow\\
&D\to D_0\ \ \ \ \ \ \ \ \ \ \ D_1\\
&\ \searrow\\
&\ \ \ \ \ \ D_1\\
\end{align*}
$$
The last thing to note, is when a traveler splits into two distinct paths, we retain a sense of order of the two daughter travelers. That is to say, the following, game is distinct from the game above:
$$
\begin{align*}
B\to B\to A\to A\to A\to &C\to A\to \color{red}{D}\to \color{blue}{D_1}\\
&\downarrow\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \searrow\\
&D\to D_0\ \ \ \ \ \ \ \ \ \ \ \color{blue}{D_0}\\
&\ \searrow\\
&\ \ \ \ \ \ D_1\\
\end{align*}
$$
Although our traveler in this latter game visited all the same vertices at the same times, the order by which the two daughter travelers visited $\color{blue}{D_0}$ and $\color{blue}{D_1}$ after traversing from the split-vertex $\color{red}{D}$ is different from the first game. Hence, we will call these two games distinct.
The Problem
I would like to find a canonical enumeration of all distinct finite games.
Clearly, the number of unique finite games is countably infinite. Hence, there exists a bijection between all possible finite games, and the natural numbers. However, what is the most "natural" or "canonical" way of creating such a bijection? In other words, given a natural number $n$, what would "game $n$" look like? Perhaps it may be easier to go the other way around. As in, given a game, what natural number $n$ enumerates it uniquely?
As this is (at least to me) a difficult problem, I am happy to receive any and all insight on the problem, and I kindly thank everyone in advance for taking the time to think about this. This problem is very important to me as it has arisen naturally in my passionate studies of metamathematics.
If you feel so inclined to attempt a canonical enumeration, when the time lets me, I will be rewarding a bounty to best results, and will most definitely give credit in my paper, if so you'll let me. Although I struggle myself to find such an enumeration, the work I have done is that I was able to abstract-ify the metamathematical problem I was working on, from a relatively complex problem, into this simpler "graph traversal game enumeration", and it is from here, that I am stuck.
As perhaps evident by my lack of terminology, I am new to graph theory, so I lack many theorems, notations, and tools that would facilitate this idea. Do let me know of improvements to this question!
Best Answer
The most canonical bijection is probably the one generated by performing a BFS on the game, labelling games one by one each time we find one that is complete.
Here is another one, which can be efficiently computed :
Let $\phi : \mathbb{N}^2 \rightarrow \mathbb{N}$ be a bijection. (for example, $\phi(x,y) = (x+y)(x+y+1)/2 + y$).
Let $\psi^a_X$ be a bijection from the possible games starting from $X$ (where $X\in\{A,B,C\}$) and assuming the traveler went through $A$ $a$ times to $\mathbb{N}$. $\psi^a_{C1}$ is the bijection from the possible games starting from $C$, but without an initial split of travelers, to $\mathbb{N}$.
If $G$ is a game, $s(G)$ is the child tree of $G$ when removing the root, assuming there were no splitting (so the child is unique). $s_1(G)$ and $s_2(G)$ are the children of $G$ when splitting occur. We take care to use these functions only when they are well defined. We build the following recurrence:
$$\psi^a_A(G) = \begin{cases} \phi(m,n) \text{ if the traveler goes to } D \text{ then split in }D_m \text{ and } D_n\\ (a + 1)^2 + 3\psi^{a+1}_A(s(G)) \text{ if the traveler goes to } A \text{ next } \\ (a + 1)^2 + 1 + 3\psi^{a+1}_B(s(G)) \text{ if the traveler goes to } B \text{ next }\\ (a + 1)^2 + 2 + 3\psi^{a+1}_C(s(G)) \text{ if the traveler goes to } C \text{ next }\\ \end{cases}$$ $$\psi^a_B(G) = \begin{cases} \phi(m,n) \text{ if the traveler goes to } D \text{ then split in }D_m \text{ and } D_n\\ a^2 + 3\psi^a_A(s(G)) \text{ if the traveler goes to } A \text{ next }\\ a^2 + 1 + 3\psi^a_B(s(G)) \text{ if the traveler goes to } B \text{ next }\\ a^2 + 2 + 3\psi^a_C(s(G)) \text{ if the traveler goes to } C \text{ next }\\ \end{cases}$$ $$\psi^a_C(G) = \phi(\psi^a_{C1}(s_1(G)), \psi^a_{C1}(s_2(G)))$$ $$\psi^a_C1(G) = \begin{cases} \phi(m,n) \text{ if the traveler goes to } D \text{ then split in }D_m \text{ and } D_n\\ a^2 + 3\psi^a_A(s(G)) \text{ if the traveler goes to } A \text{ next }\\ a^2 + 1 + 3\psi^a_B(s(G)) \text{ if the traveler goes to } B \text{ next }\\ a^2 + 2 + 3\psi^a_C(s(G)) \text{ if the traveler goes to } C \text{ next }\\ \end{cases}$$
Then our bijection is defined by :
$$\psi(G) = \begin{cases} 3\psi^0_A(G) \text{ if the traveler start from } A\\ 1 + 3\psi^0_B(G) \text{ if the traveler start from } B\\ 2 + 3\psi^0_C(G) \text{ if the traveler start from } C\\ \end{cases}$$