%% 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[revision]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{39}
\addbibresource{39.bib}

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

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}[theorem]{Example}

\usepackage{lipsum}

\newcommand{\Acal}{{\mathcal A}}
\newcommand{\Bcal}{{\mathcal B}}
\newcommand{\Ccal}{{\mathcal C}}
\newcommand{\Dcal}{{\mathcal D}}
\newcommand{\Fcal}{{\mathcal F}}
\newcommand{\Gcal}{{\mathcal G}}
\newcommand{\Lcal}{{\mathcal L}}
\newcommand{\Ocal}{{\mathcal O}}
\newcommand{\Pcal}{{\mathcal P}}
\newcommand{\Tcal}{{\mathcal T}}
\newcommand{\Ofrak}{{\mathfrak O}}
\newcommand{\BDcal}{{\mathcal B}{\mathcal D}}
\newcommand{\STcal}{{\mathcal S}{\mathcal T}}

\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Cone}{\operatorname{Cone}}
\newcommand{\coker}{\operatorname{coker}}
\newcommand{\Div}{\operatorname{Div}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\indeg}{\operatorname{indeg}}
\newcommand{\Jac}{\operatorname{Jac}}
\newcommand{\outdeg}{\operatorname{outdeg}}
\newcommand{\Pic}{\operatorname{Pic}}
\newcommand{\row}{\operatorname{row}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\sign}{\operatorname{sign}}
\newcommand{\supp}{\operatorname{supp}}

\DeclareRobustCommand{\rchi}{{\mathpalette\irchi\relax}}
\newcommand{\irchi}[2]{\raisebox{\depth}{$#1\chi$}}

%% define your title in the usual way
\title{Topological Bijections for Oriented Matroids}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Spencer Backman\thanks{\href{mailto:spencer.backman@mail.huji.ac.il}{spencer.backman@mail.huji.ac.il}}\addressmark{1}, Francisco Santos\thanks{\href{mailto:francisco.santos@unican.es}{francisco.santos@unican.es}}\addressmark{2}, \and Chi Ho Yuen\thanks{\href{mailto:chi.yuen@math.unibe.ch}{chi.yuen@math.unibe.ch}}\addressmark{3}}

%
%
%

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Einstein Institute for Mathematics, Hebrew University of Jerusalem, Israel\\
\addressmark{2}Department of Mathematics, Statistics and Computer Science, University of Cantabria, Spain\\ \addressmark{3}Mathematical Institute, University of Bern, Switzerland}

%% put the date of submission here
\received{November 15, 2018}

%% leave this blank until submitting a revised version
\revised{March 31, 2019}

%% 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{In previous work by the first and third author with Matthew Baker, a family of bijections between bases of a regular matroid and the Jacobian group of the matroid was given. The core of the work is a geometric construction using zonotopal tilings that produces bijections between the bases of a realizable oriented matroid and the set of {\em $(\sigma,\sigma^*)$-compatible orientations} with respect to some {\em acyclic} circuit (respectively, cocircuit) signature $\sigma$ (respectively, $\sigma^*$). In this work, we extend this construction to general oriented matroids and circuit (respectively, cocircuit) signatures coming from generic single-element liftings (respectively, extensions). As a corollary, when both signatures are induced by the same lexicographic data, we give a new (bijective) proof of the interpretation of $T_M(1,1)$ using orientation activity due to Gioan and Las Vergnas. Here $T_M(x,y)$ is the Tutte polynomial of the matroid.}

%The main ingredient of the proof is the theory of oriented matroid programming, in which pseudosphere arrangements serve as the equivalent objects of zonotopal tilings (which do not exist when the underlying oriented matroid is not realizable) up to duality; as such, we call our bijections {\em topological bijections} to reflect the reference of the topological representation theorem.

%% 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{Oriented matroid, Tutte polynomial, orientation activity}

%% 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, ie. [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{TopoBij.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{Introduction}

The {\em Tutte polynomial} $T_M(x,y)$ of a matroid $M$ is one of the most prominent invariants associated to $M$; among other information, special evaluations of $T_M(x,y)$ enumerate various objects linked to $M$. For instance, when $M$ is the graphical matroid of a finite connected graph $G$, $T_M(1,1)$ enumerates the following objects: the set $\Tcal(G)$ of spanning trees of $G$, Gioan's {\em cycle-cocycle reversal system} $\Gcal(G)$, and the {\em Jacobian group} $\Jac(G)$ (also called the {\em sandpile group}, {\em critical group}, etc.). Finding bijective proofs for these enumerative results has attracted a considerable amount of interest in combinatorics. In \cite{BBY}, a new family of bijections between $\Tcal(G)$ and $\Jac(G)$ via $\Gcal(G)$ was constructed. The key step in the work is a bijection $\beta_{\sigma,\sigma^*}$ between spanning trees and {\em $(\sigma,\sigma^*)$-compatible orientations}\footnote{In \cite{BBY}, such a map is denoted by $\hat{\beta}_{\sigma,\sigma^*}$, but since we will never refer to the original $\beta_{\sigma,\sigma^*}$ in this note, we drop the hat for the sake of notational simplicity.}, special orientations of $G$ that form a system of representatives of $\Gcal(G)$, for every pair of {\em acyclic cycle signature} $\sigma$ and {\em acyclic cocycle signature} $\sigma^*$.

To motivate our work, we explain the essential definitions and describe the map $\beta_{\sigma,\sigma^*}$ here: a {\em cycle signature} $\sigma$ picks an orientation for each simple cycle $C$ of the graph, and $\sigma$ is {\em acyclic} if the equation $\sum_{C} a_C\sigma(C)=0$ has no non-zero non-negative solution over the reals, where the sum is over all simple cycles of $C$, and each $\sigma(C)$, which is a directed cycle, is interpreted as an element in $\mathbb{Z}^{E(G)}$; define an {\em acyclic cocycle signature} similarly for cocycles (minimal cuts). An orientation $\Ocal$ of the edges of $G$ is {\em $(\sigma,\sigma^*)$-compatible} if every directed cycle (respectively, cocycle) of $\Ocal$ is oriented according to $\sigma$ (respectively, $\sigma^*$).

\begin{theorem} \cite[Theorem 1.5.1]{BBY} \label{thm:BBY}
Let $G$ be a connected graph, and fix an acyclic cycle signature $\sigma$ and an acyclic cocycle signature $\sigma^*$. Given a spanning tree $T$, let $\Ocal(T)$ be the orientation of $G$ in
which each $e\not\in T$ is oriented according to its orientation in $\sigma(C(T,e))$ and each $e\in T$ is oriented according to its orientation in $\sigma^*(C^*(T,e))$. Then the map $\beta_{\sigma,\sigma^*}:T\mapsto \Ocal(T)$ is a bijection between the set of spanning trees of $G$ and the set of $(\sigma,\sigma^*)$-compatible orientations of $G$. Here $C(T,e)$ (respectively, $C^*(T,e)$) is the fundamental cycle (respectively, cocycle) of $e$ with respect to $T$.
\end{theorem}

While the description of the map $\beta_{\sigma,\sigma^*}$ is combinatorial, the proof of its bijectivity uses polyhedral geometry in an essential way. Roughly speaking, $\sigma$ induces a {\em fine} zonotopal tiling $\Sigma$ of the {\em graphical zonotope} $Z$ associated to $G$, in which cells of $\Sigma$ (which are parallelepipeds) canonically correspond to the spanning trees of $G$ and vertices of $\Sigma$ correspond to (a subset of) orientations of $G$; on the other hand, $\sigma^*$ induces a shifting direction ${\bf v}$ in the affine span of $Z$. Now $\beta_{\sigma,\sigma^*}$ coincides with the shifting map that maps each cell $Z(T)$ of $\Sigma$ to the unique vertex ${\bf u}_\Ocal$ of $\Sigma$ such that ${\bf u}_\Ocal+\epsilon{\bf v}$ is in the interior of $Z(T)$ for sufficiently small $\epsilon>0$.

The above definitions and statements work beyond graphs. In fact, in \cite{BBY} they were done in the setting of {\em regular matroids}. Moreover, \cref{thm:BBY} was proven in \cite{BBY} for {\em realizable} oriented matroids, using the same argument involving zonotopes and their tilings. However, it is not obvious how to further generalize the work to all oriented matroids as the geometric argument requires realizing the oriented matroid. In fact, even for realizable oriented matroids, the argument of \cite{BBY} applies only to some zonotopal tilings, not to arbitrary (fine) ones.

In this note we extend \cref{thm:BBY} to arbitrary oriented matroids and to arbitrary circuit (respectively, cocircuit) signatures of it induced by generic single-element liftings (respectively, extensions), while the zonotopal argument is replaced by an argument involving {\em oriented matroid programs}.

\begin{theorem} \label{thm:main}
Let $M$ be an oriented matroid, and let $M',\widetilde{M}$ be a generic single-element extension and a generic single-element lifting of $M$, respectively. Let $\sigma^*$ (respectively, $\sigma$) be the cocircuit (respectively, circuit) signature associated to $M'$ (respectively, $\widetilde{M}$). Given a basis $B$, let $\Ocal(B)$ be the orientation of $M$ in which we orient each $e \not\in B$ according to its orientation in $\sigma(C(B,e))$ and each $e \in B$ according to its orientation in $\sigma^*(C^*(B,e))$. Then the map $\beta_{\sigma,\sigma^*}:B \mapsto \Ocal(B)$ gives a bijection between the set of bases of $M$ and the set of $(\sigma,\sigma^*)$-compatible orientations of $M$.
\end{theorem}

We explain the intuition of our proof of \cref{thm:main} here. By the topological representation theorem of Folkman and Lawrence \cite{FL_TRT} (which is also the reason we call our bijections {\em topological bijections}), we can represent the lifting $\widetilde{M}$ (together with the distinguished element $g$) as an {\em affine pseudosphere arrangement} in which each region represents a $\sigma$-compatible orientation of $M$, see \cref{fig:PSA}. In the realizable case, such arrangement can be thought as the dual of the zonotopal tiling used in \cite{BBY}; this phenomenon is related to the Bohne--Dress theorem on single-element liftings of realizable oriented matroids \cite{Bohne_thesis, RZ_BD_thm}.

\begin{figure}
\centering
\includegraphics[width=0.7\textwidth]{PSA.png}
\caption{The affine pseudosphere arrangement of the graphical oriented matroid $M$ of $K_3$ (the three curves represent the three elements of $M$) together with the extra element $g$ (the circle ``at infinity''). The regions are labeled by ($\sigma$-compatible) orientations of $M$ (i.e., orientations of $K_3$). The arrangement is dual to a zonotopal tiling of the zonotope associated to $M$.}
\label{fig:PSA}
\end{figure}

Now the distinguished element $f$ of the extension $M'$ can be included to the picture as an ``increasing direction'' or ``objective function'', with respect to which we consider the optimum of each region. We will prove that the regions whose optima are {\em bounded}, i.e., not lying on $g$, are precisely the $(\sigma,\sigma^*)$-compatible orientations. Since the extension $M'$ is generic, the optima are vertices; since the lifting $\widetilde{M}$ is generic, each such vertex is the intersection of pseudospheres that form a basis of $M$. In this way, we can associate each $(\sigma,\sigma^*)$-compatible orientation with a basis of $M$. We will prove that this map coincides with $\beta_{\sigma,\sigma^*}$ and is a bijection, finishing the proof; see \cref{fig:OMP}.

\begin{figure}
\centering
\includegraphics[width=0.7\textwidth]{OMP.png}
\caption{The new curve represents the element $f$ in a generic single-element extension. There are three regions whose optima with respect to $f$ are bounded, and each of these optima is the intersection of curves (elements of $M$) that form a basis of $M$ (a spanning tree of $K_3$).}
\label{fig:OMP}
\end{figure}

We mention a few similar results in the literature. A classical theorem of Greene and Zaslavsky states that the number of bounded regions in an affine pseudosphere arrangement equals the {\em beta invariant} of the corresponding matroid, regardless of the choice of $g$ \cite{GZ_HPZono}. Our \cref{thm:main} can be thought as counting regions with respect to another type of boundedness, and again the count is independent of the choice of $f$ (as long as the choice is generic). More generally, given a {\em strong map} between oriented matroids $M_1\rightarrow M_2$ on the same ground set, Las Vergnas gave a formula to count the number of orientations that are acyclic in $M_1$ and totally cyclic in $M_2$ \cite{LV_ATCO}. \cref{thm:main} has a similar flavour in view of \cref{lem:general_CCMO}, although we note that the map $\tilde{M}\rightarrow M'$ is not a strong map in general; indeed, while an extension followed by a contraction of the new elements gives rise to a strong map, $\tilde{M}\rightarrow M'$ can be thought of (by \cref{lem:common_ex_lift}) as a single-element extension followed by contracting a {\em different} element (or equivalently, the map is a contraction followed by an extension).

In \cref{sec:connection}, we will elaborate more on an interesting interpretation of \cref{thm:main} using the notions of {\em orientation activity} and {\em activity classes} of Gioan and Las Vergnas \cite{GLV_AB2b}. When both $M'$ and $\widetilde{M}$ are {\em lexicographic} with respect to the same data, a $(\sigma,\sigma^*)$-compatible orientation is called a {\em circuit-cocircuit minimal orientation} or an {\em active-fixed and dual-active fixed (re)orientation} in the literature. So our theorem provides a new bijective proof that the number of these (re)orientations equals the number of bases, i.e., $T_M(1,1)$. As a corollary, the number of {\em activity classes} also equals $T_M(1,1)$. This suggests the possibility that the notion of orientation activity might be extended beyond lexicographic data, at least in special cases.

\section{Preliminaries}

We assume the reader is familiar with the basic definitions in oriented matroid theory, and we refer to \cite{BLSWZ_book} for details and notation. Let $M$ be an oriented matroid on ground set $E$. The set of bases of $M$ will be denoted by $\Bcal(M)$, and the set of signed circuits (respectively, signed cocircuits) of $M$ will be denoted by $\Ccal(M)$ (respectively, $\Ccal^*(M)$). The support of a signed subset $X$ will be denoted by $\underline{X}$, and the underlying matroid of an oriented matroid $M$ will be denoted by $\underline{M}$.

\begin{definition}
An oriented matroid $M'$ is a {\em single-element extension} of $M$ if the ground set of $M'$ is $E\sqcup\{f\}$ for some new element $f$ and $M=M'\setminus \{f\}$. Dually, $\widetilde{M}$ is a {\em single-element lifting} of $M$ if the ground set of $\widetilde{M}$ is $E\sqcup\{g\}$ for some new element $g$ and $M=\widetilde{M}/\{g\}$.
\end{definition}

Let $M'$ be a single-element extension of $M$. For every signed cocircuit $D$ of $M$ there exists a unique signed cocircuit $D'$ of $M'$ such that $D'|_E=D$. Therefore we can define a map\footnote{In other literature, such a map is simply called a signature, but since we have been using the latter term with a different meaning, we will abuse terminology slightly here.} $\hat{\sigma}^*:\Ccal^*(M)\rightarrow \{+,0,-\}$ associated to the extension by setting $\hat{\sigma}^*(D):=D'(f)$. We say $\hat{\sigma}^*$ is {\em generic} if its image is $\{+,-\}$. In such case, $\sigma^*$ induces a {\em cocircuit signature} of $M$ that sends each cocircuit $\underline{D}$ of $\underline{M}$ to one of the two signed cocircuits of $\Ccal^*(M)$ supported on $\underline{D}$, namely the one in which $\hat\sigma^*$ is positive (that is, the one that extends to have $f$ on its positive side). Dually, every generic single-element lifting induces a {\em circuit signature} that sends each circuit of $\underline{M}$ to the signed circuit of $M$ with that support that extends to have $g$ in its positive side. An observation is that such construction of signatures generalizes the notion of acyclic signatures in \cite{BBY}, hence \cref{thm:main} is indeed a generalization of \cref{thm:BBY}.

\begin{proposition}
Every acyclic circuit (respectively, cocircuit) signature of a realizable oriented matroid is a circuit signature induced by some generic single-element lifting (respectively, extension). In fact, they correspond  precisely to the realizable liftings (respectively, extensions).
\end{proposition}

An {\em orientation} of $M$ is a map $\Ocal:E\rightarrow\{+,-\}$. $\Ocal$ is {\em compatible} with a signed circuit or cocircuit $C$ if $\Ocal(e)=C(e)$ for every $e\in\underline{C}$. We often interpret an orientation as a {\em reorientation} $_{-A}M$ of $M$ along a subset $A\subset E$ of elements. This is equivalent to our definition, by letting $\Ocal(e) = -$ if and only if $e\in A$; in this description $\Ocal$ is compatible with $C$ if $C^- = \underline{C} \cap A$. A circuit or cocircuit $C\subset E$ is {\em compatible} with $\Ocal$ if one of the signed versions of $C$ is compatible with $\Ocal$.

\begin{definition} \label{def:CCMO}
Let $\sigma$ (respectively, $\sigma^*$) be the circuit (respectively, cocircuit) signature induced by some generic single-element lifting $\widetilde{M}$ (respectively, extension $M'$). Then an orientation $\Ocal$ of $M$ is {\em $(\sigma,\sigma^*)$-compatible} if every signed circuit (respectively, cocircuit) compatible with $\Ocal$ is oriented according to $\sigma$ (respectively, $\sigma^*$). The set of $(\sigma,\sigma^*)$-compatible orientations of $M$ is denoted by $\rchi(M;\sigma,\sigma^*)$.
For an orientation $\Ocal$ of $M$, $\Ocal'_-$ is the orientation of $M'$ such that $\Ocal'_-|_E=\Ocal$ and $\Ocal'_-(f)=-$; dually, $\widetilde{\Ocal}_-$ is the orientation of $\widetilde{M}$ such that $\widetilde{\Ocal}_-|_E=\Ocal$ and $\widetilde{\Ocal}_-(g)=-$.
\end{definition}

\section{Proof of the Main Result}

Throughout this section, $M$ will be an oriented matroid on ground set $E$, and $M'$ (respectively, $\widetilde{M}$) will be a generic single-element extension (respectively, lifting) of $M$ on ground set $E\sqcup\{f\}$ (respectively, $E\sqcup\{g\}$).

\cref{thm:main} will be deduced from the following theorem.

\begin{theorem} \label{thm:main_actual}
For every $\Ocal\in\rchi(M;\sigma,\sigma^*)$, there exists a unique basis $B\in\Bcal(M)$ such that $B\cup\{f\}$ is a circuit compatible with $\Ocal'_-$ and $(E\setminus B)\cup\{g\}$ is a cocircuit compatible with $\widetilde{\Ocal}_-$.
\end{theorem}

As explained in the introduction, such a basis corresponds to the optimum (with respect to $f$) of the region corresponding to $\Ocal$ in the pseudosphere arrangement.

We start with a few lemmas.

\begin{lemma} \cite[Lemma 1.10]{Santos_book} \label{lem:common_ex_lift}
There exists an oriented matroid $\widetilde{M}'$ on ground set $E\sqcup\{f,g\}$ such that $M'=\widetilde{M}'/\{g\}$ and $\widetilde{M}=\widetilde{M}'\setminus \{f\}$.
\end{lemma}

\begin{lemma} \label{lem:generic_ex_circuit}
The set of circuits of $M'$ containing $f$ is $\{B\cup\{f\}:B\in\Bcal(M)\}$. Dually, the set of cocircuits of $\widetilde{M}$ containing $g$ is $\{(E\setminus B)\cup\{g\}:B\in\Bcal(M)\}$.
\end{lemma}

\begin{proof}
Let $B\in\Bcal(M)$. We first claim that $B$ is also a basis of $M'$. Since every circuit of $M'$ not containing $f$ is a circuit of $M$, $B$ is independent in $M'$; since every circuit of $M$ is a circuit of $M'$, $B\cup\{e\}$ is dependent in $M'$ for any $e\in E\setminus B$. So if $B$ is not a basis of $M'$, it must be the case that $X:=B\cup\{f\}$ is a basis of $M'$. In such case, $B=X\setminus\{f\}$ avoids the fundamental cocircuit $D'$ of $f$ with respect to $X$ in $M'$. Since $M'$ is generic, $f$ is not an isthmus and $D'\setminus\{f\}$ contains a cocircuit $D''$ of $M$, now $B$ avoids the cocircuit $D''$ in $M$, contradicting the basic property of bases.

Next we claim that the fundamental circuit $C'$ of $f$ with respect to $B$ is the whole of $X$. Suppose not, pick an arbitrary $e\in X\setminus C'$ and let $D$ be the fundamental cocircuit of $e$ with respect to $B$ in $M$. On one hand, $D':=D\cup\{f\}$ is a cocircuit of $M'$ as the extension is generic, so $D'$ must be the fundamental cocircuit of $e$ with respect to $B$ in $M'$. On the other hand, since $e\not\in C'=C(B,f)$, $f$ cannot be in $D'=C^*(B,e)$, a contradiction. This shows $\{B\cup\{f\}:B\in\Bcal(M)\}\subset\Ccal(M')$.

Conversely, let $C'\in\Ccal(M')$ be a circuit containing $f$. Then $Y:=C'\setminus\{f\}$ is independent in $M'$ thus in $M$. If $Y$ is not a basis of $M$, then it is properly contained in some $B\in\Bcal(M)$, but by the above containment, $B\cup\{f\}$ is a circuit of $M'$ properly containing $C'$, a contradiction. The dual statement can be proven similarly.
\end{proof}

\begin{lemma} \label{lem:general_CCMO}
An orientation $\Ocal$ of $M$ is $\sigma^*$-compatible if and only if $\Ocal'_-$ is totally cyclic. Dually, $\Ocal$ is $\sigma$-compatible if and only if $\widetilde{\Ocal}_-$ is acyclic.
\end{lemma}

\begin{proof}
Suppose $\Ocal'_-$ is compatible with some signed cocircuit $D'$. By \cite[Proposition 7.1.4 (ii)]{BLSWZ_book}, $D:=D'|_E$ is either (i) a signed cocircuit of $M$, in which $f\in\underline{D'}$, or (ii) equal to the conformal composition $D_1\circ D_2$ of signed cocircuits of $M$, in which $\sigma^*(D_1)=-\sigma^*(D_2)\neq 0$. For case (i), $D$ is a signed cocircuit compatible with $\Ocal$, but it is not compatible with $\sigma^*$ as $D'(f)=\Ocal'_-(f)=-$; for case (ii), both $D_1,D_2$ are compatible with $\Ocal$, but exactly one of them is not compatible with $\sigma^*$ as $\sigma^*(D_1)=-\sigma^*(D_2)$.

Conversely, if $D$ is a signed cocircuit compatible with $\Ocal$ but not $\sigma^*$, then $(D\ -)$ is a signed cocircuit of $M'$ that is compatible with $\Ocal'_-$, hence $\Ocal'_-$ is not totally cyclic. The dual statement can be proven similarly.
\end{proof}

Using the above lemmas, we can give an alternative description of the map $\beta_{\sigma,\sigma^*}$, matching the statement of \cref{thm:main_actual}.

\begin{proposition} \label{prop:beta_EL_pos}
Let $B$ be a basis of $M$ and let $\Ocal=\beta_{\sigma,\sigma^*}(B)$. Then $B\cup\{f\}$ is a circuit compatible with $\Ocal'_-$ and $(E\setminus B)\cup\{g\}$ is a cocircuit compatible with $\widetilde{\Ocal}_-$.
\end{proposition}

\begin{proof}
By \cref{lem:generic_ex_circuit}, $X:=B\cup\{f\}$ is a circuit of $\underline{M'}$. Denote by $C$ the signed circuit of $M'$ whose support is $X$ and satisfies $C(f)=-$. For every $e\in B$, let $D_e$ be the fundamental cocircuit of $e$ with respect to $B$ in $M$, oriented according to $\sigma^*$. By the definition of $\sigma^*$, the signed subset $D_e':=(D_e\ +)$ is a signed cocircuit of $M'$, and $X\cap \underline{D_e'}=\{e,f\}$. By the orthogonality of signed circuits and cocircuits as well as the fact that $D_e'(f)=-C(f)$, we must have $\Ocal(e)=D_e(e)=D_e'(e)=C(e)$. Therefore $X$ is oriented as $C$ in $\Ocal'_-$ and thus a compatible circuit. The second statement is the dual of the first one.
\end{proof}

Now we show that the image of $\beta_{\sigma,\sigma^*}$ is contained in the set of $(\sigma,\sigma^*)$-compatible orientations.

\begin{proposition} \label{prop:EL_pos_CCM}
Let $\Ocal$ be an orientation of $M$. If there exists a basis $B\in\Bcal(M)$ such that $B\cup\{f\}$ is a circuit compatible with $\Ocal'_-$ and $(E\setminus B)\cup\{g\}$ is a cocircuit compatible with $\widetilde{\Ocal}_-$, then $\Ocal\in\rchi(M;\sigma,\sigma^*)$.
\end{proposition}

\begin{proof}
By \cref{lem:general_CCMO}, it suffices to show that $\Ocal'_-$ is totally cyclic and $\widetilde{\Ocal}_-$ is acyclic. Suppose $D$ is a signed cocircuit compatible with $\Ocal'_-$. Since $B$ is also a basis of $M'$ (cf. the proof of \cref{lem:generic_ex_circuit}), $X:=\underline{D}\cap B$ is non-empty, but then $X$ will be simultaneously in the circuit part and cocircuit part of $\Ocal'_-$, contradicting \cite[Corollary 3.4.6]{BLSWZ_book}. The dual statement can be proven similarly.
\end{proof}

Finally we prove \cref{thm:main} via proving \cref{thm:main_actual}.

\begin{proof}[Proof of \cref{thm:main_actual}]
``Uniqueness''. Suppose both $B_1$ and $B_2$ are bases satisfying the condition. Let $C_1,C_2$ be the signed circuits of $M'$ obtained from restricting $\Ocal'_-$ to $B_1\cup\{f\}$ and $B_2\cup\{f\}$, respectively; let $D_1,D_2$ be the signed cocircuits of $\widetilde{M}$ obtained from restricting $\widetilde{\Ocal}_-$ to $(E\setminus B_1)\cup\{g\}$ and $(E\setminus B_2)\cup\{g\}$, respectively. Let $\widetilde{M}'$ be the oriented matroid containing both $M'$ and $\widetilde{M}$ as guaranteed by \cref{lem:common_ex_lift} and consider the lift $\widetilde{C_1}$ of $C_1$ in $\widetilde{M}'$.

Case I: $\widetilde{C_1}(g)=+$. Let $D'_1,D'_2$ be the extensions of $D_1,D_2$ in $\widetilde{M}'$. We must have $D'_1(f)=D'_2(f)=-$ by orthogonality, which in turn forces the lift  $\widetilde{C_2}$ of $C_2$ to take value $+$ at $g$. Apply the circuit elimination axiom to $\widetilde{C_1}$ and $-\widetilde{C_2}$ and eliminate $f$. Denote by $C$ the resulting signed circuit. We have $\underline{C}\cap\underline{D'_1}\subset (B_2\setminus B_1)\cup\{g\}$, but $C$ is conformal with $-D'_1$ over $B_2\setminus B_1$ as $D'_1|_{B_2\setminus B_1}=\Ocal|_{B_2\setminus B_1}=C_2|_{B_2\setminus B_1}$, so $C(g)=D'_1(g)=-$ by orthogonality. However, the same orthogonality argument applied to $C$ and $D'_2$ implies that $C(g)=-D'_2(g)=+$, a contradiction.

Case II: $\widetilde{C_1}(g)=-$. The analysis is similar to Case I.

Case III: $\widetilde{C_1}(g)=0$. This case is impossible as well, as $\widetilde{C_1}$ cannot be orthogonal to $D'_1,D'_2$ in the first place.\\

``Existence''. Let $\Ocal\in\rchi(M;\sigma,\sigma^*)$. By reorienting $M$ if necessary, we may assume $\Ocal\equiv +$. For the sake of matching convention in the literature, we also reorient $f,g$ in $\widetilde{M}'$, so the all positive orientation $\Ocal'_+$ of $M'$ is totally cyclic and the all positive orientation $\widetilde{\Ocal}_+$ is acyclic by \cref{lem:general_CCMO}. Now we consider the {\em oriented matroid program} $\Pcal:=(\widetilde{M}', g, f)$ \cite[Chapter 10]{BLSWZ_book}.

$\Pcal$ is both {\em feasible} and {\em bounded} from our assumption on $\widetilde{\Ocal}_+$ and $\Ocal'_+$: $\widetilde{\Ocal}_+$ itself is a positive covector of $\widetilde{M}$, which corresponds to a (full-dimensional) feasible region; any positive circuit of $M'$ whose support is of the form $B\cup\{f\}, B\in\Bcal(M)$ provides a bounded cone $B$ containing the feasible region. By the main theorem of oriented matroid programming \cite[Theorem 10.1.13]{BLSWZ_book}, $\Pcal$ has an optimal solution $Y$, which is a covector of $\widetilde{M}'$.

By definition, $Y$ is {\em feasible} and {\em optimal}, i.e., $Y(g)=+$, $Y|_E$ is non-negative, and $Y\circ Z|_E$ is not non-negative for every covector $Z$ (of $\widetilde{M}'$) that is $0$ at $g$ and $+$ at $f$. Since $Y$ is a covector containing $g$ in $\widetilde{M}'$, $Y\setminus\{f\}$ is a covector of $\widetilde{M}$ containing $g$. So $\underline{Y}\setminus\{f\}$ contains a cocircuit (of $\underline{\widetilde{M}}$), whose support is of the form $(E\setminus B_0)\cup\{g\}$ for some $B_0\in\Bcal(M)$ by \cref{lem:generic_ex_circuit}. If the containment is proper, then $\underline{Y}\setminus\{f\}$ contains some cocircuit $Z_0$ of $\underline{M}$. Since the extension is generic, the extension $Z_0'$ of $Z_0$ in $M'$ contains $f$. Without loss of generality, we may identify $Z_0'$ as the signed cocircuit of $M'$ (hence $\widetilde{M}'$) in which $Z_0'(f)=+$. Now we have a contradiction as $Y\circ Z_0|_E$ is non-negative. Therefore $\underline{Y}\setminus\{f\}=(E\setminus B_0)\cup\{g\}$, and it is a cocircuit of $\underline{\widetilde{M}}$. We claim that $B_0$ is the basis of $M$ we want.

The second assertion is immediate as $Y|_{E\cup\{g\}}$ is non-negative. By \cref{lem:generic_ex_circuit}, $B_0\cup\{f\}$ is a circuit of $\underline{M'}$. Denote by $X$ the signed circuit of $M'$ supported on $B_0\cup\{f\}$ such that $X(f)=+$, it remains to show $X$ is non-negative. Suppose $X(e)=-$. Let $Z_e$ be the fundamental cocircuit of $e$ with respect to $B_0$ in $\underline{M}$, and let $Z_e'$ be its extension in $\underline{M'}$. Since the extension is generic, $f\in\underline{Z_e'}$, and again we can abuse notation to identify $Z_e'$ as the signed cocircuit of $M'$ (hence $\widetilde{M}'$) in which $Z_e'(f)=+$. From the choice of $Z_e'$, $\underline{Z_e'}\cap\underline{X}=\{e,f\}$, so $Z_e'(e)=+$ by orthogonality. In particular, $Y\circ Z_e|_E$ is non-negative, which is a contradiction. Therefore $B_0\cup\{f\}$ is a positive circuit of $\Ocal'_+$ as well.
\end{proof}

\begin{proof}[Proof of \cref{thm:main}]
By \cref{prop:beta_EL_pos,prop:EL_pos_CCM}, every orientation in the image of $\beta_{\sigma,\sigma^*}$ is $(\sigma,\sigma^*)$-compatible. Injectivity follows from \cref{prop:beta_EL_pos} and the uniqueness part of \cref{thm:main_actual}. Surjectivity follows from \cref{prop:beta_EL_pos} and the existence part of \cref{thm:main_actual}.
\end{proof}

\section{Relation with Orientation Activity} \label{sec:connection}

A set of {\em lexicographic data} $(<,s)$ of $M$ consists of a total ordering $<$ of $E$ together with a choice of sign $s(e)\in\{+,-\}$ for every element $e$ of $E$. We fix an arbitrary set of such data for the rest of the discussion.

Following \cite{LV_Activity}, an element of $E$ is {\em internally (respectively, externally) active} in an orientation $\Ocal$ if it is the minimal element in some signed cocircuit (respectively, circuit) compatible with $\Ocal$. The {\em internal (respectively, external) activity} $\iota(\Ocal)$ (respectively, $\epsilon(\Ocal)$) is the number of internally (respectively, externally) active elements in $\Ocal$.

Now let $e_{1}<\ldots<e_{\iota}$ (respectively, $e'_{1}<\ldots<e'_{\epsilon}$) be the elements that are internally (respectively, externally) active in $\Ocal$. For $k=1,2,\ldots,\iota$, denote by $F_k$ the union of (the supports of) all signed cocircuits compatible with $\Ocal$ whose minimal elements are at least $e_k$; dually, for $k=1,2,\ldots,\epsilon$, denote by $F'_k$ the union of (the supports of) all signed circuits compatible with $\Ocal$ whose minimal elements are at least $e'_k$. The partition $\mathcal{F}=(F_{\iota}, F_{\iota-1}\setminus F_{\iota},\ldots, F_1\setminus F_2; F'_{\epsilon},F'_{\epsilon-1}\setminus F'_{\epsilon},\ldots, F'_1\setminus F'_2)$ of $E$ is the {\em active partition} of $\Ocal$. The {\em activity class} of an orientation is the set of orientations obtained from reversing any union of components from $\mathcal{F}$. It can be proven that any two orientations in an activity class share the same active partition (hence the same internal and external activities) \cite{GLV_AB2a}, so activity classes are well-defined and they partition the set of orientations of $M$.

On the other hand, a set of lexicographic data induces a circuit signature $\sigma_{(<,s)}$ (a dual construction gives a cocircuit signature): let $\underline{C}$ be a circuit of $\underline{M}$, and let $e$ be the minimal element in $C$ with respect to $<$, then we set $\sigma_{(<,s)}(\underline{C})$ to be the unique signed circuit $C$ supported on $\underline{C}$ such that $C(e)=s(e)$. The lifting (respectively, extension) of $M$ given by that circuit (respectively, cocircuit) signature is the {\em lexicographic extension (respectively, lifting)} induced by that lexicographic data. If $\sigma$ and $\sigma^*$ are circuit and cocircuit signatures induced by the same lexicographic data, then a $(\sigma,\sigma^*)$-compatible orientation is called a {\em circuit-cocircuit minimal orientation} in \cite{Bac_PO} and an {\em active fixed and dual-active fixed (re)orientation} in \cite{GLV_AB2b}. We have the following simple observation relating these compatible orientations and activity classes.

\begin{proposition}
Suppose $\sigma$ (respectively, $\sigma^*$) is the circuit (respectively, cocircuit) signature induced by the lexicographic data we fixed. Then $\rchi(M;\sigma,\sigma^*)$ is a system of representatives of the activity classes of $M$.
\end{proposition}

\begin{proof}
Within an activity class, every component of the active partition of any (hence all) orientation contains exactly one active element, so there is a unique choice of reversal for each component to guarantee such element is oriented according to $s$. Therefore precisely one orientation within the class is $(\sigma,\sigma^*)$-compatible.
\end{proof}

\begin{example}
Both the single-element lifting in \cref{fig:PSA} and the single-element extension in \cref{fig:OMP} are induced by the lexicographic data shown in \cref{fig:lexi}.
\end{example}

\begin{figure}
\centering
\includegraphics[width=0.15\textwidth]{lexi.png}
\caption{A set of lexicographic data in $K_3$ that was used in \cref{fig:PSA} and \cref{fig:OMP}. We set $s$ to be all positive, and the reference orientations of edges are show in the diagram.}
\label{fig:lexi}
\end{figure}

As a corollary, topological bijections provide a new bijective proof of the following enumerative result.

\begin{corollary} \label{coro:act_class}
The number of activity classes of an oriented matroid $M$ equals $T_M(1,1)$.
\end{corollary}

We note that \cref{coro:act_class} also follows from the aforementioned works by Gioan and Las Vergnas on orientation activity and its relation with the Tutte polynomial. In particular, another bijective proof (using {\em active bijections}, in which an ordering of elements is essential) was given in \cite{GLV_Activity}. Our contribution, however, is to show that (at least) in terms of $T_M(1,1)$, the notion of ``activity'' can be extended beyond lexicographic data.

\acknowledgements{Work of S. Backman is supported by the Zuckerman STEM Postdoctoral Scholarship and DFG--Collaborative Research Center, TRR 109 ``Discretization in Geometry and Dynamics''. Work of F. Santos is supported by grant MTM2017-83750-P of the Spanish Ministry of Science and grant EVF-2015-230 of the Einstein Foundation Berlin, as well as the Clay Institute and the National Science Foundation (Grant No. DMS-1440140) while he was in residence at MSRI Berkeley, California during the Fall 2017 semester ``Geometric and Topological Combinatorics''. Work of C.H. Yuen is  supported by NWO Vici grant 639.033.514.}

%% 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}
