\documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.59}{25(1)}{2018} \usepackage{amsmath, amsfonts,amssymb,amsthm,amstext,amscd} \usepackage{tikz} \usepackage{enumerate} \usepackage{xcolor} \usepackage{tkz-graph} \usetikzlibrary{decorations.pathmorphing} \tikzstyle{vertex}=[circle, draw, inner sep=0pt, minimum size=6pt] \newcommand{\vertex}{\node[vertex]} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{remark}[theorem]{Remark} \newtheorem{example}[theorem]{Example} \newtheorem{construction}[theorem]{Construction} \newtheorem{claim}[theorem]{Claim} \newtheorem{problem}[theorem]{Problem} %\textwidth 6in %\oddsidemargin.25in %\evensidemargin.25in %\parskip.05in \def \R {\mathbb{R}} \def \C {\mathbb{C}} \def \H {\mathbb{H}} \def \Z {\mathbb{Z}} \def \D {\mathbb{D}} \def \M {\mathcal M} \def \CN {\mathbb N} \def \CO {\mathcal O} \def \CR {\mathcal R} \def \CS {\mathcal S} \def \CW {\mathcal W} \def \rk {{\mbox rank}} \def \GF {{\mbox {GF}(2)}} \begin{document} \title{\bf Equivalence of edge bicolored graphs on surfaces} \author{Oliver T. Dasbach\thanks{Supported by NSF grant DMS-1317942.}\\ \small Department of Mathematics\\[-0.8ex] \small Louisiana State University \\[-0.8ex] \small Baton Rouge, LA 70803. U.S.A. \\ \small\tt dasbach@math.lsu.edu\\ \and Heather M. Russell \\ \small Department of Mathematics\\[-0.8ex] \small University of Richmond \\[-0.8ex] \small Richmond, VA 23173. U.S.A. \\ \small\tt hrussell@richmond.edu} \date{\dateline{Oct 11, 2017} {Feb 22, 2018}{Mar 16, 2018}\\ \small Mathematics Subject Classifications: 05C10, 57M25, 57M27, 05C50} \maketitle \begin{abstract} Consider the collection of edge bicolorings of a graph that are cellularly embedded on an orientable surface. In this work, we count the number of equivalence classes of such colorings under two relations: reversing colors around a face and reversing colors around a vertex. In the case of the plane, this is well studied, but for other surfaces, the computation is more subtle. While this question can be stated purely graph theoretically, it has interesting applications in knot theory. \end {abstract} %%% Paper Notation %\def \R {\mathbb{R}} %\def \C {\mathbb{C}} %\def \Z {\mathbb{Z}} \section{Introduction} Consider the following game for a connected, finite graph cellularly embedded (i.e. every face is a disk) on a compact orientable surface. Given a coloring of the edges by two colors, a finite number of two kinds of moves are allowed: (1) Reverse the colors of all the edges connected to some vertex, and (2) Reverse the colors of all the edges bounding some face. The goal is to find the number of equivalence classes of colorings under these moves. This problem arises in the context of knot theory. Given a checkerboard coloring of a link diagram lying on the sphere or more generally on a compact orientable surface, a checkerboard graph of the diagram has a natural edge coloring coming from crossing data. Our moves on this graph correspond exactly to region crossing changes which reverse all crossings bordering some (black or white) region of the diagram. Recent work of Ayaka Shimizu \cite{Shimizu:RegionChanges} shows that every knot diagram on a sphere can be transformed to one of the unknot by a sequence of region crossing changes. This is proven directly on the level of knot diagrams. Cheng Zhiyun and Gao Hongzhu \cite{ChengGao:RegionChanges} investigate region crossing changes for links of two components using graph theory and linear algebra. Cheng Zhiyun \cite{Cheng:RCCLinks} extends this work to links of $n$ components giving necessary and sufficient linking number conditions for a link to lie in the same equivalence class as the unlink. Every graph cellularly embedded on the sphere is the checkerboard graph of a knot or link, so the results of Shimizu and Cheng-Gao answer our question in the genus zero case. However, we will show that it also follows from previously known results. The number of equivalence classes is given by the absolute value $|T(-1,-1)|$ of the Tutte polynomial $T(x,y)$ at $(x,y)=(-1,-1)$ \cite{RosenstiehlRead:EdgeTripartition}. When a graph arises as a checkerboard graph of a diagram of a link $L$, the absolute value $|T(-1,-1)|$ equals the absolute value of the Jones polynomial of $L$ at $1$. The number of equivalence classes is given by $2^{c-1}$ where $c$ is the number of components of $L$. Moreover, representatives for the equivalence classes can be read off from $L$. For graphs on orientable surfaces of higher genus, one might hope that the equivalence classes are counted by the generalization of the Tutte polynomial to graphs on surfaces: the Bollob\'as-Riordan-Tutte (BRT) polynomial \cite{BR:BRTorientable, DFKLS:GraphsOnSurfaces}. We will show the BRT polynomial does indeed count the components of a link on a surface. However, it turns out that the problem of counting equivalence classes does not just depend on the genus of the surface and an evaluation of the BRT polynomial of the graph. Instead, the number of equivalence classes can be computed by finding the kernel of a certain map on homology. We start with a motivating example of a graph embedded on a torus in Section \ref{section:example}. Section \ref{section:medial graph} looks at the connection between graphs and links defining a subspace of the intersection of the cycle space of the graph and its dual whose dimension is measured by the Bollob\'as-Riordan-Tutte polynomial. In Section \ref{section:plane} we discuss the game for plane graphs, and Section \ref{section:surfaces} covers the case for graphs on orientable compact surfaces of arbitrary genus. We have given an intuitive description of the two moves of the game in this introduction. The precise description of the moves, given in the statement of Theorem \ref{Thm:PlaneGraphs}, is slightly more complicated in order to allow for possible loops and bridges in $G$. Note that Zaslavsky \cite{Zaslavsky:SignedGraphs} investigates a related problem for signed graphs called switching equivalence in which only one of our two moves is allowed. \section{Example} \label{section:example} \begin{figure} \begin {center} \begin{tikzpicture} \GraphInit[vstyle=Art] \draw [dashed] (0,0) -- (6,0) -- (6,6) -- (0,6) -- (0,0); \vertex (p1) at (2,2) {}; \vertex (p2) at (2,4) {}; \vertex (p3) at (4,2) {}; \vertex (p4) at (4,4) {}; \Edge [label=$2$, labelstyle=left](p1)(p2); \Edge [label=$3$, labelstyle=above](p2)(p4); \Edge [label=$4$, labelstyle=left](p4)(p3); \Edge [label=$1$, labelstyle=above](p3)(p1); \Edge [label=$7$, labelstyle=above](0,2)(p1); \Edge [label=$5$, labelstyle=left](p1)(2,0); \Edge [label=$8$, labelstyle=above](p2)(0,4); \Edge [label=$5$, labelstyle=left](p2)(2,6); \Edge [label=$6$, labelstyle=left](p3)(4,0); \Edge [label=$7$, labelstyle=above](p3)(6,2); \Edge [label=$6$, labelstyle=left](p4)(4,6); \Edge [label=$8$, labelstyle=above](p4)(6,4); \Edge [label=$9$, labelstyle={above=6pt}](p1)(p4); \end{tikzpicture} \caption{Graph with four vertices and nine edges on a torus \label{fig:TicTacToeGraph}} \end{center} \end{figure} We discuss the mathematics of the game in an example. Figure \ref{fig:TicTacToeGraph} shows a graph $G=(V,E)$ with four vertices and eight edges embedded on a plane model of a torus. The torus is obtained by identifying the top with the bottom dotted edge of the square and the left with the right dotted edge. We translate the game into a problem of determining the dimension of a vector space over $\GF = \mathbb{Z}/2\mathbb{Z}$, the field with two elements $0$ and $1$. We fix an ordering of the edges of $G$ (and hence $G^*$) and use it implicitly. Assigning, say, $0$ to the color blue and $1$ to the color red, we see that bicolorings of $G$ are in bijection with vectors in $\GF^{|E|}$. Given some coloring vector $w\in \GF^{|E|}$, switching colors around a vertex of $G$ corresponds to adding a row of the incidence matrix of $G$ to $w$. The row vectors of the incidence matrix form a subspace $U$ of $\GF^{|E|}$ of dimension $|V|-1$ (see e.g. \cite{GodsilRoyle:AlgebraicGraphTheory}, Lemma 14.15.1). This subspace $U$ is called the cocycle space (or cut space) of $G$. For our example graph $G$ in Figure \ref{fig:TicTacToeGraph}, the incidence matrix $\mathcal I$ over $\GF$ is $${\mathcal I}=\left( \begin{array}{ccccccccc} 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0\\ \end{array} \right). $$ Since the graph has $|V|=4$ vertices the rank over $\GF$ is $|V|-1=3$. Any row is linearly dependent on the other rows, so the cocycle space $U$ is the subspace of $\GF^9$ generated by the first three rows of $\mathcal I$. The graph has five regions in its embedding, thus the dual graph $G^* = (V^*,E^*)$ has five vertices. The incidence matrix of the dual graph in this case is $${\mathcal I}^*=\left( \begin{array}{cccccccccc} 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ \end{array} \right). $$ The edges in $E$ and $E^*$ are in $1$-$1$ correspondence, and thus $|E|=|E^*|$. Here, and throughout our discussion, we pick the same ordering on $E$ and $E^*$ and use this when considering rows of both ${\mathcal{I}}$ and ${\mathcal{I}}^*$ as vectors in $\GF^{|E|}$. Adding rows of ${\mathcal I}^*$ to a coloring vector corresponds to switching colors around faces of the graph. Since the dual graph has five vertices, its cocycle space $U^*$ is $4$-dimensional. Any vertex and face in $G$ are incident to either two or zero common edges. This means $U^*$ is orthogonal to $U$, and thus $U^* \subseteq U^{\perp}.$ The subspace $U^{\perp} \subseteq \GF^{|E|}$ is called the cycle space (or flow space) of $G$. The dimensions of the cycle and cocycle spaces are related (e.g. \cite{GodsilRoyle:AlgebraicGraphTheory}) by the formula $$\dim U + \dim U^{\perp} = |E|.$$ The intersection $U \cap U^{\perp}$ is called the bicycle space of $G$. Its dimension $b$ is given by the Tutte polynomial at $(-1,-1)$ \cite{RosenstiehlRead:EdgeTripartition}: $$|T_G(-1,-1)|=2^b.$$ (We give a formula for the Tutte polynomial via a specialization of the Bollob\'as-Riordan-Tutte polynomial in the next section.) For our problem, we are interested in the dimension of $\GF^{9}/(U + U^*)$. Since $$\dim (U+U^*)= \dim U + \dim U^*-\dim U \cap U^*$$ we need to determine the dimension of $U \cap U^*$. We know that $U^* \subseteq U^{\perp}$, and thus the space $U \cap U^*$ is a subspace of the bicycle space. For our example in Figure \ref{fig:TicTacToeGraph}, the dimension of $U+U^*$ turns out to be $6$, and hence the dimension of $U \cap U^*$ is $1$. Since the codimension of $U+U^*$ in $\GF^9$ is $3$ there are $2^3$ different equivalence classes for our game. The construction can be interpreted within the setting of the balanced overlaid Tait (BOT) graph (e.g. \cite{CDR:Dimers,RussellEtAl:DehnColoring}): For the graph $G$ and its dual graph $G^*$ chose a vertex $v_0$ in $G$ and an adjacent vertex $v_0^*$ in $G^*$. Let $\mathcal I$ and $\mathcal I^*$ be the incidence matrices of graph $G$ and its dual over $\GF$. In the matrices we remove a row corresponding to $v_0$ in $G$ and to $v_0^*$ in $G^*$. We form a new matrix $A$ by combining the rows of $\mathcal I$ and $\mathcal I^*$ excluding the two removed rows. This matrix can be interpreted in a different way. If we lay $G$ and $G^*$ on top of each other by inserting a new vertex for every intersection of an edge in $G$ with the corresponding edge in $G^*$, this forms the BOT graph. We remove $v_0$ and $v_0^*$ and all of its adjacent edges. By construction we obtain a tripartite graph. Figure \ref{fig:BOT} gives an example. The matrix $A$ describes the adjacencies of vertices in the BOT graph among the bipartition of the vertices. \begin{figure}[h] \begin {center} \begin{tikzpicture}[scale=0.4] \vertex[fill=red] (p1) at (0,0) {}; \vertex[fill=red] (p2) at (4,0) {}; \vertex[fill=red] (p3) at (4,4) {}; \vertex[fill=red] (p4) at (0,4) {}; \Edges (p1,p2,p3,p4,p1); \Edge (p1)(p3); \end{tikzpicture} \hspace {1cm} \begin{tikzpicture}[scale=0.4] \vertex[fill=blue] (q1) at (3,1) {}; \vertex[fill=blue] (q2) at (1,3) {}; \vertex[fill=blue] (q3) at (3,5) {}; \Edge (q1)(q2); \Edge[style={bend left}](q2)(q3); \Edge (q2)(q3); \Edge[style={bend left}](q2)(q3) \Edge (q1)(q3) \Edge[style={bend right}](q1)(q3) \end{tikzpicture} \hspace {1cm} \begin{tikzpicture}[scale=0.4] \vertex[fill=red] (p1) at (0,0) {}; \vertex[fill=red] (p2) at (4,0) {}; \vertex[fill=red] (p3) at (4,4) {}; \vertex[fill=blue] (q1) at (2,1){}; \vertex[fill=blue] (q2) at (2,3){}; \vertex[fill=green] (r1) at (2,0){}; \vertex[fill=green] (r2) at (4,1){}; \vertex[fill=green] (r3) at (2,2){}; \vertex[fill=green] (r4) at (2,4){}; \vertex[fill=green] (r5) at (0,2){}; \Edges(p1, r1, p2, r2, p3, r4, q2, r3, q1); \Edges(r1, q1, r2); \Edges(p1,r3,p3); \Edges(p1,r5,q2); \end{tikzpicture} \caption{Graph $G$, its dual graph, and the overlay graph with two vertices and their adjacent edges removed. \label{fig:BOT}} \end{center} \end{figure} \section{The components of the medial graph of a graph on a surface} \label{section:medial graph} Consider a link projection on an orientable surface such that all faces of the projection are disks and one can color the faces of the projection with black and white in a checkerboard fashion. Two dual checkerboard graphs $G_b$ and $G_w$ that are embedded on the surface are constructed as follows: The vertices of $G_b$ (resp. $G_w$) correspond to the faces colored in black (resp. white), and two vertices are connected by an edge if and only if the corresponding faces are adjacent to a common crossing of the link projection: \begin{center} \begin{equation} \label{CrossingToEdge} \begin{tikzpicture}[baseline=25] \draw (0,0)--(2,2); \draw (1,1.8) node{b}; \draw (1,0.2) node{b}; \draw (1.8,1) node{w}; \draw (0.2,1) node{w}; \draw (2,0)--(1.1,0.9); \draw (0.90, 1.1)--(0,2); \begin{scope}[xshift=2.6cm, baseline=25.4] \draw [->, line join=round, decorate, decoration={ zigzag, segment length=4, amplitude=.9,post=lineto, post length=2pt }] (0,1) -- (1,1); \end{scope} \begin {scope}[xshift=3.4cm, baseline = 25] \vertex [label={$b$}](p1) at (1,1.8) {}; \vertex [label={[yshift=-0.8cm] $b$}](p2) at (1,0.2) {}; \Edge(p1)(p2); \draw (p1) -- (p2); \end{scope} \end{tikzpicture} \end{equation} \end{center} Neither $G_b$ nor $G_w$ can be used to recover the original link diagram since crossing changes do not change the two checkerboard graphs. However, for any graph $G$ with a cellular embedding on a surface one can construct a unique alternating link diagram $D_L$ such that $G$ is one of the checkerboard graphs by reversing the arrow in (\ref{CrossingToEdge}). The link $L$ is called a {\it medial link} of $G$, and its underlying $4$-valent graph is called the {\it medial graph} of $G$. Since the medial graph comes from flattening a link diagram, it can be viewed as a collection of closed curves on the surface. In this sense, the number of components of the medial graph is well-defined. Figure \ref{Medial Graph} gives an example where the number of components is $3$. \begin{figure}[h] \begin {center} \begin{tikzpicture} [thick,scale = .6] \vertex (p1) at (0,0){}; \vertex (p2) at (2,-1.5){}; \vertex (p3) at (2,1.5){}; \vertex (p4) at (4,0){}; \vertex (p5) at (6,0){}; \Edges (p1, p2,p3,p1); \Edges (p2, p4, p3); \Edge[style={bend right}](p4)(p5); \Edge[style={bend right}](p5)(p4) \begin{scope}[xshift = 9cm,yshift=-2cm, rounded corners = 3mm ] \draw (.9,.9) -- (0,0) -- (-1,0) -- (-1,4) -- (0,4) -- (1.9,2.1); \draw (2.9,2.9) -- (1.1,1.1); \draw (.9,2.9) -- (0.5,2.5) --(.5,1.5) -- (1.5,.5) -- (2.5,.5) -- (2.9,.9); \draw (3.1,1.1) -- (3.5,1.5) -- (3.5,2.5) -- (2.5,3.5) -- (1.5,3.5) -- (1.1,3.1); \draw (2.1,1.9) -- (3.5,.5) -- (4.5,.5) -- (4.9,.9); \draw (5.1,1.1) -- (5.5,1.5) -- (5.5,2.5) -- (4.5,3.5) -- (3.5,3.5) -- (3.1,3.1); \draw (5.1,3.1) -- (6,4) -- (7,4) -- (7,0) -- (6,0) -- (4.5,1.5) -- (4.5,2.5) -- (4.9,2.9); \end{scope} \end{tikzpicture} \end{center} \caption{A graph $G$ and the alternating diagram $D_L$ of a link with three components} \label{Medial Graph} \end{figure} \subsection{The Bollob\'as-Riordan-Tutte polynomial} Recall that, for a graph which is cellularly embedded on the sphere, the Tutte polynomial counts the number of components of the medial graph, and this data provides an easy way to count equivalence classes in our game for graphs on spheres. Our goal in this subsection is to show the Bollob\'as-Riordan-Tutte (BRT) polynomial \cite{BR:BRTorientable} for graphs with a cellular embedding on an orientable surface counts the number of components in the medial graph. We will later show that the number of equivalence classes in our game on arbitrary surfaces unfortunately does not have a simple dependency on this count. We begin with a definition of the BRT polynomial. Let $v(G), e(G), f(G)$, and $k(G)$ be the number of vertices, edges, faces and connected components of a graph embedded on a surface. The nullity $n(G)$ is $n(G) = e(G)-v(G)+k(G)$, and the genus $g(G)$ is $$g(G)=\frac{2 k(G)-v(G)+e(G)-f(G)} 2.$$ The BRT polynomial $BRT_G(x,y,z)$ is defined as: $$BRT_G(x,y,z)= \sum_{H \subseteq G} x^{k(H)-k(G)} y^{n(H)} z^{g(H)}.$$ Here the sum is over all spanning subgraphs of $G$. We slightly departed from the original definition by changing the variable from $x$ to $x+1$. The relation to the Tutte polynomial is given \cite{BR:BRTorientable} by $$BRT_G(x-1,y-1,1) = T_G(x,y).$$ Chmutov and Pak \cite{ChmutovPak:BollobasRiordan} showed that the Kauffman bracket of an alternating virtual link can be interpreted as an evaluation of the BRT polynomial. In \cite{DFKLS:GraphsOnSurfaces} it is shown that the Jones polynomial of an arbitrary link can be seen as an evaluation of the BRT polynomial of a graph embedded on a surface that can be constructed from a plane diagram of the link. We will use those relations between link diagrams and the BRT polynomial below. For plane graphs it is known that the Tutte polynomial determines the number of components of the medial graph (e.g. \cite{GodsilRoyle:AlgebraicGraphTheory}). For a graph on an arbitrary orientable surface we need the extension to the BRT polynomial: \begin{theorem} \label{Thm:ComponentsMedialGraph} Consider $BRT_G(x,y,z)$ for a graph embedded on an orientable surface $\Sigma$. Construct the link diagram $D_L$ on the surface $\Sigma$ with checkerboard graph $G$ by reversing the arrow in (\ref{CrossingToEdge}). Then the number of components $c$ of $D_L$ is counted by the BRT polynomial as: $$|BRT_G(-2,-2,1/4)| = 2^{c-1}.$$ \end{theorem} \begin{proof} As in \cite{ChmutovPak:BollobasRiordan, DFKLS:GraphsOnSurfaces, DFKLS:DDD} we consider the specialization of the BRT polynomial given by $(x,y,z)=(-A^4-1, -1-A^{-4}, 1/(-A^2-A^{-2})^2).$ Recall the slight change of variables from $x$ to $x+1$ from the original definition of the BRT polynomial. This defines a Laurent polynomial $\langle D_L \rangle$ in $A$ and $A^{-1}$ by $$A^{-e(G)} \langle D_L \rangle = A^{2-2 v(G)} BRT_G(-A^4-1, -1-A^{-4}, 1/(-A^2-A^{-2})^2).$$ Thus, $$\langle D_L \rangle = \sum_{H \subseteq G} A^{e(G)-2 e(H)} (-A^2-A^{-2})^{f(H)-1}.$$ Locally with respect to the link diagram $D_L$ the Laurent polynomial $\langle D_L \rangle$ has the following property \cite{ChmutovPak:BollobasRiordan}: \begin{equation} \label{skein relation} \left \langle \begin{tikzpicture}[scale=0.4, baseline=9.0] \draw (0,0)--(2,2); \draw (2,0)--(1.1,0.9); \draw (0,2)--(0.9,1.1); \end{tikzpicture} \right \rangle= A \left \langle \begin{tikzpicture}[scale=0.4, baseline=9.0] \draw (0,0)to [bend right] (0,2); \draw (2,0) to [bend left] (2,2); \end{tikzpicture} \right \rangle+ A^{-1} \left \langle \begin{tikzpicture}[scale=0.4, baseline=9.0] \draw (0,0)to [bend left] (2,0); \draw (0,2) to [bend right] (2,2); \end{tikzpicture} \right \rangle, \end{equation} and $$\left \langle \begin{tikzpicture}[scale=0.4, baseline=-2.0] \draw (0,0) circle (1cm); \end{tikzpicture} \right \rangle=1. $$ We are interested in its value at $A=1$. We will show that if $L$ has $c$ components, then $\langle D_L \rangle_{A=1} = (-1)^{\nu} (-2)^{c-1},$ where $\nu$ is the number of crossings in the diagram $D_L$. In particular this holds for a diagram of the unknot without crossings. By induction on the number of crossings, if the two strands in the link diagram on the left-hand side of Equation (\ref{skein relation}) are on two different components of the link, then the two links on the right-hand side have one component less, and we verify: $$(-1)^{\nu} (-2)^{c-1}=(-1)^{\nu-1} \left ( (-2)^{c-2} + (-2)^{c-2} \right ).$$ If the two strands on the left-hand side of Equation (\ref{skein relation}) are on the same component of the link then one of the links on the right-handside has one component more, while the other one has the same number of components. This verifies: \[(-1)^{\nu} (-2)^{c-1}=(-1)^{\nu-1} \left ( (-2)^{c-1} + (-2)^{c} \right ).\qedhere\] \end{proof} \subsection{Example} The graph on the torus in Figure \ref{fig:TicTacToeGraph} has BRT polynomial \cite{vAult:BRTSage}: \begin{eqnarray*} BRT_G(x,y,z)=&x^3+4 x^2 y+9 x^2+6 x y^2+36 x y+32 x+2 y^4+16 y^3+60 y^2+112 y+48\\ & + \left(2 x y^3+8 x y^2+y^6+9 y^5+34 y^4+68 y^3+64 y^2\right) z \end{eqnarray*} We have $BRT_G(-2,-2,1/4)=-4$. Therefore, by Theorem \ref{Thm:ComponentsMedialGraph} the medial graph has $3$ components. \subsection{Components of the medial graph as cycles} \label{Space P} Each cycle in $G$ (or $G^*$) corresponds to a unique vector in $\GF^{|E|}$. Given such a cycle, the associated vector has a 1 in the position of each edge occurring an odd number of times in the cycle and zeroes elsewhere. Similarly, each subset of $E$ (or $E^*$) will be identified with the vector in $\GF^{|E|}$ having a 1 in the position of an edge if and only if it is present in the subset. Using these two constructions, we conflate the notions of cycles in $G$ and $G^*$ and subsets of $E$ and $E^*$ with their corresponding vectors in $\GF^{|E|}$. Let $k_1, \dots, k_c$ be the components of the medial graph for $G$. Since the medial graph of a graph $G$ equals the medial graph of its dual $G^*$, the edges intersected when tracing along a component $k_i$ of the medial graph form a cycle $v_i$ in both $G$ and $G^*$. Note that an edge could be intersected by a component twice, and in that case, the edge would appear twice in the cycle (and thus would have a 0 in that edge's entry of $v_i\in \GF^{|E|}$). Then for $i=1,\ldots, c$, we conclude $v_i \in U^{\perp} \cap (U^{*})^{\perp},$ where $U^{\perp}$ is the cycle space of $G$ and $(U^*)^{\perp}$ is the cycle space of $G^*$. The following is a straightforward generalization from results for plane graphs (see Section 17.3. of \cite{GodsilRoyle:AlgebraicGraphTheory}) : \begin{lemma} \label{Generators for P} Let $G=(V,E)$ be a connected graph embedded on an oriented surface. Let $k_1, \dots, k_c$ be the components of the medial graph, with vectors $v_1, \dots, v_c$ as above. Then \begin{enumerate}[(i)] \item Each edge of $G$ occurs in an even number of the vectors $v_i$, and no proper subset of the set $\{ v_1, \dots, v_c \}$ covers every edge in $G$ an even number of times. \item Each vector is the sum of all of the other vectors. \item The subspace $\mathcal P$ of $\GF^{|E|}$ generated by $\{ v_1, \dots, v_c \}$ has dimension $c-1$. \end{enumerate} \end{lemma} \section{Plane graphs} \label{section:plane} The linear algebra discussed in the previous sections is particularly nice for graphs embedded on spheres (i.e. plane graphs). Since every cycle in such a graph bounds a disk, it follows that $U^*=U^{\perp}$, and thus $U \cap U^*=U\cap U^{\perp}$. In other words, for graphs on spheres $U \cap U^*$ is the bicycle space. The following theorem gives an easy way to count the number of equivalence classes in our game for graphs on spheres. The two moves on bicolorings described here are more complicated than the ones given in the introduction. This is due to the fact that we allow our graphs to have loops and bridges. \begin{theorem} \label{Thm:PlaneGraphs} Let $G=(V,E)$ be a finite, connected plane graph. The following two moves define an equivalence relation on the set of edge bicolorings of $G$. Two colorings are equivalent if and only if one can be obtained from the other by a finite sequence of the following two moves: \begin{enumerate} \item Around a vertex, switch the colors of all edges with exactly one endpoint at that vertex (i.e. all non-loops adjacent to the vertex). \item Around a face of the embedded graph, switch all colors of the edges appearing exactly once in the boundary cycle of the face. \end{enumerate} Then the absolute value of the Tutte polynomial evaluation $|T(-1,-1)|$ yields the number of equivalence classes of colorings. \end{theorem} \begin{proof} As in the example in Section \ref{section:example}, the problem reduces to computing the intersection of the cycle and the cocycle spaces of $G$. Using Euler characteristic, the number of equivalence classes in our game is $2^b$ where $b=|E| - \dim{(U+U^*)} = |E|-(\dim U+\dim U^*-\dim{(U\cap U^*)}) = 2g+\dim{(U\cap U^*)}$ where $g$ is the genus of the surface on which the graph is embedded. In the plane case then, the number of equivalence classes is simply $2^b$ where $b=\dim{(U\cap U^*)}$. The row vectors of the incidence matrix for $G$ span the cocycle space $U\subseteq \GF^{|E|}$ which has dimension $|V|-1$ (see e.g. \cite{GodsilRoyle:AlgebraicGraphTheory}, Lemma 14.15.1). The cocycle space $U^*$ of the dual graph $G^*=(V^*,E^*)$ has dimension $|V^*|-1$. Using Euler characteristic and duality, we see $\dim U^*=|V^*|-1=|E|-|V|+1 = |E|-\dim U$. Since $\dim U + \dim U^{\perp}=|E|$ and $U^*\subseteq U^{\perp}$, it follows that $U^*=U^{\perp}$ and $U \cap U^*=U \cap U^{\perp}$. The claim follows since the dimension of the bicycle space $U\cap U^{\perp}$ is given by $b$ where $2^b=|T(-1,-1)|$ \cite{RosenstiehlRead:EdgeTripartition}. \end{proof} Given a knot diagram on an orientable surface, a region crossing change (RCC) is the result of reversing all crossings incident to a region of the diagram. Shimizu \cite{Shimizu:RegionChanges} and Cheng-Gao \cite{ChengGao:RegionChanges} study equivalence classes of planar link diagrams under the RCC operation. Their results follow as a corollary of Theorem \ref{Thm:PlaneGraphs}. \begin{corollary} Suppose $D$ is a $c$ component link diagram in the plane. Then the number of equivalence classes of diagrams with the same shadow as $D$ under the RCC operation is $2^{c-1}$. In particular, every knot diagram can be transformed to one of the unknot via a finite sequence of RCC moves. \end{corollary} \begin{proof} Given a link diagram in the plane, consider either of its checkerboard graphs. By Theorem \ref{Thm:ComponentsMedialGraph}, the Tutte polynomial of this graph specializes to $|T(-1,-1)|=2^{c-1}$, and the result now follows by Theorem \ref{Thm:PlaneGraphs}. \end{proof} \subsection{Representatives for the equivalence classes} For connected plane graphs there is a natural way of choosing representatives for the equivalence classes of the color change game using the vectors defined in Section \ref{Space P}. %First we recall the background from Section 17.3 in \cite{GodsilRoyle:AlgebraicGraphTheory}. Say $G=(V,E)$ is a finite, connected plane graph with medial graph having $c$ components. In Lemma \ref{Generators for P}, we described a $c-1$ dimensional space $\mathcal{P} \subseteq U^{\perp} \cap (U^*)^{\perp}$. In the plane setting since $U^*=U^{\perp}$ for plane graphs, the spaces $U\cap U^{\perp}$, $U\cap U^*$, and $\mathcal{P}$ are all the same. (As we will see in the next section, this is not true for arbitrary surfaces.) The vectors $v_1, \ldots, v_c$ described in Section \ref{Space P} span $\mathcal{P}$, and by Lemma 17.3.3 in \cite{GodsilRoyle:AlgebraicGraphTheory} any subset of $c-1$ of these $c$ vectors is a basis. \begin{theorem} Let $v_1, \dots, v_{c-1}$ be the basis for the bicycle space for $G$ described above. For $j=1, \dots, c-1,$ pick an edge $e_j\in E$ such that $v_j$ has a 1 in the position of $e_j$ and $v_k$ has 0 in the position of $e_j$ for all $k