%% 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[final]{FPSAC2022}
%% 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}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{claim}{Claim}
\newtheorem{cjt}{Conjecture}
\newtheorem{sublemma}{Sublemma}


\theoremstyle{remark}
\newtheorem{rk}{Remark}

%\usepackage{lipsum}
%\usepackage{enumitem}
%\usepackage{caption}
%\usepackage{subcaption}

%\usepackage[dvipsnames]{xcolor}

\newcommand{\Ot}{\mathcal{O}}

\def\Se{S^e}
\def\So{S^o}

\def\cB{\mathcal{B}}
\def\cP{\mathcal{P}}
\def\cS{\mathcal{S}}
\def\cSe{\cS^e}
\def\cSo{\cS^o}

\def\bx{\overline{x}}
\def\by{\overline{y}}

\def\mue{\mu^e}
\def\muo{\mu^o}

%% define your title in the usual way
\title{Enumeration of Corner Polyhedra and 3-Connected Schnyder Labelings}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[\'E.~Fusy, E.~Narmanli, and G.~Schaeffer]{\'Eric Fusy\thanks{\href{mailto:eric.fusy@u-pem.fr}{eric.fusy@u-pem.fr}. Partially supported by ANR COMBIN\'E: ANR-19-CE48-0011.}\addressmark{1},
Erkan Narmanli\thanks{\href{erkan.narmanli@normalesup.org}{erkan.narmanli@normalesup.org}. Partially supported by ANR GATO: ANR-16-CE40-0009.} \addressmark{2},
\and Gilles 
Schaeffer\thanks{\href{gilles.schaeffer@lix.polytechnique.fr}{gilles.schaeffer@lix.polytechnique.fr}. Partially supported by ANR GATO: ANR-16-CE40-0009.}\addressmark{2}
}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}LIGM, CNRS, Universit\'e Gustave Eiffel, Champs-sur-Marne, France.\\ \addressmark{2}LIX, CNRS, \'Ecole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France.}

%% 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{We show that corner polyhedra and 3-connected Schnyder labelings 
  can be set in exact correspondance with (weighted) bi-modal models of
  quadrant walks via a bijection due to Kenyon, Miller, Sheffield and
  Wilson.

  Our approach leads to polynomial time enumeration algorithms, and to
  the determination of their exact asymptotic growth constants, which
  are rational.  We use a heuristic argument to compute explicit but
  conjectural polynomial corrections to these exponential behaviors,
  that suggest that the corresponding generating series are not
  D-finite.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{planar maps, orientations, bijections, exact and asymptotic enumeration}

%% 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{biblio_fpsac.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}\label{sec:intro}
This article is concerned with the enumerative properties of two
fascinating families of discrete geometric structures, corner polyhedra
and rigid orthogonal surfaces. Corner polyhedra,
see Figure~\ref{fig:corner_poly}(a), were introduced by Eppstein and
  Mumford \cite{eppstein2010steinitz} who were interested in the
  possibility to give an elegant characterization \emph{\`a la
    Steinitz} of the graphs that can be realized as 1-skeleton for certain classes of orthogonal polyhedra, while rigid orthogonal surfaces, see
  Figure~\ref{fig:schnyder_lab}(a), were considered by Felsner
    \cite{felsner2003geodesic} in relation with the order dimension of
    3-polytopes.

It turns out that these geometric structures can be described in a
very similar way by certain underlying combinatorial structures,
\emph{polyhedral orientations} for corner polyhedra, see Figure~\ref{fig:corner_poly}(b), and ($3$-connected) 
\emph{Schnyder labelings} for rigid orthogonal surfaces, see Figure~\ref{fig:schnyder_lab}(b). As
illustrated by Figure~\ref{fig:table}, and as already partially
observed by several authors, \emph{e.g.}~\cite{eppstein2010}, these
combinatorial counterparts are similar to those that were already observed for
horizontal/vertical contact segments and rectangular tilings.

After recalling in Section~\ref{models} the definition of polyhedral
orientations and Schnyder labelings, and how to recast them in terms
of bipolar orientations, we move on in Section~\ref{bij-tandem} to set
up exact correspondences with certain weighted bi-modal models of
so-called tandem quadrant walks via a bijection due to Kenyon, Miller, Sheffield
and Wilson \cite{kenyon2019bipolar}. The resulting correspondences,
stated as Claim~\ref{claim:poly} and Claim~\ref{claim:schnyder}, allow
us to describe in Section~\ref{enum} polynomial time algorithms to
count these structures, and moreover to determine in
Theorem~\ref{thm:growth_rates} their exact asymptotic growth constants,
see also Figure~\ref{fig:table}.

As can be observed in Figure~\ref{fig:table}, these results parallel
those for the number of plane bipolar orientations, and for the number of 
transversal structures.  However the analysis is made more difficult
by the fact that the tandem walks that we have to deal with have a
bimodal behavior: the step set available at a current point depends on
the parity of the ordinate of this point. This puts the complete
analysis of the asymptotic behavior out of reach of our current
understanding of these models, based on Denisov--Wachtel approach
\cite{denisov2015random}. Resorting to a plausible but conjectural
version of their argument we are able to state
Conjecture~\ref{cj:asympt} on the polynomial corrections, which would
imply that the associated series are not D-finite.

As mentioned in Figure~\ref{fig:table}, a nice final touch on the
emerging global picture is the possibility to recast these results in terms
of colored pseudoline contact systems (details on this, and complete proofs, will be provided in the forthcoming extended version~\cite{FNS}).
\begin{figure}
  \begin{center}\footnotesize
\begin{tabular}{|c|c|c|c|}
  \hline
 horizontal/vertical  & rectangular tilings  & corner polyhedra & rigid orthogonal\\
contact segments (\cite{Tamassia})   &  (\cite{kant1997regular})  & (\cite{eppstein2010steinitz}, Sec~\ref{sec:intro})          & surfaces (\cite{felsner2003geodesic}, Sec~\ref{sec:intro})\\\hline 
  separating decompositions & transversal structures  & polyhedral orientations & Schnyder labelings\\
  (\cite{de1995bipolar})
  & (\cite{kant1997regular,fusy2009transversal})   & (\cite{eppstein2010steinitz}, Sec~\ref{defs}) & (\cite{felsner2000convex}, Sec~\ref{defs})\\\hline
  plane bipolar  & $T$-transverse bipolar &  $P$-admissible bipolar & 
  $S$-transverse  bipolar  \\
    orientations (\cite{de1995bipolar}) & orientations (\cite{Na20}) & orientations (Sec~\ref{bipolar}) & orientations (Sec~\ref{bipolar})\\\hline
tandem walks & $T$-admissible tandem & $P$-admissible tandem & $S$-admissible tandem\\
(\cite{Na20})  & walks (\cite{Na20}) &  walks (Sec~\ref{subsec:application}) &  walks (Sec~\ref{subsec:application})\\\hline
free bicolored & rigid bicolored & free tricolored  & rigid tricolored \\
contact-systems (\cite{FNS}) & contact-systems (\cite{FNS}) & contact-systems (\cite{FNS}) & contact-systems (\cite{FNS}) \\\hline
$\asymp 8^n$ (\cite{baxter2001dichromatic}) & $\asymp (27/2)^n$ (\cite{Na20}) & $\asymp (9/2)^n$  (Sec~\ref{enumasympt}) & $\asymp (16/3)^n$ (Sec~\ref{enumasympt})\\\hline
\end{tabular}
\end{center}
\caption{Four parallel families of structures.\label{fig:table}} 
\end{figure}


\section{Presentation of the two models}\label{models}
\subsection{Definitions}\label{defs}
A \emph{planar map} is a connected multigraph embedded on the oriented sphere up to o\-ri\-en\-ta\-tion-preserving homeomorphism.  It is \emph{rooted} by marking a corner, whose incident face is taken as the outer face in planar representations. Vertices and edges are called \emph{inner} or \emph{outer} depending on whether they are incident to the outer face or not. 
A map is called \emph{Eulerian} if its vertices have even degree, then the faces can be uniquely bicolored in light and dark faces so that the outer face is light (any edge has a dark face on one side and a light face on the other side). Dually, a map is  bipartite if and only if all faces have even degree, then the vertex bicoloration is unique, up to choosing the color of a given vertex.  

\begin{figure}
\begin{center}
\includegraphics[width=15cm]{figures/corner_poly}
\end{center}
\vspace{-1em}
\caption{From a corner polyhedron to an Eulerian triangulation endowed with a polyhedral orientation (extremal corners are indicated in violet, there are two such corners at each inner vertex and at each light inner face).}
\label{fig:corner_poly}
\vspace{-1em}
\end{figure}


A \emph{triangulation} is a map where all faces have degree $3$. It is known that a triangulation is 3-colorable if and only if it is Eulerian. In that case, the coloration of vertices (say in blue, green, red) is unique once the colors around a given triangle are fixed. If the triangulation is rooted, we take the convention that the root-vertex is red, and the outer vertices are colored red, green, blue in clockwise order around the outer face (\textit{i.e.}, walking along the outer contour with the outer face on the left). Note that every edge is also canonically colored red, green, or blue: it receives the color it misses (\textit{e.g.}, an edge connecting a green vertex and a blue vertex is colored red). 
In an orientation of a planar map, a corner $c=(v,e_1,e_2)$ is called \emph{lateral} if exactly one of $e_1,e_2$ is ingoing at $v$ (the other one being outgoing), it is called \emph{extremal} otherwise (either $e_1,e_2$ are both ingoing or both outgoing at $v$). 
For $T$ a rooted Eulerian triangulation, a \emph{polyhedral orientation} of $T$ is an orientation of  $T$ such that (see Figure~\ref{fig:corner_poly}(c) for an example):
\begin{enumerate}[label={(PO\arabic*)}]
\item There is no extremal corner at the outer vertices, and the outer contour is a cw cycle. 
\item Every inner vertex is incident to exactly two extremal corners, and all the extremal corners are incident to light faces (hence dark face contours are either cw or ccw).% (hence the contours of the dark faces are directed cycles, either cw or ccw), .
\end{enumerate}
\begin{rk}
Based on a counting argument, it can be checked that there must be exactly two extremal corners in every inner light face. 
 %Furthermore, given that the triangulation is 3-colorable, we can see that it implies a strict color alternance of the edges around a given vertex.
\end{rk}
\begin{rk}
  Not every Eulerian triangulation admits a polyhedral orientation: in
  fact it is the case if and only if all its red/blue/green ccw triangles  are
  facial, as first shown in~\cite{eppstein2010steinitz}. These so-called \emph{corner triangulations} are enumerated in \cite{dervieux}.
  \end{rk}
From now on, we call \emph{polyhedral orientation} a (corner) triangulation endowed with a polyhedral orientation.


\begin{figure}[t]
\begin{center}
\includegraphics[width=13cm]{figures/schnyder_lab}
\end{center}
\vspace{-1em}
\caption{From a rigid orthogonal surface to a $(6,4)$-dissection endowed with a Schnyder labeling.}
\label{fig:schnyder_lab}
\vspace{-1em}
\end{figure}

A \emph{$(6,4)$-dissection} is a planar map $D$ whose outer face is a simple cycle of length $6$, and whose inner faces have degree $4$. Such a map is bipartite, and if rooted (which is assumed here) the vertex-bicoloration (in black and white vertices) is the unique one such that the root-vertex is white. 
The outer vertices are labeled $R,G,B,R,G,B$ in ccw order around the outer face, starting with the root-vertex. An outer vertex is called \emph{isolated} if it has degree $2$ (\textit{i.e.}, is not incident to an inner edge). 
A \emph{Schnyder labeling} of $D$ is a coloration of the inner edges of $D$ in blue, green, red, such that (see Figure~\ref{fig:schnyder_lab}(c)):
\begin{enumerate}[label={(SL\arabic*)}]
\item The two outer vertices labeled $R$ (resp.\ $B, G$) have their incident inner edges red (resp.\ blue, green).
\item The edges at each inner vertex form, in cw order, 3 non-empty groups of red, green and blue edges, respectively.  
\end{enumerate}
\begin{rk}
  It is known~\cite{felsner2000convex,fusy2008dissections} that a $(6,4)$-dissection admits a Schnyder labeling if and only if it has no multiple edge and every $4$-cycle delimits a face. These dissections are counted bijectively in~\cite{fusy2008dissections}.
  \end{rk}
\begin{rk}
One can classically associate to $D$ a planar (essentially $3$-connected) map $M$, which is obtained from $D$ by adding in each inner face an edge that connects the two opposite white vertices, and then erasing all edges and black vertices of $D$.
Via this mapping, our definition of Schnyder labelings matches the one of Felsner~\cite{felsner2000convex}.
\end{rk}
From now on, we call \emph{Schnyder labeling} a $(6,4)$-dissection endowed  with a Schnyder labeling.





\subsection{Encoding by (constrained, decorated) plane bipolar orientations}\label{bipolar}
%For a rooted planar map, with $S$ the root-vertex and $N$ a secondary marked outer vertex, 
A \emph{plane bipolar orientation} is a rooted planar map endowed with an acyclic orientation with a unique source $S$ at the root-vertex, and a unique sink $N$ incident to the outer face. It is known~\cite{de1995bipolar} that a plane bipolar orientation is characterized by the following local properties (for orientations with $S$ as a  
source and $N$ as a sink), illustrated in Figure~\ref{fig:bipolar_rules}:
\begin{itemize} 
\item[(B):] Apart from $\{S,N\}$, each vertex has two lateral corners (so the incident edges form two groups: ingoing and outgoing edges).
\item[(B'):] Each face (including the outer one) has two extremal corners, so that the contour is partitioned into a left lateral path and a right lateral path that share their origins and ends, which are called the \emph{bottom vertex} and \emph{top vertex} of the face.
\end{itemize}
 The \emph{type} of a face is the integer pair $(i,j)$ such that the left (resp.\ right) lateral path of the face has length $i+1$ (resp.~$j+1$). The \emph{outer type} of the orientation is the type of the outer face.
%\begin{rk}
 %   Using lateral and extremal corners, we see that Property~(B) states that every vertex has two lateral corners and~(B') states that every face has exactly two extremal corners (at the bottom and the top vertices), see Figure~\ref{fig:bipolar_rules}.
%\end{rk}
\begin{figure}[t]
  \begin{center}
    \includegraphics[width=0.8\textwidth]{figures/bipolar_rules.pdf}
  \end{center}
\vspace{-1em}
    \caption{Local rules for plane bipolar orientation, (B) on the left and~(B') on the right, and their translation in terms of lateral and extremal corners.}
    \label{fig:bipolar_rules}
\vspace{-1em}
\end{figure}
If the underlying map of the orientation is bipartite, \textit{i.e.}, the type $(i,j)$ of every inner face is such that $i+j$ is even, then the vertex bicoloration is chosen such that $N$ is white. An inner face is called a \emph{blacktip face} (resp.\ \emph{whitetip face}) if its top vertex is black (resp.\ white). 

A plane bipolar orientation is called \emph{$P$-admissible} if it is bipartite, it has outer type $(0,k)$ for some even~$k\geq 2$, and the type $(i,j)$ of every blacktip (resp.\ whitetip) inner face is such that $i\geq 1$ (resp.\ $j\geq 1$). 

\begin{claim}\label{claim:poly}
Polyhedral orientations with $n$ inner vertices, among which $i$ are red, $j$ are blue, and $k$ are green, are in bijection with $P$-admissible plane bipolar orientations with~$n+1$ edges, $i+1$ white vertices, $j+1$ black vertices, and $k$ inner faces.
\end{claim}
From polyhedral orientations the bijection consist in removing all green vertices, see Figure~\ref{fig:poly_bijection} for an example.

\begin{figure}[t]
  \begin{center}
  \includegraphics[width=0.8\textwidth]{figures/p-admissible_poly-orientation_bijection.pdf}
  \end{center}
\vspace{-1em}
  \caption{On the left a polyhedral orientation (with dots at lateral corners), and on the right the corresponding~$P$-admissible plane bipolar orientation.}
  \label{fig:poly_bijection}
\vspace{-1em}
\end{figure}


An \emph{$S$-transverse plane bipolar orientation} is a bipartite planar map $M$ with outer degree~$6$, inner faces of degree $4$, and two types of edges: \emph{plain edges} that are directed, span all vertices of $M$, and form a plane bipolar orientation $X$ of outer type $(2,2)$; and \emph{transversal edges} that are undirected edges within the inner faces of $X$, such that each transversal edge within an inner face $f$ connects a black vertex (strictly) in the left lateral path of $f$ and a white vertex (strictly)  in the right lateral path of $f$; we also ask $X$ to have at least one inner face, and for all its inner faces to have (even) degree at least $6$.

\begin{claim}\label{claim:schnyder}
Schnyder labelings with $n$ inner faces, $i+1$ white vertices and $j+1$ black vertices, and whose two~$G$ outer vertices are non-isolated, are in bijection with $S$-transverse plane bipolar orientations with~$n+4$ vertices, among which $i+1$ are white and $j+1$ are black.
\end{claim}
The bijection from Schnyder labelings is defined as follows: orient the red edges (resp.\ the blue edges) from black to white (resp.\ from white to black), these become the plain edges, while the green edges become the transversal edges (see Figure~\ref{fig:claim_schnyder_example}).
\begin{figure}[t]
  \begin{center}
  \includegraphics[width=0.8\textwidth]{figures/polyedre_bijection.pdf}
  \end{center}
  \vspace{-1em} 
  \caption{On the left a Schnyder labeling (with non-isolated outer $G$ vertices), and on the right the corresponding~$S$-transverse plane bipolar orientation.}
  \label{fig:claim_schnyder_example}
\vspace{-1em}
\end{figure}

\begin{rk}
For enumerative purposes, the constraint that the two outer vertices labeled $G$ are non-isolated is mild. Indeed, if $s_n$ denotes the number of Schnyder labelings with $n$ inner faces (with $n\geq 2$), and $s_n'$ denotes the number of those where the two outer vertices labeled~$G$ are non-isolated, then  $s_n=s_n'+2s_{n-1}'+s_{n-2}'$ for $n\geq 4$ (the three terms correspond to having $0$, $1$, or $2$ isolated vertices among the two outer $G$).  
\end{rk}

\begin{rk}\label{rk:transvers}
Let $X$ be an $S$-transverse bipolar orientation and let $f$ be an inner face of $X$, with $q_0,\ldots,q_{m+1}$ the
quadrangular faces within $f$, ordered from bottom to top. Let $\gamma$ be the path from the first to the last black vertex
on the strict left boundary of $f$, and let $2\ell$ be its length. Let $\gamma'$ be the path from the first to the last white vertex
on the strict right boundary of $f$, and let $2r$ be its length.  
It is easy to see that for $h\in[1, m]$, $q_h$ either has two edges on $\gamma$ and none on $\gamma'$, or the opposite. We can thus attach to $f$ a word in $\frak{S}(o^\ell \overline{o}^r)$ giving the types of $q_1,\ldots,q_m$ ($o$ if the face has two edges on $\gamma$, $\overline{o}$ otherwise). It completely encodes the configuration of transversal edges within $f$, and any such word is a valid encoding. Hence the configuration can be encoded by an integer in $[1, \binom{\ell+r}{r}]$. 
%Note also that the degree of $f$ is $2\ell+2r+6$ in all cases (in particular, all inner faces of $X$ have degree at least $6$).
 \end{rk}

%\begin{rk}\label{rk:transvers}
%Let $X$ be an $S$-tranversed plane bipolar orientation and let $f$ be an inner face of $X$, with $q_0,\ldots,q_{m+1}$ the
%quadrangular faces within $f$, ordered from bottom to top. Let $\gamma_{L}$ be the path from the first to the last white vertex
%on the strict left boundary of $f$ (\textit{i.e.}, excluding the extremal vertices of $f$), and let $2k$ be its length. Let $\gamma_{R}$ be the path from the first to the last black vertex
%on the strict right boundary of $f$, and let $2\ell$ be its length.  
%It is easy to see that for $a\in[1, m]$, $q_a$ either has two edges on $\gamma_L$ and none on $\gamma_R$ or the opposite. We can thus attach to $f$ a word in $\frak{S}(L^kR^\ell)$ giving the types of $q_1,\ldots,q_m$. It completely encodes the configuration of transversal edges within $f$, and any such word is a valid encoding. Hence the configuration can be encoded by an integer in $[1, \binom{k+\ell}{k}]$.  
% \end{rk}

\section{Bijections with walks in the quadrant}\label{bij-tandem}

Similarly as in~\cite{Na20}, once our models have been set in bijection to certain models of plane bipolar orientations, they can be set in bijection to specific quadrant walks by specializing a bijection due to Kenyon, Miller, Sheffield and Wilson (shortly called the KMSW bijection), which we use as a bijective black box.

\subsection{KMSW bijection}


A \emph{tandem walk} is a walk on the lattice $\mathbb{Z}^2$, with steps in $\{(1,-1)\}\cup\{(-i,j)|\ i,j\geq 0\}$. A step that is not a SE step (\textit{i.e.}, a step of the form $(-i,j)$) is called a \emph{face-step}. 
%, its \emph{type} is the integer pair $(i,j)$. 
%The step $(-i,j)$ is said to have type $(i,j)$. 

\begin{thm}[\cite{kenyon2019bipolar}]
There is a bijection between plane bipolar orientations of outer type $(d,d')$ and tandem walks from $(0,d)$ to $(d',0)$ staying in the quadrant $\mathbb{N}^2$. For $X$ a plane bipolar orientations and $\pi$ the corresponding tandem walk, the number of edges of $X$ corresponds to one plus the length of $\pi$, each inner face of type $(i,j)$ in $X$ corresponds to a face-step $(-i,j)$ in $\pi$, and each non-pole vertex corresponds to a SE step of $\pi$. 
\end{thm}

\begin{rk}
The bijection is easy to specialize to the bipartite setting (we will use the bijection in this setting only). A plane bipolar orientation $X$ is bipartite if and only if in the corresponding walk, each face-step $(-i,j)$ is such that $i+j$ is even; such a tandem walk is called \emph{even}. Moreover, the non-pole white and black vertices of $X$ correspond to the SE steps that start at even $y$ and odd $y$, respectively (this is due to the property that the $y$ where the step starts indicates a path-length in $X$ between $N$ and the vertex corresponding to the step).   Similarly, whitetip inner faces and blacktip inner faces correspond to face-steps that start at even $y$ and at odd $y$, respectively, see Figure~\ref{fig:exemple_kmsw} for an example. 
\end{rk}
\begin{figure}[t]
    \begin{center}
        \includegraphics[width=0.6\textwidth]{figures/exemple_kmsw.pdf}
    \end{center}
\vspace{-1em}
    \caption{A bipartite plane bipolar orientation, and the corresponding even tandem walk through the KMSW bijection.}
    \label{fig:exemple_kmsw}
\vspace{-1em}
\end{figure}



\subsection{Application to the two models}\label{subsec:application}

We first specialize the KMSW bijection (in the bipartite setting) to the $P$-admissible bipolar orientations.  
A \emph{$P$-admissible tandem walk} is an even tandem walk where  every face-step $(-i,j)$ starting at even (resp.\ odd) $y$ has $j\geq 1$ (resp.\ $i\geq 1$). 
Via Claim~\ref{claim:poly} we obtain:

\begin{prop}
Polyhedral orientations are in bijection with $P$-admissible quadrant tandem walks starting at the origin and ending on the $x$-axis. If the polyhedral orientation has $n$ inner vertices, among which $a$ are red,  $b$ are blue, and $c$ are green, then the corresponding $P$-admissible tandem walk has length $n$, with $a$ SE steps starting at even $y$, $b$ SE steps starting at odd $y$, and $c$ face-steps. 
\end{prop}

We then specialize the KMSW bijection to the S-transverse plane bipolar orientations. For this (given Remark~\ref{rk:transvers}), we need a weighted terminology: a step $s$ in a tandem walk is said to be \emph{weighted} by $w\in\mathbb{N}$ if $s$ comes with an integer in $[1, w]$ (for the enumeration, the weights of the steps composing the walk have to be multiplied, those where no weight is indicated are implicitly assumed to have weight $1$). An \emph{$S$-admissible tandem walk} is defined as an even tandem walk such that every face-step $(-i,j)$ with even entries is of the form $i=2\ell+2,j=2r+2$ and is weighted by $\binom{\ell+r}{r}$,  every face-step $(-i,j)$ with odd entries and starting at even $y$ is of the form  $i=2\ell+1,j=2r+3$ and is weighted by $\binom{\ell+r}{r}$, and  every face-step $(-i,j)$ with odd entries and starting at odd $y$ is of the form $i=2\ell+3,j=2r+1$ and is weighted by $\binom{\ell+r}{r}$.    
Via Claim~\ref{claim:schnyder} and Remark~\ref{rk:transvers}, we obtain:

\begin{prop}\label{prop:schnyder-tandem}
Schnyder labelings whose two outer~$G$ vertices are non-isolated are in bijection with $S$-admissible tandem walks in the quadrant that start  at $(0,2)$ and end at $(2,0)$, and have length at least $3$ (\textit{i.e.}, have at least one face-step). If the Schnyder labeling has $n$ inner faces, with $a+1$ white vertices and $b+1$ black vertices, then the corresponding $S$-admissible tandem walk has $n+2$ SE steps, among which $a$ start at even $y$, and $b$ start at odd $y$. 
\end{prop}

\section{Enumerative results}\label{enum}
\subsection{Exact enumeration}\label{enumexact}
A system of two equations with two catalytic variables $x$, $y$ can
easily be written for the series $Q^e(t,x,y)$ and
$Q^o(t,x,y)$ of $P$-admissible tandem walks with even or odd final $y$
positions, along the lines for instance of \cite[Theorem 3]{Beat20}, and
the same can be done for $S$-admissible tandem walks. The resulting
equations are however somewhat cumbersome to manipulate and it turns
out to be more efficient to reduce the problem to small step walk
problems, in the spirit of \cite[Proposition~4]{Na20}, but taking into
account the final $y$ parity.

We start with Schnyder labelings, which lead to simpler recurrences due to the weights on face-steps:
\begin{prop}
Let $s_n$ denote the number of Schnyder labelings with $n$ inner faces. 
%$s'_n$ the number of $S$-admissible tandem walk from $(0,2)$ to $(2,0)$ with $n+2$ SE-steps. 
%, $s_{i,j}$ those having $i+1$ white vertices and $j+1$ black vertices.
Let moreover
$s^{\searrow}_n(i,j)$, and 
$s^{\nwarrow}_n(i,j)$ be given by the following recurrences:
\begin{align}
  s^{\searrow}_n(i,j)&=s^{\searrow}_{n-1}(i-1,j+1)+s^{\nwarrow}_{n-1}(i-1,j+1)\label{eq1}\\\nonumber
  s^{\nwarrow}_n(i,j)&=(s^{\searrow}_{n}(i+2,j-2)+s^{\nwarrow}_{n}(i+2,j-2))+(s^{\searrow}_{n}(i+1,j-3)+s^{\nwarrow}_{n}(i+1,j-3))\\
  &\quad +(s^{\nwarrow}_{n}(i+2,j)+s^{\nwarrow}_{n}(i,j-2))\quad\textrm{ if $j$ is odd, }\\\nonumber
  &=(s^{\searrow}_{n}(i+2,j-2)+s^{\nwarrow}_{n}(i+2,j-2))+(s^{\searrow}_{n}(i+3,j-1)+s^{\nwarrow}_{n}(i+3,j-1))\\
  &\quad +(s^{\nwarrow}_{n}(i+2,j)+s^{\nwarrow}_{n}(i,j-2))\quad\textrm{ if $j$ is even, }
\end{align}
with null boundary conditions for all coefficients $s^*_n(i,j)$ with $n\leq0$ or $i<0$ or $i>n$ or $j<0$ except $s^{\searrow}_0(0,2)=1$.
Then, for $n\geq 4$, $s_n=s'_{n}+2s'_{n-1}+s'_{n-2}$ where  $s'_n=s^{\searrow}_{n+2}(2,0)$. 
%Then $s'_n=s^{\searrow}_{n+2}(2,0)$, and $s_n=s'_{n}+2s'_{n-1}+s'_{n-2}$ for $n\geq4$.
\end{prop}

The recurrence allows us (thanks to the boundary conditions) to compute $s_2,\ldots,s_n$ using $O(n^3)$ additions on integers of size $O(n)$.  
The first terms are
\[
\sum_{n\geq2} s_nt^n=3t^2+2t^3+3t^4+6t^5+14\,t^6+36\,t^7+102\,t^8+306\,t^9+972\,t^{10}+3216\,t^{11}+O(t^{12}).
\]
The proposition can be refined to take into account the number of
black and white vertices, since these quantities respectively
correspond to the numbers of iterations through
Equation~\eqref{eq1} at even or odd values of $j$. Let $s_{i,j}$ be the number of Schnyder labelings with $i+1$ white and $j+1$ black vertices (and $n=i+j-2$ inner faces). The first terms are
\begin{align*}
\sum_{a,b\geq2}& s_{a,b}x^ay^bt^{a+b-2}\!=\!3x^2y^2t^2\!+\!(x^3y^2+x^2y^3)t^3\!+\!3t^4x^3y^3\!+\!(3x^4y^3 + 3x^3y^4)t^5 \! \\ &
\!+\!( {x}^{5}{y}^{3}\!+\!12{y}^{4}{x}^{4}\!+\!{x}^{3}{y}^{5} ) {t}^{6}\!+\!( 18{y}^{4}{x}^{5}\!+\!18{x}^{4}{y}^{5} ) {t}^{7}\!+\! ( 12{x}^{6}{y}^{4}+78{x}^{5}{y}^{5}\!+\!12{x}^{4}{y}^{6} ) {t}^{8}\! +\! O(t^{9}).
\end{align*}
In particular, the coefficient of $x^{a+1}y^{2a+1}t^{3a}$ gives the number of Schnyder woods on triangulations with $a+2$ vertices,  obtained in~\cite{bernardi2009intervals}. The sequence starts as 1, 1, 3, 14, 84, 594 \cite[A005700]{OEIS}.
%in that expansion is as expected the well known number of triangulations endowed with a Schnyder wood~\cite{bernardi2009intervals}: 

\begin{proof}
  According to Proposition~\ref{prop:schnyder-tandem}, $s_n'$ is the number of (weighted) $S$-admissible tandem walk from $(0,2)$ to $(2,0)$ with $n+2$ SE steps. 

  Observe now that a weighted $S$-admissible tandem walk identifies
  with an un\-weight\-ed tandem walk with step set
  $\Sigma=\{(1,-1),(-2,2),(-3,1),(-1,3),(-2,0),(0,2)\}$ such that $(-1,3)$ 
  steps (resp.~$(-3,1)$ steps) always start from an even (resp.\ odd)
  $y$ position, and $\{(-2,0),(0,2)\}$-steps never follow $(1,-1)$
  steps. Indeed the weight on $(-i,j)$-steps of $S$-admissible walks
  exactly corresponds to the number of ways to convert such a step
  into a sequence of steps of $\Sigma$ starting with a step in
  $\{(-2,2),(-3,1),(-1,3)\}$ and followed with a sequence of steps in 
  $\{(-2,0),(0,2)\}$.  Upon distinguishing the various small step
  walks according to the origin and type of their last steps, one can
  then directly write the above last step removal recurrences.
\end{proof}
A similar recurrence can be obtained for polyhedral orientations,
although 3 series are necessary due to a further restriction on the
set of admissible walks with small steps to consider.
%\begin{prop}
%Let $p_n$ denote the number of polyhedral orientations with  $n$ inner vertices, which is also the number of $P$-admissible tandem walks of length $n$ starting from the origin and ending on the $x$-axis. 
%Let moreover
%$p^{\searrow}_n(i,j)$,
%$p^{\leftarrow}_n(i,j)$, and
%$p^{\uparrow}_n(i,j)$ be given by the following recurrences:
%\begin{align}
 % p^{\searrow}_n(i,j)&=p^{\searrow}_{n-1}(i-1,j+1)+p^{\nwarrow}_{n-1}(i-1,j+1)+p^{\uparrow}_{n-1}(i-1,j+1)\\\label{eq1p}\nonumber
 % p^{\nwarrow}_n(i,j)&=(p^{\searrow}_{n-1}(i+1,j-1)+p^{\nwarrow}_{n-1}(i+1,j-1)+p^{\uparrow}_{n-1}(i+1,j-1))\\\nonumber
  %  &\quad+(p^{\searrow}_{n-1}(i+2,j)+p^{\nwarrow}_{n-1}(i+2,j)+p^{\uparrow}_{n-1}(i+2,j))\\ &\quad+(p^{\nwarrow}_{n}(i+2,j))\quad\textrm{if $j$ is even,}\\\nonumber
   %               &=(p^{\searrow}_{n-1}(i+1,j-1)+p^{\nwarrow}_{n-1}(i+1,j-1)+p^{\uparrow}_{n-1}(i+1,j-1))\\\nonumber
    %&\quad+(p^{\searrow}_{n-1}(i,j-2)+p^{\nwarrow}_{n-1}(i,j-2)+p^{\uparrow}_{n-1}(i,j-2))\\ &\quad +(p^{\nwarrow}_{n}(i+2,j))\quad\textrm{if $j$ is odd,}\\\nonumber
 % p^{\uparrow}_n(i,j)&=p^{\nwarrow}_{n}(i,j-2)+p^{\uparrow}_{n}(i,j-2)
%\end{align}
%with boundary conditions  $p^*_n(i,j)=0$ for all $n\leq0$ or $i<0$ or $j<0$ or $i>n$, except $p^{\searrow}_0(0,0)=1$. 
%Then $p_n=\sum_{i\ge0}p^{\searrow}_{n}(i,0)$.
%\end{prop}
Letting $p_n$ be the number of polyhedral orientations with $n$ inner vertices, the resulting first terms are
\[
\sum_{n\geq4} p_nt^n= t^3 + 3t^5 + 4t^6 + 15t^7 + 39\,t^8 + 122\,t^{9} + 375\,t^{10} + 1212\,t^{11}+ 3980\,t^{12} + O(t^{13}).
\]
Again, the enumeration can be refined to take into account the number
of red vertices, blue vertices and green vertices. Letting $p_{a,b,c}$ be the number of polyhedral orientations with $a,b,c$ inner red, blue and green vertices, the first terms are 
\begin{equation*}
\begin{split}
\sum_{a,b,c\geq1} p_{a,b,c}&x^ay^bz^ct^{a+b+c}= xyzt^3 + (x^2y^2z+xy^2z^2+x^2yz^2)t^5 + 4x^2y^2z^2t^6 \\[-0.4cm] &+ (x^{3} y^{3} z + 4 x^{3} y^{2} z^{2} + 4 x^{2} y^{3} z^{2} + x^{3} y z^{3} + 4 x^{2} y^{2} z^{3} + x y^{3} z^{3})t^7 + O(t^8).
\end{split}
\end{equation*}

\subsection{Asymptotic enumeration}\label{enumasympt}
Our main result regarding the asymptotic enumeration is to show that the growth rates of the coefficients $p_n$ and $s_n$ 
are respectively $9/2$ and $16/3$. We also conjecture in each case the exponent of the polynomial correction.  

\begin{prop}[upper bounds]\label{prop:bound}
The coefficients $p_n$ and $s_n$ satisfy the bounds 
$p_n\leq (9/2)^{n+1}$  and $s_n\leq 2\cdot (16/3)^{n}$. 
\end{prop}
The proof method (\textit{e.g.}, for $p_n$) consists in defining a well chosen
biased random walk starting at the origin and remaining
$P$-admissible all the way (but not restricted to the quadrant). Letting $P_n$ denote this walk for its first $n$ steps, we
show that the probability that $P_n$ ends at $(1,1)$ is at least
$(2/9)^np_{n-1}$. Hence $p_{n-1}\leq (9/2)^n$.
 
\begin{thm}[Growth rates]\label{thm:growth_rates}
We have $\lim_{n\to\infty} p_n^{1/n}=9/2$ and $\lim_{n\to\infty} s_n^{1/n}=16/3$.
\end{thm}
The proof (for $p_n$) again relies on studying the random walk $P_n$. We show that it has (asymptotically) zero drift and remains a.a.s. in the box 
$\beta_n=[- \lceil n^{2/3}\rceil,\lceil n^{2/3}\rceil]^2$, and we derive from this that the number of $P$-admissible tandem walks of length $n$ remaining in $\beta_n$ is $(9/2)^{n+o(n)}$. Hence, letting such a walk $\gamma$ start at $(\lceil n^{2/3}\rceil, \lceil n^{2/3}\rceil)$, it stays in the quadrant. 
In addition, we can prepend (resp.\ append) to $\gamma$ a canonical walk of length $O(n^{2/3})$ to obtain (injectively) a $P$-admissible quadrant walk starting at the origin and  ending on the $x$-axis. This ensures that $p_n\geq (9/2)^{n+o(n)}$, which together with $p_n\leq (9/2)^n$ implies that $\lim_{n\to\infty} p_n^{1/n}=9/2$.  

Furthermore, we can establish a central limit theorem for the endpoint
 $(X_n,Y_n)$ of $P_n$ (rescaled by $\sqrt{n}$), with a covariance matrix of the form $\Big(\begin{array}{ll}\!\!a&\!\!b\!\!\!\\[-.1cm] \!\!b&\!\!a\!\!\!\end{array}\Big)$, where $a=72/5,b=-81/10$. Results by Denisov and Wachtel~\cite[Theorem~6]{denisov2015random} 
(to be extended to a bimodal setting in order to be applicable here) then indicate that the probability that $P_n$ stays in the quadrant and ends at $(1,1)$ should behave as $\kappa\, n^{-1-\pi/\arccos(\xi)}$, with $\kappa$ a positive constant, and $\xi=-b/a=9/16$. A very similar approach can be developed for Schnyder labelings, where this time the covariance matrix for the 
associated random walk has $a=192/7, b=-1408/63$, giving $\xi=-b/a=22/27$. 
%A very similar approach can be developed for Schnyder labelings, establishing that $4(3/16)^n s_{n-1}'$ is the probability that a certain random walk $P_n'$ of length $n$ starting at $(0,2)$ ends at $(2,0)$. This random walk has zero drift, and a central limit theorem holds,  with a covariance matrix of the form $\Big(\begin{array}{ll}\!\!a&\!\!b\!\!\!\\[-.1cm] \!\!b&\!\!a\!\!\!\end{array}\Big)$, where $a=192/7,b=-1408/63$. 
%Again this indicates the probability that $P_n'$ stays in the quadrant and ends at $(2,0)$ should behave as $\kappa'\, n^{-1-\pi/\arccos(\xi')}$, with $\kappa'$ a positive constant, and $\xi'=-b/a=22/27$. 
Based on this, we conjecture: 

\begin{cjt}\label{cj:asympt}
We have $p_n\sim \kappa\cdot(9/2)^n\cdot n^{-\alpha}$, where $\alpha=1+\pi/\mathrm{arccos}(9/16)\approx 4.23$ and $\kappa$ is a positive constant; and  $s_n\sim \kappa'\cdot (16/3)^n\cdot n^{-\alpha'}$, where $\alpha'=1+\pi/\mathrm{arccos}(22/27)\approx 6.08$ and $\kappa'$ is a positive constant. 
\end{cjt}

\begin{rk}
Using the method in~\cite{bostan2014non} one can easily verify that the constants $\alpha$ and $\alpha'$ in Conjecture~\ref{cj:asympt} are irrational (\textit{e.g.}, for $\alpha$, we have to check that $X(z):=16z-9$ is such that 
$X(\frac1{2}(z+z^{-1}))=(8z^2 - 9z + 8)/z$ has no cyclotomic factor in its numerator, which is indeed the case since the numerator is irreducible of degree $2$ and  has coefficients of absolute value larger than~$2$).  
Hence, a corollary to  Conjecture~\ref{cj:asympt} would be that the generating functions of the sequences $p_n$ and $s_n$ are not D-finite.
\end{rk}


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