The Region Smoothing Swap Game
Allison Henrich Inga Johnson Jonah Ostroff


Machine learning the thermodynamic arrow of time
    Christopher Jarzynski
    December 30, 2023
================================================



We introduce a topological combinatorial game called the Region Smoothing Swap Game. The game is played on a game board derived from the connected shadow of a link diagram on a (possibly non-orientable) surface by smoothing at crossings. Moves in the game are performed on regions of the diagram and can switch the direction of certain crossings' smoothings. The players' goals relate to the connectedness of the diagram produced by game play.  



§ INTRODUCTION.

We introduce a new game, the Region Smoothing Swap Game, played on a game board derived from the connected shadow of a link diagram on a surface by smoothing at the diagram's crossings. This game can be viewed as a hybrid of the Link Smoothing Game, studied in <cit.>, and the Region Unknotting Game, studied in <cit.>. 

Suppose that D is a connected diagram of a link shadow on some (possibly non-orientable) surface S. That is, D is a connected link diagram where under- and over-strand information is unspecified at the crossings.  The unspecified crossings are called precrossings.  There are two possible options for smoothing each precrossing, shown in  Figure <ref>. When every precrossing of a link diagram D has been smoothed, the result is called a smoothed state or a smoothing of D. A  region smoothing swap is an operation that replaces one smoothed state by the state corresponding to changing the smoothings of all crossings on the boundary of a particular region in the link diagram. Figure <ref> shows a link together with two of its connected smoothed states. (The locations of the smoothed precrossings are indicated in the diagram by grey disks.) These two states are related by a single region smoothing swap, performed on the highlighted region.  




Game play begins on a connected smoothed state of link diagram D on a surface S. Two players take turns making moves. During game play, the smoothed diagram may become disconnected. A move consists of choosing a region in the link diagram and either performing a region smoothing swap at that region or keeping the state as-is.  The two players continue selecting regions and moving until all regions of D on S have been selected exactly once.  One player plays with the goal of producing a connected smoothed state when game play ends while the other player wants the game to end with a disconnected diagram.  We will call the player that wants to keep the diagram connected Player  C and the player whose goal is to disconnect the diagram Player D.  

An example game is played in Figure <ref>.  As each region is selected, the blue shading indicates that there is no change to the smoothings along the boundary of the region; the green shading indicates the adjacent smoothings are switched.





In this paper, our goal is to classify connected smoothed states of link shadows on various surfaces according to which player has a winning strategy in the Region Smoothing Swap Game.  In general, Player D typically has a strong advantage in this game. This is because an arbitrary choice of smoothings for the crossings in a link diagram is far more likely to result in a state that has two or more connected components than in a state with a single component. Indeed, some links have equivalence classes of smoothed states (where equivalence is generated by the smoothing swap operation) that don't contain any connected states.   So, we aim to identify link shadows with smoothed states on which Player C has a winning strategy. We always begin with a game board that is connected to ensure that we are in an equivalence class that contains at least one connected state. 

The example in Figure <ref> shows game play on a link diagram and a particular smoothed state where C moves first and C wins.  In fact, on this particular game board, C can always win if she moves first. To understand why Player C has a winning strategy, we first translate the game into a game on graphs to simplify our analysis.




§ GRAPHS AND THE REGION SMOOTHING SWAP GAME.


It can be useful to shift from viewing our game on a link diagram to viewing it as a game on the corresponding checkerboard graph. In this new setting, the regions of the smoothed link diagram are represented by either a vertex or a face of the graph.  The smoothed crossings are represented by the edges of the graph.  We see that the connectedness of a subset of edges in the graph captures the connectedness of the corresponding link diagram. 

Let's recall how to form the checkerboard graph corresponding to a link shadow.  We start by checkerboard coloring the shadow, then placing a vertex in each shaded region. Whenever two shaded regions are connected by a precrossing, we connect the associated vertices with an edge. The smoothing choice in the initial connected smoothed link shadow is indicated by either turning an edge “on" (pictured in bold) or “off" (pictured as dashed) depending on whether the two adjacent regions are joined or separated by the chosen smoothing.  For example, in Figure <ref>, we show the initial game board from Figure <ref> and the associated graph with edges on or off according to the choice of smoothing in the diagram. 



In the graph setting, the moves are made both on the regions of the graph and on the vertices of the graph, since both represent regions in the smoothed diagram game board.  So, when a vertex of the graph is selected, a player may (1) switch every incident edge—i.e., turn those edges that are on to off and those that are off to on—or (2) keep all incident edges as-is.  When a region of the graph is selected, a player may (1) switch every edge along its boundary—from on to off and off to on—or (2) keep all edges along the boundary as-is. The connectedness of the associated smoothed state corresponds to the requirement that the subgraph of edges that are on (shown in bold) is a tree that contains every vertex.

One benefit of the graph model of the Region Smoothing Swap Game is that the moves and the current state of the game can be easily represented using vectors with integer entries modulo 2.  To encode the current state of the game, we begin by enumerating each precrossing of the link shadow c_1, c_2, …, c_n and each region of the diagram r_1, r_2, …, r_k.  The associated graph will inherit the labeling of  c_1, c_2, …, c_n on its edges and the labeling r_1, r_2, …, r_k on its vertices and regions.  Observe that if the game board is assumed to lie on a sphere, then an Euler characteristic computation shows that n + 2 =k.


For a graph with n edges, the initial game state vector V_0=[v_1v_2…v_n] is defined by v_i=0 if the i^th edge is off, and  v_i=1 if the i^th edge is on, for 1≤ i ≤ n.  We use the notation V_j to denote the current game state vector after j moves have been made, for 1≤ j ≤ k. 

A move on a region or vertex in the graph is denoted by R_i = ϵ_i r_i  where r_i= [m_i,1 m_i,2… m_i,n]  is defined by m_i,j =1 if the edge c_j is in the boundary of region r_i or incident to vertex r_i, and  m_i,j =0 otherwise.  The value of ϵ_i is 1 or 0 depending on whether the player wants to switch all edge values or keep them as is.  The effect of the move R_i on game state vector V_j  is V_j+1 = V_j+R_i modulo 2.  


 As an example, the game play from Figure <ref> is represented with vectors in Figure <ref>.





By the commutativity of vector addition, the example in Figure <ref> shows that the entire game play can be captured by the following matrix equation.


    V_7   =V_0 + R_1 + R_2 + … + R_7 
       =V_0 + ϵ_1 r_1 + ϵ_2 r_2 + … + ϵ_7 r_7
       =V_0 + [ϵ_1 ϵ_2  …ϵ_7  ]  [ r_1
    r_2
    ⋮
    r_7]


In general, given a connected state vector V_0, our goal is to strategically pick, or as we shall see pair, the values ϵ_i for 1≤ i ≤ k so that the resulting state vector V_k from Equation <ref> represents a connected diagram. 


    V_k=V_0 + [ϵ_1 ϵ_2  …ϵ_k  ]  [ r_1
    r_2
    ⋮
    r_k]



Using this formalism, we can determine a general winning strategy for Player C for the example in Figure <ref>. Player C moves on r_5 first, keeping the region as-is. The remaining moves are determined by pairing moves on the following regions/vertices: r_1 and r_4,  r_2 and r_6, and r_3 and r_7.  In each pair, for any move made by D, there is a corresponding response move by C. In particular, Player C should respond to D's moves by choosing ϵ_1 ≠ϵ _4,  ϵ_2 ≠ϵ _6, and ϵ_3 = ϵ _7. Regardless of which vertices/regions Player D decides to move on and which signs for ϵ_i he chooses, C's response guarantees a connected diagram will result. Why is this? Consider the following matrix representing our game board.



    R=[ r_1; r_2; r_3; r_4; r_5; r_6; r_7;     ]
    =
    [ 1 1 0 1 1; 1 1 0 0 0; 1 0 1 1 0; 1 1 1 0 1; 0 0 1 1 0; 0 1 0 0 1; 0 0 1 1 1 ]


If Player C follows the strategy outlined above, the following are the eight possibilities for the vector E=[ϵ_1 ϵ_2  …ϵ_7  ]. The vectors represent the game play choices for Player D, with Player C's strategy entirely determined by D's choices. Note that the first vector in the list represents the game play shown in Figure <ref>.



    [ 1 1 1 0 0 0 1 ]
    [ 1 1 0 0 0 0 0 ]
    [ 1 0 1 0 0 1 1 ]
    [ 1 0 0 0 0 1 0 ]
    [ 0 1 1 1 0 0 1 ]
    [ 0 1 0 1 0 0 0 ]
    [ 0 0 1 1 0 1 1 ]
    [ 0 0 0 1 0 1 0 ]


Multiplying each of these E vectors by the R matrix in Equation <ref> and adding the vector V_0 =[1   1   0  0  1 ] gives the following eight vectors, the resulting values for V_7 that represent the states of the final game board.



    [ 0 1 0 1 1 ]
    [ 1 1 0 1 0 ]
    [ 1 1 0 1 0 ]
    [ 0 1 0 1 1 ]
    [ 0 1 1 0 1 ]
    [ 1 1 1 0 0 ]
    [ 1 1 1 0 0 ]
    [ 0 1 1 0 1 ]


As we can see, there are only four distinct ending game states that are possible if D has freedom to choose his own moves and C follows her strategy. The corresponding graphs are shown in Figure <ref>. Note that the subgraphs defined by the edges that are turned on are all spanning trees in the checkerboard graph. Thus, the strategy we described is indeed a winning strategy.





As we can see in Figure <ref>, there are many possible starting game boards that come from the twist knot.  In Figure <ref> we list all possible starting game graphs and group them according to their winning pairing strategy for C.  We will see that the pairs of moves described above remain quite useful on any starting game board.  In fact, the move pairing strategy can be used to prove the following theorem.

 If Player C moves first, then Player C has a winning strategy playing the Region Smoothing Swap Game on any connected game board associated to the 5-crossing twist knot shadow in Figure <ref>.




All connected starting game boards are shown in Figure <ref> and placed in one of three groups labeled (a), (b), and (c).  For each  group of starting game boards, we describe a winning strategy for C, assuming she moves first. We use the names of regions, r_i, and crossings, c_j, as given in Figure <ref>. In all groups, Player C's first move is on r_5 and she keeps the region as-is.  

For any starting board in group (a), we observe the following pairing strategy results in a win for C: ϵ_1 = ϵ _4,  ϵ_2 = ϵ _6, and ϵ_3 = ϵ _7.  In fact, after any single pair of moves ϵ_1 = ϵ _4,  ϵ_2 = ϵ _6, or ϵ_3 = ϵ _7, the mimicking strategy results in another game board within the list of Figure <ref>(a).  Thus, player C can defend the boards in group (a) so that after each move by D and corresponding reply by C, the board returns to a connected game board from group (a). 

For any starting board in group (b), we observe the following pairing strategy results in a win for C: ϵ_1 = ϵ _4,  ϵ_2 ≠ϵ _6, and ϵ_3 = ϵ _7.  Recall that, for any given set of moves, the order in which they are performed doesn't affect the outcome of the game. So, without loss of generality, we suppose the pair of moves  ϵ_2 ≠ϵ _6 are made first.  After these two moves are made on a game board from (b), the result is a game board from (a).  Then the remaining pairs of moves  ϵ_1 = ϵ _4 and ϵ_3 = ϵ _7 are applied to a game board from group (a), resulting in final board in group (a).

Lastly, as we saw in the more detailed linear algebraic argument above for the game board (c), the following pairing strategy results in a win for C: ϵ_1 ≠ϵ _4,  ϵ_2 ≠ϵ _6, and ϵ_3 = ϵ _7.  This pairing works regardless of the order in which the paired moves are applied.  When playing on the board in group (c), we note that if both pairs of moves ϵ_1 ≠ϵ _4 and ϵ_2 ≠ϵ _6 are completed first, then the result is a connected game board from (a).  The final pair of moves, ϵ_3 = ϵ _7, completes the game, producing a game board from (a).  


We observe the special role played by the game boards in group (a) of Figure <ref>.  Once the starting board graph was moved into a board of type (a) by Player C, then C had a winning defensive strategy.  




§ GAME PLAY ON THE SPHERE




Three nice examples of link shadows on the surface of a sphere on which Player C has a winning strategy come from the minimum crossing diagrams of the figure-eight knot, the trefoil, and the Borromean rings.  The figure-eight knot in particular gives a nice example of a game that Player C can win using a mimicking strategy.







 If Player C moves second, then Player C has a winning strategy playing the Region Smoothing Swap Game on any connected game board associated to the figure-eight knot shadow, as seen in Figure <ref>.



For this proof, we refer to the labeling of regions/vertices by r_i and crossings by c_i shown in Figure <ref>. The strategy Player C should follow to win is a mimicking strategy that pairs r_1 with r_2, r_3 with r_6, and r_4 with r_5. In other words, Player C should play so that ϵ_1=ϵ_2, ϵ_3=ϵ_6, and ϵ_4=ϵ_5. Following this strategy, given any game board from Figure <ref>, any pair of moves yields another game board from this collection. For instance, the second graph is obtainable from the first in the figure (and vice versa) by changing both r_1 and r_2; the third graph is obtainable from the first by changing r_4 and r_5; the fourth graph is obtainable from the first by changing both r_3 and r_6. 

Since each member of the collection is a winning state for Player C, she can always win.






 If Player C moves first, then Player C has a winning strategy playing the Region Smoothing Swap Game on any connected game board associated to the trefoil knot shadow in Figure <ref>.



For this proof, we refer to the labeling of regions/vertices using r_i and crossings with c_i as in Figure <ref>. Note that each connected game board is isomorphic to the one pictured, so it suffices to show that C has a winning strategy on this particular board. Let Player C move first on r_5, the region that contains the vertex of degree 2, keeping it as-is. For the remaining moves, we pair r_1 with r_2 and r_3 with r_4, and ensure that C follows a strategy such that ϵ_1=ϵ_2 while ϵ_3≠ϵ_4. So, for instance, if D moves on r_1 and performs a smoothing swap, then C performs a smoothing swap on r_2. Any moves on r_1 and r_2 that satisfy ϵ_1=ϵ_2 produce a graph that is identical to the starting graph. If, on the other hand, D moves on r_3 and leaves it as-is, then C should perform a smoothing swap on r_4. The resulting graph is isomorphic to the original graph. Any other pair of choices following the ϵ_3≠ϵ_4 strategy similarly produces an isomorphic graph.




  Suppose the Region Smoothing Swap Game is played on a connected starting board determined by the Borromean rings (pictured in Figure <ref>). Then Player C has a winning strategy when playing second.










  We begin with the standard representation of the Borromean rings and the connected game board shown in  Figure <ref>.  Notice that the associated graph—which we see is the complete graph on four vertices, K_4—contains two types of spanning trees: those that contain a vertex of degree three (shown in Figure <ref>(b)) and those that do not (shown in Figure <ref>(a)).  




For the graphs in Figure <ref>(a), a pairing strategy exists that results in a win for Player C playing second.  We describe this strategy using the notation defined in Figure <ref>. The defensive strategy for C is to respond to D's moves so that ϵ_1 =ϵ_2, ϵ_3=ϵ_4, ϵ_5=ϵ_6 and ϵ_7=ϵ_8.  

For each pair of moves, this mimicking strategy results in either changing every edge of K_4, when ϵ_2i =ϵ_2i-1 = 1, or changing none of the edges in the graph, when ϵ_2i =ϵ_2i-1 = 0.  For either of the two graphs in Figure <ref>(a), changing every edge of the graph produces the complementary subgraph of the checkerboard graph, which is the other graph from Figure <ref>(a); similarly for rotations and reflections of these graphs.  
 
For the graphs in (b), with a vertex of degree three, the mimicking strategy 
employed above does not work.  This strategy fails because the spanning trees in Figure <ref>(b) have complements that are not trees. Thus, the corresponding game board does not remain connected when moves such as ϵ_1 =ϵ_2=1 are made.   However, there is a shuffling of the pairings that does result in a win for C, namely ϵ_1=ϵ_7, ϵ_2 = ϵ_8, ϵ_3=ϵ_5, and ϵ_4=ϵ_6.  To see why this pairing works on either starting board from Figure <ref>(b), we first make the observation shown in Figure <ref>.  This figure shows the “star trek" graph—our name for  the graph in Figure <ref>(c)—that when added to either spanning tree that contains a vertex of degree three, yields the other spanning tree that contains a vertex of degree three.  Next, we note that the pairing ϵ_1=ϵ_7=1 results in adding the star trek graph to the connected starting graph.  The pairings ϵ_2 = ϵ_8, ϵ_3=ϵ_5, and ϵ_4=ϵ_6 also result in adding the star trek graph.  Therefore, this strategy always yields one of the connected spanning trees from Figure <ref>(b).
 








§ GAME PLAY ON THE KLEIN BOTTLE


So far, we've focused on game boards that live on the surface of a sphere, but some of the most interesting examples of games we've come across live on more complex surfaces. In particular, there exists an infinite family of game boards on the Klein bottle on which Player C has a winning strategy moving second. Before we describe our game board, let us recall one useful method of representing the Klein bottle: as a square with certain edges identified. In Figure <ref>, we see a popular representation of a Klein bottle (from Wikipedia) together with two possible polygonal representations, where edges are identified in pairs according to the orientations shown in the diagram. 



To picture a family of game boards on the Klein bottle that we call the “ladder family," we make use of the polygonal representation in Figure <ref>(b).   The two smallest members of this family, n=2 (the 2-step ladder) and n=3 (the 3-step ladder), are shown in Figure <ref>. We will refer to the horizontal graph edges as the “steps" of the ladder and the vertical edges as the  “rails." 



Unlike game play on the sphere, notice that it is possible for a smoothed state on the Klein bottle to be connected when the selected subgraph contains a cycle.    For example, the smoothed states in Figure <ref> are connected, but the graphs contain a cycle. Before further discussion of the game, we make an observation about special game boards, like those in Figure <ref>, that contain a cycle and always result in a connected smoothed state.

 If a subgraph of an n-step ladder graph on the Klein bottle contains exactly one horizontal step and exactly one rail at each height of the ladder,  then the smoothed state corresponding to this subgraph is connected. 
 



  We begin by making a quick observation regarding a simple subgraph of the n-step ladder graph. Then we prove the lemma for an arbitrary subgraph of the ladder that contains exactly one horizontal step and exactly one rail at each height.

The simple subgraph we consider first is the graph that contains the edges c_2, c_6, …, c_4n-2 and c_4n.  For the 3-step ladder, this graph is in Figure <ref>(a).   Observe that an ϵ-neighborhood of this graph within the Klein bottle is a Möbius strip, therefore the boundary of this ϵ-neighborhood consists of exactly one connected component.  Also notice that if smoothings were made around this graph they would trace out the boundary of the Möbius strip, thus one smoothed component would surround this graph.



To prove Lemma <ref>, we consider an arbitrary subgraph, G, of the ladder that contains exactly one horizontal step and exactly one rail at each height.  Since the graph contains exactly one step at each height, it cannot contain any vertices of degree four or zero.  Thus, G can only contain vertices of degree one, two, or three, as shown in Figure <ref>(b) & (c).    In particular, this implies that every vertex is included in G.

Since G contains a single rail at each height, each step of G will either have a rail on each end or two rails on one end of the step.  Thus, each step in G will either have both adjacent vertices of degree two or the step will have vertices of degree three and one.  We create an ϵ-neighborhood around the subgraph G' of G that contains every rail of G and each step of G whose adjacent vertices are both degree two.  Using an inductive argument starting at the bottom of the ladder, this subgraph can be viewed as a non-decreasing path up the ladder that connects up exactly once along the orientation-reversing identifications on the bottom and top of the polygon.  If the ϵ-neighborhood around the subgraph G' is glued along all orientation-preserving identifications within G', we get a connected rectangular strip with orientation-reversing gluings at each end.  Therefore, the ϵ-neighborhood around the subgraph G' is homeomorphic to a  Möbius strip.  As in the case of the simple graph, smoothings made in the diagram according to the edges in G' will result in a single boundary component around G'.  
  
To complete the argument for G, we notice that the only edges in G that are not in G' are the degree three and one vertices.  Thus, the graph G' is a connected strong deformation retract of G via the homotopy that continuously shrinks each step in G - G' towards the degree three vertex of that step.  This simple homotopy can be extended to the ϵ-neighborhood of G to prove that the ϵ-neighborhood of G' is a strong deformation retract of the ϵ-neighborhood of G. Following this homotopy on ϵ-neighborhoods, the smoothed state corresponding to the graph G is isotopic to the smoothed state corresponding to G'.  Therefore, the smoothed state corresponding to G is one connected component.
    

 If Player C moves second, then Player C has a winning strategy playing the Region Smoothing Swap Game on any game board associated to ladder family of links on the Klein bottle that contains exactly one horizontal step and exactly one rail at each height of the ladder (such as the game boards shown in Figure <ref>).  


 First, following Lemma <ref>, we note that our goal is to produce a subgraph of the checkerboard graph that contains exactly one rail and exactly one step at each height. Our starting configuration has this property. For the game on this graph, we follow a pairing strategy, setting ϵ_2i-1=ϵ_2i (see labelings in Figure <ref>) so Player C will mimic D's moves in these pairs. 

First of all, if Player D chooses ϵ_2i-1=0 or ϵ_2i=0 for some i, our mimicking strategy preserves the status quo—our graph is unaltered. Suppose, then, that Player D chooses ϵ_2i-1=1 or ϵ_2i=1 for some i. Then Player C will ensure ϵ_2i-1=ϵ_2i=1. In the diagram that results from this pair of moves, neither edge c_2i-1 or c_2i has been altered, but four edges have been switched, namely c_2i-3, c_2i-2, c_2i+1, and c_2i+2 (with subscripts mod 4n for the n-step ladder). If exactly one of the edges c_2i-3 and c_2i-2 was initially in the (bold) subgraph, then exactly one edge will be in the subgraph following the two moves. Similarly for c_2i+1 and c_2i+2. Thus, our desired “one edge at each height" property has been preserved, and the final game board is connected, by Lemma <ref>.




§ GAME PLAY ON THE CONNECT SUM OF TWO KLEIN BOTTLES


We've just seen an interesting game board on a Klein bottle, but why stop there? Are there game boards on more complex surfaces for which Player C has a winning strategy? We asked just this question and found an intriguing example on the connect sum of two Klein bottles. 


 The matrix corresponding to this example is as follows, where the ith column corresponds to c_i and the jth row corresponds to r_j.


    [ 1 1 1 0 0 0 1 0 1 0; 0 1 1 0 0 1 0 1 1 0; 0 0 0 1 1 0 1 1 0 1; 1 0 0 1 1 1 0 0 0 1; 0 0 1 0 0 1 0 1 1 1; 1 0 0 1 1 0 1 0 0 1; 1 1 0 1 1 1 0 0 0 0; 0 1 1 0 0 0 1 1 1 0;   ]






 If Player C moves second, then Player C has a winning strategy playing the Region Smoothing Swap Game on the graph on the connect sum of two Klein bottles shown in Figure <ref> when the starting game graph corresponds to any of the V_0 vectors below.  


    V_0^1=[ 0 1 0 0 1 1 0 0 1 1 ]
    
    V_0^2=[ 1 0 1 1 0 0 1 1 0 0 ]
    
    V_0^3=[ 0 1 0 0 1 0 1 0 1 1 ]
    
    V_0^4=[ 1 0 1 1 0 1 0 1 0 0 ]



 First, note that each of the four V_0^k vectors above corresponds to a connected game board. The reader may verify this fact by checking that an ϵ-neighborhood of each graph associated to a V_0^k has a single boundary component.  With this in mind, the strategy we describe for Player C is the following mimicking strategy: ϵ_1 =ϵ_3, ϵ_2 =ϵ_6, ϵ_4 =ϵ_8, and ϵ_5 =ϵ_7.

Note that, if a region smoothing swap is performed at both r_2 and r_6, the effect is that every c_i is swapped. The same is true for the pair r_4 and r_8. On the other hand, if a region smoothing swap is performed at both r_1 and r_3, all but c_6 and c_7 will be swapped. The same is true for r_5 and r_7. 

Now, if we begin with V_0^1 and all c_i's are swapped, the resulting vector is V_0^2 (and vice versa). Similarly for V_0^3 and V_0^4. Moreover, if all but c_6 and c_7 are swapped in V_0^1, the result is V_0^3. Similarly for V_0^2 and V_0^4. Together, this implies that if Player C follows a mimicking strategy in the pairs of r_i's designated above starting with any of the V_0^k vectors, any pair of moves produces a game board that is one of the four V_0^k's. Since these four vectors all represent connected game boards, Player C has a winning strategy.





§ RELATED RESULTS

As we discussed in the introduction, the Region Smoothing Swap Game is a variation on the Link Smoothing Game. In <cit.>, game boards were partially classified according to their outcome classes. Here, we provide a proof of completing the classification of Link Smoothing game boards.


 Let G be a connected, planar graph associated to a link shadow D.  If G represents a 𝒫-position game (i.e., a game in which the second player has a winning strategy), then G is composed of two edge-disjoint spanning trees.


To prove the theorem, we use a result of Nash-Williams <cit.> and separately Tutte <cit.>,  that gives a necessary and sufficient condition for a graph G to have two edge-disjoint spanning trees.  Before stating the conditions, though, we need some notation for a special graph associated to G that is defined in terms of a partition of the vertex set of G.  

Let G be a graph with vertex set V(G) and edge set E(G).  We denote the number of vertices and edges in G by |V(G)| and  |E(G)| respectively. For a partition P of V(G), we define E_P(G) as the set of edges that join vertices belonging to different members of P.  The graph G_P is defined as the graph with vertex set P and edge set E_P(G).  The Nash-Williams and Tutte result can now be stated as follows.

 A graph G has k edge-disjoint spanning trees if and only if 

    |E_P(G)| ≥ k (|P|-1)

for every partition P of  V(G).


  We begin with the supposition that G is a P-position graph for the link smoothing game. The definition of  P-position implies that the player with the goal to keep the diagram connected has a winning strategy when moving second on the given game board.  Such a winning strategy can only exist if there are an even number of edges in the graph G, else the player moving last would be the player with goal to disconnect and such a player can always disconnect the diagram on the final move.

By way of contradiction, we suppose that G does not consist of two edge disjoint spanning trees.  Then the result of Nash-Williams and Tutte implies the existence of a partition P of the vertices of G such that |E_P(G)| < 2(|P| -1).  Since the set E_P(G) is a subset of the edges of G and |P| is less than |V(G)|, we can conclude  |E(G)|≤ |E_P(G)| < 2(|P| -1) ≤ 2(|V(G)| -1).  Hence,  
    |E(G)| <  2(|V(G)| -1).
  By Theorem 6 in <cit.>, the previous inequality implies the graph represents an L-position diagram.  This contradicts our P-position supposition.






§ QUESTIONS FOR FURTHER RESEARCH


In doing research on the Region Smoothing Swap Game, our goal has been to find examples of link diagrams on surfaces on which Player C has a winning strategy. Since Player D tends to have an advantage in this game, finding such examples can be challenging. What is special about examples for which Player C has a winning strategy? An analysis akin to the one begun for the Link Smoothing Game in <cit.> which was completed in Section <ref> above would be interesting. Such an analysis will likely be more challenging to perform, however, in the setting of the Region Smoothing Swap Game on surfaces. It would be especially interesting to know more about the relationship between examples on which C can win and the surfaces on which these link smoothings live.

This topic provides a wealth of other open problems for those who are curious about variations on the Region Smoothing Swap Game. Just as with the Link Smoothing Game, the players' goals can be changed or the allowable moves can be modified to create a new game to study. We encourage our readers to invent and study their own games with knots, links, graphs, and surfaces!
 

 

§ ACKNOWLEDGEMENTS.
  The authors would like to thank the Simons Foundation (#426566, Allison Henrich) for their support of this research.

amsalpha
99

RUGS. Brown, F. Cabrera, R. Evans, G. Gibbs, A. Henrich and J. Kreinbihl, The region unknotting game. Math. Mag. 90 no. 5 (2017) 323-337.

link-smoothA. Henrich and I. Johnson, The link smoothing game. AKCE Int. J. Graphs Comb. 9 no. 2 (2012) 145-159.

NWC. St.J. A. Nash-Williams, Edge-Disjoint Spanning Trees of Finite Graphs. Journal London Math. Soc. 36 (1961) 445–450.

TutteW. T. Tutte, On the problem of decomposing a graph into n connected factors. Journal London Math. Soc. 142 (1961), 221–230.  




 