%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{18}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\theoremstyle{definition}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{corollary}[thm]{Corollary}
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{exercise}[thm]{Exercise}
\newtheorem{Rem}[thm]{Remark}



%% define your title in the usual way
\title[Bijections and Lawrence polytopes]{A framework unifying some bijections for graphs and its connection to Lawrence polytopes}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Changxin Ding\thanks{\href{mailto:cding66@gatech.edu}{cding66@gatech.edu}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}School of Mathematics, Georgia Institute of Technology}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{Let $G$ be a connected graph. The Jacobian group (also known as the Picard group or sandpile group) of $G$ is a finite abelian group whose cardinality equals the number of spanning trees of $G$. The Jacobian group admits a canonical simply transitive action on the set $\mathcal{R}(G)$ of cycle-cocycle reversal classes of orientations of $G$. Hence one can construct combinatorial bijections between spanning trees of $G$ and $\mathcal{R}(G)$ to build connections between spanning trees and the Jacobian group. The geometric bijections (defined by Backman, Baker, and Yuen) and the Bernardi bijections are two important examples. In this paper, we construct a new family of such bijections that includes both. Our bijections depend on a pair of atlases (different from the ones in manifold theory) that abstract and generalize certain common features of the two known bijections. The definitions of these atlases are derived from triangulations and dissections of the Lawrence polytopes associated to $G$. The acyclic cycle signatures and cocycle signatures used to define the geometric bijections correspond to regular triangulations. Our bijections can extend to subgraph-orientation correspondences. Most of our results hold for regular matroids. We present our work in the language of fourientations, which are a generalization of orientations. }

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{sandpile group, cycle-cocycle reversal class, Lawrence polytope, triangulation, dissection, fourientation}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{Lawrence.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above




\section{Overview}\label{introduction}

This paper is an extended abstract of our recent work \cite{D3} to be submitted to the conference FPSAC 2024. Most of this paper comes from \cite[Section 1]{D3}. The major change we have made is that this paper is written in the setting of graphs rather than regular matroids. We hope this will benefit some readers who are not familiar with matroids. 


Given a connected graph $G$, we build a new family of bijections between the set $\mathcal{T}(G)$ of spanning trees of $G$ and the set $\mathcal{R}(G)$ of equivalence classes of orientations of $G$ up to cycle and cocycle reversals. The new family of bijections includes the \emph{BBY bijection} (also known as the geometric bijection) constructed by Backman, Baker, and Yuen \cite{BBY}, and the \emph{Bernardi bijection}\footnote{The Bernardi bijection in \cite{Bernardi} is a subgraph-orientation correspondence. In this paper, by the Bernardi bijection we always mean its restriction to spanning trees.} in \cite{Bernardi}. 

These bijections are closely related to the \emph{Jacobian group} (also known as the \emph{Picard group} or \emph{sandpile group}) $\text{Jac}(G)$ of $G$. The group $\text{Jac}(G)$ and the set $\mathcal{T}(G)$ of spanning trees are equinumerous. Recently, many efforts have been devoted to making $\mathcal{T}(G)$ a \emph{torsor} for $\text{Jac}(G)$, i.e., defining a simply transitive action of $\text{Jac}(G)$ on $\mathcal{T}(G)$. In \cite{BW}, Baker and Wang  interpreted the Bernardi bijection as a bijection between $\mathcal{T}(G)$ and \emph{break divisors}. Since the set of break divisors is a canonical torsor for $\text{Jac}(G)$ (see \cite{AKBS}), the Bernardi bijection induces the \emph{Bernardi torsor}. In \cite{Yuen}, Yuen defined the geometric bijection between $\mathcal{T}(G)$ and break divisors of $G$. Later, this work was generalized in \cite{BBY} where Backman, Baker, and Yuen defined the BBY bijection between $\mathcal{T}(G)$ and the cycle-cocycle reversal classes $\mathcal{R}(G)$. The set $\mathcal{R}(G)$ was introduced by Gioan \cite{G1} and is known to be a canonical torsor for $\text{Jac}(G)$ \cite{BBY}. Hence any bijection between $\mathcal{T}(G)$ and $\mathcal{R}(G)$ makes $\mathcal{T}(G)$ a torsor. 
From the point of view in \cite{BBY}, replacing break divisors with $\mathcal{R}(G)$ provides a more general setting. In particular, we may also view the Bernardi bijection as a bijection between $\mathcal{T}(G)$ and $\mathcal{R}(G)$ and define the Bernardi torsor. 

Our work puts all the above bijections in the same framework. It is surprising because the BBY bijection and the Bernardi bijection rely on totally different parameters. The main ingredients to define the BBY bijection 
are an \emph{acyclic cycle signature} $\sigma$ and an \emph{acyclic cocycle signature} $\sigma^*$ of $G$. The BBY bijection sends spanning trees to $(\sigma,\sigma^*)$-compatible orientations, which are representatives of $\mathcal{R}(G)$. The Bernardi bijection relies on a ribbon structure on the graph $G$ together with a vertex and an edge as initial data. Although for planar graphs, the Bernardi bijection becomes a special case of the BBY bijection, they are different in general \cite{Yuen, BBY}. The main ingredients to define our new bijections are a \emph{triangulating atlas} and a \emph{dissecting atlas} of $G$. These atlases (different from the ones in manifold theory) abstract and generalize certain common features of the two known bijections. They are derived from \emph{triangulations} and \emph{dissections} of the \emph{Lawrence polytopes} associated to graphs. The acyclic cycle signatures and cocycle signatures used to define the BBY bijections correspond to \emph{regular} triangulations. 


Our bijections extend to subgraph-orientation correspondences. The construction is similar to the one that extends the BBY bijection in \cite{D2}. The extended bijections have nice specializations to forests and connected subgraphs. 

Our results are also closely related to and motivated by K\'alm\'an's work \cite{K}, K\'alm\'an and T\'othm\'er\'esz's work \cite{KT1}, and Postnikov's work \cite{P} on \emph{root polytopes} of \emph{hypergraphs}, where the hypergraphs specialize to graphs, and the Lawrence polytopes generalize the root polytopes in the case of graphs. See \cite[Section 1.8]{D3} for details. 

We find it very efficient to present our theory in the language of \emph{fourientations}, which are a generalization of orientations introduced by Backman and Hopkins \cite{BH}.  

Most of our results hold for \emph{regular matroids} as in \cite{BBY}, although in this paper we focus on graphs. See \cite{D3} for the regular matroid version of this paper.   





\section{Notation and terminology}
\subsection{Cycles and cocycles of a graph}
%In this section, we introduce the definition of directed cts, directed cocycles, orientations, etc; see also \cite{BBY} and \cite{D2}.
Let $G$ be a connected finite graph with nonempty edge set $E$, where \emph{loops} and \emph{multiple edges} are allowed. For each edge $e\in E$, we may assign a direction to it and hence get an \emph{arc}. Note that a loop also has two possible directions. An \emph{orientation} of the graph $G$ is an assignment of a direction to each edge, typically denoted by $\overrightarrow{O}$. 

A subset $C$ of $E$ is called a \emph{cycle} if there exist distinct vertices $v_1,v_2, \cdots, v_n$ such that $C=\{\text{edge }v_iv_{i+1}:i=1,2,\cdots,n\}$, 
where $v_{n+1}:=v_1$. Note that a cycle may be a loop. If we direct every edge in $C$ from $v_i$ to $v_{i+1}$ or direct every edge in $C$ from $v_{i+1}$ to $v_{i}$, then we get a \emph{directed cycle}, typically denoted by $\overrightarrow{C}$. Given a subset $W$ of vertices, the set of edges with one endpoint in $W$ and the other one not in $W$ is called a \emph{cut}. A \emph{cocycle} $C^*$ is a cut which is minimal for inclusion. If we direct every edge in $C^*$ from $W$ to its complement (or in the other way), then we get a \emph{directed cocycle}, typically denoted by $\overrightarrow{C^*}$. 

When an arc $\overrightarrow{e}$, a directed cycle $\overrightarrow{C}$, or a directed cocycle $\overrightarrow{C^*}$ is specified, the corresponding underlying edge(s) will be denoted by $e$, $C$, or $C^*$, respectively. Viewing $\overrightarrow{O}$, $\overrightarrow{C}$, and $\overrightarrow{C^*}$ as sets of arcs, it makes sense to write $\overrightarrow{e}\in\overrightarrow{O}$, etc. 


Now we define \emph{cycle-cocycle reversal (equivalence) classes} of orientations of $G$ introduced by Gioan \cite{G1}.
If $\overrightarrow{C}$ is a directed cycle in an orientation $\overrightarrow{O}$ of $G$, then a \emph{cycle reversal} replaces $\overrightarrow{C}$ with the opposite directed cycle in $\overrightarrow{O}$. The equivalence relation generated by cycle reversals defines the \emph{cycle reversal classes} of orientations of $G$. Similarly, we may define the \emph{cocycle reversal classes}. The equivalence relation generated by cycle and cocycle reversals defines the \emph{cycle-cocycle reversal classes}. It is proved in \cite{G1} that the number of cycle-cocycle reversal classes of $G$ equals the number of spanning trees of $G$. 

Let $T$ be a spanning tree of $G$ and $e$ be an edge. If $e\notin T$, then we call the unique cycle in $T\cup \{e\}$ the \emph{fundamental cycle} of $e$ (with respect to $T$); if $e\in T$, then we call the unique cocycle in $(E\backslash T)\cup \{e\}$ the \emph{fundamental cocycle} of $e$ (with respect to $T$).  






\subsection{Fourientations, potential cycles, and potential cocycles}\label{four}

It is convenient to introduce our theory in terms of \emph{fourientations}. Fourientations of graphs are systematically studied by Backman and Hopkins \cite{BH}. We will only make use of the basic notions. A fourientation $\overrightarrow{F}$ of the graph $G$ is a subset of the set of all the $2|E|$ arcs. Intuitively, a fourientation is a choice for each edge of $G$ whether to 
make it \emph{one-way oriented}, leave it \emph{unoriented}, or \emph{biorient} it. 
We denote by $-\overrightarrow{F}$ the fourientation obtained by reversing all the arcs in $\overrightarrow{F}$. In particular, the bioriented edges remain bioriented. We denote by $\overrightarrow{F}^c$ the set complement of $\overrightarrow{F}$, which is also a fourientation. A \emph{potential cycle} of a fourientation $\overrightarrow{F}$ is a directed cycle $\overrightarrow{C}$ such that $\overrightarrow{C}\subseteq \overrightarrow{F}$. A \emph{potential cocycle} of a fourientation $\overrightarrow{F}$ is a directed cocycle $\overrightarrow{C^*}$ such that $\overrightarrow{C^*}\subseteq -\overrightarrow{F}^c$. See Figure~\ref{fourientation1} for examples.




\begin{figure}[ht]
            \centering
            \includegraphics[scale=1]{fourientation12.eps}
            \caption{Examples of fourientation, potential cycle and potential cocycle}
            \label{fourientation1}
\end{figure}




\section{New framework: a pair of atlases and its induced map}\label{new framework}

The BBY bijection studied in \cite{BBY} relies upon a pair consisting of an acyclic cycle signature and an acyclic cocycle signature. We will generalize this work by building a new framework where the signatures are replaced by \emph{atlases} and the BBY bijection is replaced by a map $f_{\mathcal{A},\mathcal{A^*}}$. This section will introduce these new terminologies. 

\begin{definition}\label{def1}
Let $T$ be a tree of $G$ (from now on, by trees we mean spanning trees). 

(1) We call the edges in $T$ \emph{internal} and the edges not in $T$ \emph{external}.

(2) An \emph{externally oriented tree} $\overrightarrow{T}$ is a fourientation where all the internal edges are bioriented and all the external edges are one-way oriented. Dually, an \emph{internally oriented tree} $\overrightarrow{T^*}$ is a fourientation where all the external edges are bioriented and all the internal edges are one-way oriented. 

(3) An \emph{external atlas} $\mathcal{A}$ of $G$ is a collection of externally oriented trees $\overrightarrow{T}$ such that each tree of $G$ appears exactly once. Dually, an \emph{internal atlas} $\mathcal{A^*}$ of $G$ is a collection of internally oriented trees $\overrightarrow{T^*}$ such that each tree of $G$ appears exactly once.
\end{definition}

    
Given an external atlas $\mathcal{A}$ (resp.\ internal atlas $\mathcal{A^*}$) and a tree $T$, by $\overrightarrow{T}$ (resp.\ $\overrightarrow{T^*}$) we always mean the oriented tree in the atlas though the notation does not refer to the atlas. 


\begin{definition}[See Figure~\ref{mapexample}]\label{def2}
For a pair of atlases $(\mathcal{A},\mathcal{A^*})$, we define the following map
    \begin{align*}
    f_{\mathcal{A},\mathcal{A^*}}:\{\text{trees of }G\} & \to \{\text{orientations of }G\} \\
    T & \mapsto \overrightarrow{T} \cap \overrightarrow{T^*} \text{ (where } \overrightarrow{T}\in\mathcal{A},\overrightarrow{T^*}\in\mathcal{A^*}\text{).}
    \end{align*}    
\end{definition}
 
\begin{figure}[ht]
            \centering
            \includegraphics[scale=0.9]{map_short.eps}
            \caption{An example for Definition~\ref{def1} and \ref{def2}. The trees of the triangle graph are in red. For each tree $T$, the externally oriented tree $\overrightarrow{T}\in\mathcal{A}$ and the internally oriented tree $\overrightarrow{T^*}\in\mathcal{A^*}$ are in the same column. Their intersection  $f_{\mathcal{A},\mathcal{A^*}}= \overrightarrow{T} \cap \overrightarrow{T^*}$ is displayed at the bottom.}  
            \label{mapexample}
\end{figure} 


In the forthcoming Example~\ref{sigma atlas} and Example~\ref{B atlas}, we will put the BBY bijection and the Bernardi bijection in our framework. Before that, we recall the definitions of cycle (resp.\ cocycle) signatures and acyclic cycle (resp.\ cocycle) signatures in \cite{BBY}. 

\begin{definition}\label{def3}
Let $G$ be a graph. 

(1) A \emph{cycle signature} $\sigma$ of $G$ is the choice of a direction for each cycle of $G$. For each cycle $C$, we denote by $\sigma(C)$ the directed cycle we choose for $C$. By abuse of notation, sometimes we also view $\sigma$ as the set of the directed cycles of $G$ chosen by $\sigma$.

(2) The cycle signature $\sigma$ is said to be \emph{acyclic} if whenever $a_C$ are nonnegative reals with $\sum_C a_C\sigma(C)=0$ in $\mathbb{R}^E$ we have $a_C=0$ for all $C$, where the sum is over all cycles of $G$, and $\sigma(C)$ is viewed as a $\{0,\pm 1\}$-vector in $\mathbb{R}^E$ w.r.t. a fixed reference orientation.

(3) \emph{Cocycle signatures} $\sigma^*$ and \emph{acyclic cocycle signatures} are defined similarly. 
 

\end{definition}

\begin{example}[Atlases $\mathcal{A}_\sigma,\mathcal{A}^*_{\sigma^*}$ and the BBY map (bijection)]\label{sigma atlas} Let $\sigma$ be a cycle signature of $G$. We may construct an external atlas $\mathcal{A}_\sigma$ from $\sigma$ such that for each externally oriented tree $\overrightarrow{T}\in\mathcal{A}_\sigma$, each external arc $\overrightarrow{e}\in\overrightarrow{T}$ is oriented according to the orientation of the fundamental cycle of $e$ determined by $\sigma$. Similarly, we may construct an internal atlas $\mathcal{A}^*_{\sigma^*}$ from any cocycle signature $\sigma^*$ such that for each internally oriented tree $\overrightarrow{T^*}\in\mathcal{A}^*_{\sigma^*}$, each internal arc $\overrightarrow{e}\in\overrightarrow{T^*}$ is oriented according to the orientation of the fundamental cocycle of $e$ determined by $\sigma^*$. Then when the two signatures are acyclic, the map $f_{\mathcal{A}_\sigma,\mathcal{A}^*_{\sigma^*}}$ is exactly the BBY map defined in \cite{BBY}. 
\end{example}




\begin{example}[Atlases $\mathcal{A_\text{B}}, \mathcal{A}_q^*$ and the Bernardi map (bijection)]\label{B atlas}
The Bernardi bijection is defined for a connected graph $G$ equipped with a \emph{ribbon structure} and with initial data $(q,e)$, where $q$ is a vertex and $e$ is an edge incident to the vertex; see \cite[Section 3.2]{Bernardi} for details. Here we use an example (Figure~\ref{mapexample2}) to recall the construction of the bijection in the atlas language. The Bernardi bijection is a map from trees to certain orientations. The construction makes use of the \emph{Bernardi tour} which starts with $(q,e)$ and goes around a given tree $T$ according to the ribbon structure. We may construct an external atlas $\mathcal{A_\text{B}}$ of $G$ as follows. Observe that the Bernardi tour cuts each external edge twice. We orient each external edge toward the first-cut endpoint,  biorient all the internal edges of $T$, and hence get an externally oriented tree $\overrightarrow{T}$. All such externally oriented trees form the atlas $\mathcal{A_\text{B}}$. 

The internal atlas $\mathcal{A}_q^*$ of $G$ is constructed as follows. For any tree $T$, we orient each internal edge away from $q$, biorient external edges, and hence get $\overrightarrow{T^*}\in\mathcal{A}_q^*$. We remark that $\mathcal{A}_q^*$ is a special case of $\mathcal{A}^*_{\sigma^*}$, where $\sigma^*$ is an acyclic cocycle signature \cite[Example 1.3.4]{BBY}. 

The map $f_{\mathcal{A}_\text{B},\mathcal{A}_q^*}$ is exactly the Bernardi map. 

\begin{figure}[ht]
            \centering
            \includegraphics[scale=0.8]{Bernardibijection2T.eps}
            \caption{An example for the Bernardi map. The tree $T$ is in red.}
            \label{mapexample2}
\end{figure}
\end{example}



\section{Bijections and the two atlases}\label{bijection and atlas}

We will see in this section that the map $f_{\mathcal{A},\mathcal{A^*}}$ induces a bijection between trees of $G$ and cycle-cocycle reversal classes of $G$ when the two atlases satisfy certain conditions which we call \emph{dissecting} and \emph{triangulating}. Furthermore, we will extend the bijection as in \cite{D2}. 

The following definitions play a central role in our paper. Although the definitions are combinatorial, they were derived from dissecting and triangulating Lawrence polytopes; see Section~\ref{Lawrence-intro}.

\begin{definition}\label{key def}
Let $\mathcal{A}$ be an external atlas and $\mathcal{A^*}$ be an internal atlas of $G$. 

(1) We call $\mathcal{A}$ \emph{dissecting} if for any two distinct trees $T_1$ and $T_2$, the fourientation $\overrightarrow{T_1}\cap(-\overrightarrow{T_2})$ has a potential cocycle. Dually, we call $\mathcal{A^*}$ \emph{dissecting} if for any two distinct trees $T_1$ and $T_2$, the fourientation $(\overrightarrow{T_1^*}\cap(-\overrightarrow{T_2^*}))^c$ has a potential cycle. 

(2) We call $\mathcal{A}$ \emph{triangulating} if for any two distinct trees $T_1$ and $T_2$, the fourientation $\overrightarrow{T_1}\cap(-\overrightarrow{T_2})$ has no potential cycle. Dually, we call $\mathcal{A^*}$ \emph{triangulating} if for any two distinct trees $T_1$ and $T_2$, the fourientation $(\overrightarrow{T_1^*}\cap(-\overrightarrow{T_2^*}))^c$ has no potential cocycle.
\end{definition}

\begin{Rem}
Being triangulating is stronger than being dissecting by \cite[Proposition 2.6]{BH}.
\end{Rem}

Now we are ready to present the first main result in this paper. 
\begin{thm}\label{main1}
    Given a pair of dissecting atlases $(
\mathcal{A},\mathcal{A^*})$ of a graph $G$, if at least one of the atlases is triangulating, then the map 
    \begin{align*}
    \overline{f}_{\mathcal{A},\mathcal{A^*}}:\{\text{trees of }G\} & \to \{\text{cycle-cocycle reversal classes of }G\} \\
    T & \mapsto [\overrightarrow{T} \cap \overrightarrow{T^*}]
    \end{align*}
is bijective, where $[\overrightarrow{T} \cap \overrightarrow{T^*}]$ denotes the cycle-cocycle reversal class containing $\overrightarrow{T} \cap \overrightarrow{T^*}$.
\end{thm}


\begin{example}[Example~\ref{sigma atlas} continued]\label{mainex}
One of the main results in \cite{BBY} is that the BBY map induces a bijection between trees and cycle-cocycle reversal classes. Because $\mathcal{A}_\sigma$ and $\mathcal{A}^*_{\sigma^*}$ are triangulating (\cite[Lemma 3.4]{D3}), Theorem~\ref{main1} recovers this result.   
\end{example}


\begin{example}[Example~\ref{B atlas} continued]
Theorem~\ref{main1} also recovers the bijectivity of the Bernardi map for trees in \cite{Bernardi}. In \cite{Bernardi}, it is proved that the Bernardi map is a bijection between trees and the \emph{$q$-connected outdegree sequences}. Baker and Wang \cite{BW} observed that the $q$-connected outdegree sequences are essentially the same as the \emph{break divisors}. Later in \cite{BBY}, the break divisors are equivalently replaced by cycle-cocycle reversal classes. The external atlas $\mathcal{A}_\text{B}$ is dissecting (\cite[Lemma 3.15]{D3}). The internal atlas $\mathcal{A}_q^*$ is triangulating because it equals $\mathcal{A}^*_{\sigma^*}$ for some acyclic signature $\sigma^*$. Hence our theorem applies.

\end{example}

In Theorem~\ref{main1}, if we do not further assume that one of the atlases is triangulating, then the map $\overline{f}_{\mathcal{A},\mathcal{A^*}}$ is not necessarily bijective; see \cite[Example 1.11]{D3}. 

In \cite{D2}, the BBY bijection is extended to a bijection between spanning subgraphs of $G$ (i.e., subsets of $E$) and orientations of $G$ in a canonical way. We also generalize this work by extending $f^{-1}_{\mathcal{A},\mathcal{A^*}}$ to $\varphi_{\mathcal{A},\mathcal{A^*}}$.  

\begin{definition}[The map $\varphi_{\mathcal{A},\mathcal{A^*}}$]\label{def-ext}
We will define a map $\varphi_{\mathcal{A},\mathcal{A^*}}$ from orientations to subgraphs such that $\varphi_{\mathcal{A},\mathcal{A^*}}\circ f_{\mathcal{A},\mathcal{A^*}}$ is the identity map, and hence $\varphi_{\mathcal{A},\mathcal{A^*}}$ extends $f^{-1}_{\mathcal{A},\mathcal{A^*}}$.  We start with an orientation $\overrightarrow{O}$. By Theorem~\ref{main1}, we get a tree $T=\overline{f}_{\mathcal{A},\mathcal{A^*}}^{-1}([\overrightarrow{O}])$. Since $\overrightarrow{O}$ and $f_{\mathcal{A},\mathcal{A^*}}(T)$ are in the same cycle-cocycle reversal class, one can obtain one of them by reversing disjoint directed cycles $\{\overrightarrow{C_i}\}_{i\in I}$ and cocycles $\{\overrightarrow{C_j^*}\}_{j\in J}$ in the other (\cite[Lemma 2.7]{D3}). Define $\varphi_{\mathcal{A},\mathcal{A^*}}(\overrightarrow{O})=(T\cup \biguplus\limits_{i\in I}C_i)\backslash \biguplus\limits_{j\in J}C_j^*$, where the symbol $\uplus$ means disjoint union.    
\end{definition}

\vspace{-2mm}

The amazing fact here is that $\varphi_{\mathcal{A},\mathcal{A^*}}$ is a bijection, and it has nice specializations. 
\begin{thm}\label{main2}
Fix a pair of dissecting atlases $(
\mathcal{A},\mathcal{A^*})$ of $G$ with ground set $E$. Suppose at least one of the atlases is triangulating. 

(1) The map $\varphi_{\mathcal{A},\mathcal{A^*}}$ is a bijection from orientations of $G$ to spanning subgraphs of $G$. 

(2) The image of the spanning forests of $G$ under the bijection $\varphi^{-1}_{\mathcal{A},\mathcal{A^*}}$ is a representative set of the cycle reversal classes of $G$. 

(3) The image of the spanning connected subgraphs of $G$ under the bijection $\varphi^{-1}_{\mathcal{A},\mathcal{A^*}}$ is a representative set of the cocycle reversal classes of $G$. 
\end{thm}

\begin{Rem}
We can apply Theorem~\ref{main2} to extend and generalize the Bernardi bijection; see \cite[Corollary 3.16]{D3} for a formal statement. 
\end{Rem}

\section{Signatures and the two atlases}\label{sign}
This section studies cycle signatures (resp.\ cocycle signatures) in terms of external atlases (resp.\ internal atlases). In particular, we will see Theorem~\ref{main1} and Theorem~\ref{main2} generalize the bijections in \cite{BBY} and \cite{D2}, respectively. 
 

Recall in Example~\ref{sigma atlas} that from signatures $\sigma$ and $\sigma^*$, we may construct atlases $\mathcal{A}_\sigma$ and $\mathcal{A}^*_{\sigma^*}$. It is natural to ask: (1) Which signatures induce triangulating atlases? (2) Is any triangulating atlas induced by a signature? 

The following definition and theorem answer these two questions. 

\begin{definition}
    A cycle signature $\sigma$ is said to be \emph{triangulating} if for any $\overrightarrow{T}\in\mathcal{A}_\sigma$ and any directed cycle $\overrightarrow{C}\subseteq\overrightarrow{T}$, $\overrightarrow{C}$ belongs to $\sigma$. Dually, a cocycle signature $\sigma^*$ is said to be \emph{triangulating} if for any $\overrightarrow{T^*}\in\mathcal{A}^*_{\sigma^*}$ and any directed cocycle $\overrightarrow{C^*}\subseteq\overrightarrow{T^*}$, $\overrightarrow{C^*}$ belongs to $\sigma^*$.

\end{definition}

\begin{thm}\label{trig-intro}
The map $\alpha: \sigma\mapsto\mathcal{A}_\sigma$ is a bijection from the set of triangulating cycle signatures of $G$ to the set of triangulating external atlases of $G$. Dually, the map $\alpha^*: \sigma^*\mapsto\mathcal{A}^*_{\sigma^*}$ is a bijection from the set of triangulating cocycle signatures of $G$ to the set of triangulating internal atlases of $G$.
\end{thm}

\begin{Rem}\label{rem-nonexample}
For a dissecting external atlas $\mathcal{A}$, it is possible for there to be no cycle signature $\sigma$ such that $\mathcal{A}_\sigma=\mathcal{A}$; see \cite[Remark 1.18]{D3}. 
\end{Rem}

\begin{Rem}
Acyclic signatures are all triangulating; see \cite[Lemma 3.4]{D3}. There exists a triangulating signature that is not acyclic; see \cite[Proposition ~3.14]{D3}. In Section~\ref{Lawrence-intro}, we will see acyclic signatures correspond to regular triangulations. 
\end{Rem}

A nice thing about the acyclic signatures is that the associated compatible orientations (defined below) form representatives of orientation classes (proved in \cite{BBY}). The triangulating signatures also have this property; see the proposition below. 

\begin{definition}\label{def4}
Let $G$ be a graph, $\sigma$ be a cycle signature, $\sigma^*$ be a cocycle signature, and $\overrightarrow{O}$ be an orientation of $G$. 

(1) The orientation $\overrightarrow{O}$ is said to be \emph{$\sigma$-compatible} if any directed cycle in $\overrightarrow{O}$ is in $\sigma$.

(2) The orientation $\overrightarrow{O}$ is said to be \emph{$\sigma^*$-compatible} if any directed cocycle in $\overrightarrow{O}$ is in $\sigma^*$. 
 
(3) The orientation $\overrightarrow{O}$ is said to be  \emph{($\sigma,\sigma^*$)-compatible} if it is both $\sigma$-compatible and $\sigma^*$-compatible.
\end{definition}


\begin{proposition}
Suppose $\sigma$ and $\sigma^*$ are \emph{triangulating} signatures. 

(1) The set of $(\sigma, \sigma^*)$-compatible orientations is a representative set of the cycle-cocycle reversal classes of $G$.

(2) The set of $\sigma$-compatible orientations (resp.\ $\sigma^*$-compatible orientations) is a representative set of the cycle (resp.\ cocycle) reversal classes of $G$.
\end{proposition}

To reformulate Theorem~\ref{main1} and Theorem~\ref{main2} in terms of signatures and compatible orientations, we write\[\text{BBY}_{\sigma,\sigma^*}=f_{\mathcal{A}_\sigma,\mathcal{A}^*_{\sigma^*}}\text{ and }\varphi_{\sigma,\sigma^*}=\varphi_{\mathcal{A}_\sigma,\mathcal{A}^*_{\sigma^*}}.\]They are exactly the BBY bijection in \cite{BBY} and the extended BBY bijection in \cite{D2} when the two signatures are acyclic. By the two theorems and a little extra work, we have the following theorems, which generalize the work in \cite{BBY} and \cite{D2}, respectively. 
\begin{thm}\label{main1-sign}
Suppose $\sigma$ and $\sigma^*$ are \emph{triangulating} signatures of a graph $G$. The map $\text{BBY}_{\sigma,\sigma^*}$ is a bijection from trees of $G$ to $(\sigma,\sigma^*)$-compatible orientations of $G$.
\end{thm}
\begin{thm}\label{main2-sign}
Suppose $\sigma$ and $\sigma^*$ are \emph{triangulating} signatures of a graph $G$.  

(1) The map $\varphi_{\sigma,\sigma^*}$ is a bijection from orientations of $G$ to spanning subgraphs of $G$.

(2) The map $\varphi_{\sigma,\sigma^*}$ specializes to a bijection between $\sigma$-compatible orientations and spanning forests of $G$.

(3)The map $\varphi_{\sigma,\sigma^*}$ specializes to a bijection between $\sigma^*$-compatible orientations and spanning connected subgraphs of $G$. 
\end{thm}




The definition of triangulating signatures is somewhat indirect. However, we have the following nice description for the triangulating \emph{cycle} signatures, the proof of which is due to Gleb Nenashev. We do not know whether it holds for regular matroids. 

\begin{thm}\label{triangular}
A \emph{cycle} signature $\sigma$ of a graph $G$ is triangulating if and only if for any three directed cycles in $\sigma$, their sum (as vectors in $\mathbb{Z}^E$) is not zero. 
\end{thm}


\section{Lawrence polytopes and the two atlases}\label{Lawrence-intro}

In this section, we will introduce a pair of \emph{Lawrence polytopes}\footnote{Readers can find some information on Lawrence polytopes in \cite{BS}.} $\mathcal{P}$ and $\mathcal{P^*}$ associated to a graph $G$. We will see that dissections and triangulations of the Lawrence polytopes correspond to the dissecting atlases and triangulating atlases, respectively, which is actually how we derived Definition~\ref{key def}. We will also see that regular triangulations correspond to acyclic signatures. 

By fixing a reference orientation of $G$, we get an \emph{oriented incidence matrix} of $G$. The matrix is not of full rank. By deleting its last row, we get a matrix $M_{r\times n}$, where $n$ equals the number of edges of $G$ and $r$ equals the number of edges of any tree of $G$. We can also construct another matrix $M^*_{(n-r)\times n}$ viewed as the dual of $M$. The construction is classic; see \cite[Section 3.6]{D2}. For the readers who are familiar with matroids, we can simply say that $M$ (resp.\ $M^*$) represents the graphic (resp.\ cographic) matroid associated to $G$. 

\begin{definition}

(1) We call \[\begin{pmatrix} M_{r\times n} & {\bf 0} \\  I_{n\times n} &  I_{n\times n} \end{pmatrix}\] the \emph{Lawrence matrix}, where $I_{n\times n}$ is the identity matrix. The columns of the Lawrence matrix are denoted by $P_1, \cdots, P_n$, $P_{-1}, \cdots, P_{-n}\in\mathbb{R}^{n+r}$ in order.     

(2) The \emph{Lawrence polytope} $\mathcal{P}\subseteq \mathbb{R}^{n+r}$ of $G$ is the convex hull of the points $P_1, \cdots, P_n$, $P_{-1}, \cdots, P_{-n}$.
    
(3) If we replace the matrix $M$ in (1) with $M^*$ , then we get the Lawrence polytope $\mathcal{P^*}\subseteq\mathbb{R}^{2n-r}$. We use the labels $P_i^*$ for the points generating $\mathcal{P^*}$.  

(4) We further assume that $G$ is loopless when defining $\mathcal{P}$ and that $G$ is coloopless when defining $\mathcal{P}^*$, to avoid duplicate columns of the Lawrence matrix. 
\end{definition}



%\begin{Rem}
%Our definition of the Lawrence polytope depends on the choice of $M$. However, our results involving the Lawrence polytope do not depend on the choice of $M$. 
%\end{Rem}
We recall some basic notions in discrete geometry. 
\begin{definition}
A \emph{simplex} $S$ is the convex hull of some affinely independent points. A \emph{face} of $S$ is a simplex generated by a subset of these points, which could be $S$ or $\emptyset$.
\end{definition}

\begin{definition}\label{tri-diss-def}
Let $\mathcal{P}$ be a polytope of dimension $d$. 

(1) If $d+1$ of the vertices of $\mathcal{P}$ form a $d$-dimensional simplex, we call such a simplex a \emph{maximal simplex} of $\mathcal{P}$.


(2) A \emph{dissection} of $\mathcal{P}$ is a collection of maximal simplices of $\mathcal{P}$ such that (I) the union is $\mathcal{P}$, and (II) the relative interiors of any two distinct maximal simplices in the collection are disjoint. 

(3) If we replace the condition (II) in (2) with the condition (III) that any two distinct maximal simplices in the collection intersect in a common face (which could be empty), then we get a \emph{triangulation}. (See Figure~\ref{tri-dis}.)
\end{definition}


\begin{figure}[ht]
            \centering
            \includegraphics[scale=0.8]{dissection.eps}
            \caption{A triangulation and a dissection of an octahedron}
            \label{tri-dis}
\end{figure}  

The next two theorems build the connection between the geometry of the Lawrence polytopes and the combinatorics of the graph. To state them, we need to label the $2|E|$ arcs of $G$. Note that each column of $M$ corresponds to the arcs of $G$ in the reference orientation. We denote them by $\overrightarrow{e_1}, \cdots, \overrightarrow{e_n}$. For the rest of the arcs, we let $\overrightarrow{e_{-i}}=-\overrightarrow{e_i}$.  
\begin{thm}\label{3-fold}
We have the following threefold bijections, all of which are denoted by $\chi$. (It should be clear from the context which one we are referring to when we use $\chi$. )

(1) The Lawrence polytope $\mathcal{P}\subseteq\mathbb{R}^{n+r}$ is an $(n+r-1)$-dimensional polytope whose vertices are exactly the points $P_1, \cdots, P_n, P_{-1}, \cdots, P_{-n}$. Hence we may define a bijection \begin{align*}
    \chi:\{\text{vertices of }\mathcal{P}\} & \to  \{\text{arcs of }G\} \\
    P_i & \mapsto  \overrightarrow{e_i}
    \end{align*}
    
    \vspace{-2mm}

(2) The map $\chi$ in (1) induces a bijection \begin{align*}    
    \chi:\{\text{maximal simplices of }\mathcal{P}\} & \to \{\text{externally oriented trees of }G\} \\
    \begin{gathered}
        \text{a maximal simplex}\\
        \text{with vertices }\{P_i:i\in I\}
    \end{gathered} & \mapsto \text{the fourientation }\{\chi(P_i):i\in I\}. 
    \end{align*}

    \vspace{-2mm}
    
(3) The map $\chi$ in (2) induces two bijections
    \begin{align*}
    \chi:\{\text{triangulations of }\mathcal{P}\} & \to \{\text{triangulating external atlases of }G\} \\
    \begin{gathered}
        \text{a triangulation with} \\
        \text{maximal simplices }\{S_j:j\in J\}
    \end{gathered} & \mapsto \text{the external atlas }\{\chi(S_j):i\in J\}, 
    \end{align*}

    \vspace{-2mm}
    
    and \begin{align*}
    \chi:\{\text{dissections of }\mathcal{P}\} & \to \{\text{dissecting external atlases of }G\} \\
     \begin{gathered}
         \text{a dissection with}\\\text{maximal simplices }\{S_j:j\in J\}
     \end{gathered} & \mapsto \text{the external atlas }\{\chi(S_j):j\in J\}.
    \end{align*}

    \vspace{-2mm}
    
(4) The statements dual to (1), (2), and (3) hold for the Lawrence polytope $\mathcal{P^*}$. 
\end{thm}

 
Recall that the map $\alpha:\sigma\mapsto\mathcal{A}_\sigma$ is a bijection between triangulating cycle signatures and triangulating external atlases of $G$. 


\begin{thm}\label{main3}
The restriction of the bijection $\chi^{-1}\circ\alpha$ to the set of acyclic cycle signatures of $G$ is bijective onto the set of \emph{regular triangulations} of $\mathcal{P}$. The dual statement also holds. (See \cite{DRS} for the definition of regular triangulations.)
\end{thm}



We conclude this section with Table~\ref{table-summarize}.

\begin{table}[!ht]
\centering
\begin{tabular}{ |c||c|c|c| }
\hline
\begin{tabular}{c}types of dissections of \\ Lawrence polytope $\mathcal{P}$\end{tabular}
 & dissection & triangulation\ & regular triangulation\\
\hline
types of external atlas $\mathcal{A}$ & dissecting & triangulating & (no good description)  \\
\hline
types of cycle signature $\sigma$ & (may not exist) & triangulating & acyclic \\
\hline
\end{tabular}
\caption{A summary of the correspondences among dissections of Lawrence polytopes, atlases, and signatures via $\alpha$ and $\chi$. We omit the dual part. }
\label{table-summarize}
\vspace{-8mm}
\end{table}



%\acknowledgements{Many thanks to Olivier Bernardi for orienting the author toward the study of this project and for countless helpful discussions. Thanks to Spencer Backman, Matt Baker, and Chi Ho Yuen for helpful discussions. Thanks to Gleb Nenashev for proving Theorem~\ref{triangular}. Thanks to the referees for helpful comments. }

\newpage
\acknowledgements{Thanks to Olivier Bernardi for providing guidance throughout this project. Thanks to Gleb Nenashev for proving Theorem~\ref{triangular}. Thanks to Spencer Backman, Matt Baker, and Chi Ho Yuen for helpful discussions.  Thanks to the referees for helpful comments. }

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
