
\documentclass[finalversion]{FPSAC2025}
\articlenumber{16}
\appto\bibfont{\setlength{\emergencystretch}{1em}}

\usepackage[utf8]{inputenc}
\usepackage{bbold}
\usepackage{float}
\usepackage{tikz}
\usetikzlibrary{cd, arrows.meta}
\usepackage{amsmath, color}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{amsthm}

\DeclareMathOperator{\Lap}{L}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\indeg}{indeg}
\DeclareMathOperator{\odeg}{outdeg}
\DeclareMathOperator{\val}{{\rm val}}
\DeclareMathOperator{\D}{{\mathcal D}}
\DeclareMathOperator{\Ver}{V}
\DeclareMathOperator{\Edg}{E}
\DeclareMathOperator{\init}{init}
\DeclareMathOperator{\fin}{fin}
\DeclareMathOperator{\var}{var}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm1}{\Cref{log-concave}}
\newtheorem*{thm2}{\Cref{MatroidVersion}}
\newtheorem*{ourbest}{\Cref{thm:ourbest}}
\newtheorem*{recallcorollary}{\Cref{cor:alexpoly}}
\newtheorem*{recallconjecture}{\Cref{conj:log-concave}}
\newtheorem{theoremidea}[theorem]{Theorem Idea}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{question}[theorem]{Question}

\newcommand{\acom}[1]{\textcolor{red}{[$\star$ #1\ $\star$]}}
\newcommand{\com}[1]{\textcolor{blue}{[$\star$ #1\ $\star$]}}


\usepackage{lipsum}

\title{Polytopal perspectives on the Alexander polynomial of special alternating links}

\author{\texorpdfstring{Elena S.~Hafner\thanks{\href{mailto:eshafner@uw.edu}{eshafner@uw.edu} E.S.H. was partially supported by NSF DMS-1847284.}\addressmark{1}, Karola M\'esz\'aros\thanks{\href{mailto:karola@math.cornell.edu}{karola@math.cornell.edu} K.M. was partially supported by NSF DMS-1847284 and NSF DMS-2348676.}\addressmark{2}, \and Alexander Vidinas\thanks{\href{mailto:acv42@cornell.edu}{acv42@cornell.edu} A.V. was partially supported by NSF DMS-1847284.}\addressmark{2}}{Elena S.~Hafner, Karola M\'esz\'aros, and Alexander Vidinas}}

\address{\addressmark{1}Department of Mathematics, University of Washington, Seattle, WA, USA \\ \addressmark{2}Department of Mathematics, Cornell University, Ithaca, NY, USA}

\received{11/15/2024}

\abstract{The Alexander polynomial (1928) was the first polynomial invariant of links devised to help distinguish them up to isotopy. In this abstract, we highlight views of the Alexander polynomials of special alternating links in terms of polytopes, namely, generalized permutahedra and root polytopes. Polytopes have been previously used to study polynomial invariants of special alternating links in the works of  Juh\'asz, K\'alm\'an, and Rasmussen (2012)  and K\'alm\'an and Postnikov (2017).  We settle Fox's longstanding conjecture of the trapezoidal property of the Alexander polynomials of alternating links in the special case of special alternating links using generalized permutahedra. We also offer a simple explanation of the connection between the generalized Alexander polynomial of Eulerian graphs defined by Murasugi and Stoimenow (2003) and root polytopes of unimodular matrices, building on the works of Li and Postnikov (2013) and T\'othm\'er\'esz (2023).
}

\keywords{Alexander polynomial, special alternating link, log-concavity, generalized permutahedron, Eulerian digraph, root polytope}

\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{refs.bib}

\begin{document}

\maketitle

\section{Introduction}

This extended abstract is based on two papers of the authors \cite{paper1, paper2} and follows their exposition. For full details on the results presented here, consult the aforementioned works.
  
  The Alexander polynomial $\Delta_L(t)\in\mathbb{Z}[t,t^{-1}]$ associated to an oriented link $L$ was the first polynomial knot invariant, discovered in the 1920s \cite{alexander1928topological}. The Alexander polynomial was originally defined by fixing a \textbf{diagram} -- a projection of $L$ in the plane decorated with \textit{undercrossings} and \textit{overcrossings}. The key property of the Alexander polynomial is that if oriented links $L_1$ and $L_2$ are isotopic, then $\Delta_{L_1}(t)=\Delta_{L_2}(t)$ up to multiplication by $\pm t^k$ for some integer $k$. Namely, up to multiplication by $\pm t^k$ for some integer $k$, $\Delta_L(t)$ is independent of the choice of diagram used to compute it.
 
 The coefficients of $\Delta_L(t)$ for an arbitrary link $L$ are palindromic. A link is \textbf{alternating} if it admits an \textbf{alternating diagram} -- that is, tracing along each component, crossings alternate between over and under. In 1962, Fox \cite{fox} conjectured that for alternating links, the absolute values of the coefficients of Alexander polynomials are trapezoidal. For alternating links $L$, the works \cite{Crowell, murasugi1958genus2} show that the Alexander polynomial can be normalized so that $\Delta_L(-t)\in \mathbb{Z}_{\geq 0}[t]$ and that its sequence of coefficients contains no internal zeros. Thus, we can write Fox's conjecture as follows:

\begin{conjecture}[\cite{fox}]\label{fox}  Let $L$ be an alternating  link. Then the coefficients of $\Delta_L(-t)$ form a trapezoidal sequence.

\end{conjecture}

Stoimenow \cite{stoi} strengthened Fox's conjecture from trapezoidality to log-concavity. Fox's 
conjecture remains stubbornly open in general, although some special cases have been settled by Hartley \cite{H79} for two-bridge knots,  Murasugi \cite{murasugi} for a family of alternating algebraic links, Ozsv\'ath and Szab\'o \cite{OS03} for the case of genus $2$ alternating knots, by the present authors for special alternating links  \cite{paper1}, and by Azarpendar, Juh\'asz and K\'alm\'an \cite{ajk24} for certain diagrammatic Murasugi sums of special alternating links. That Fox's conjecture holds for genus $2$ alternating knots was also confirmed by Jong 
\cite{jong2009alexander}. 


In \Cref{Sec:MPoly} of this abstract, we leverage Crowell's combinatorial model for Alexander polynomials of alternating links \cite{Crowell}, generalized permutahedra, and the theory of Lorentzian polynomials\footnote{In this abstract, we use the theory as developed by  Br\"and\'en and Huh in \cite{bh2019}. Lorentzian polynomials were independently developed by Anari, Liu, Oveis Gharan and   Vinzant  \cite{anari1,  anari3, anari2} under the name \textit{completely log-concave polynomials}.} \cite{bh2019} to prove the following theorem, as the present authors did in \cite[Theorem 1.2]{paper1}:

\begin{theorem}\label{log-concave} The coefficients of the Alexander polynomial $\Delta_L(-t)$ of a special alternating link $L$ form a log-concave sequence with no internal zeros. In particular, they are trapezoidal.  
\end{theorem}

In \Cref{sec:thm2}, we study a generalization of the Alexander polynomials of special alternating links to all Eulerian digraphs, defined by Murasugi and Stoimenow \cite{even}. Murasugi and Stoimenow introduced the {Alexander polynomial of an Eulerian digraph} $H$, which we denote $P_H(t)$.  The present authors prove in \cite[Theorem 1.7]{paper2}:

\begin{theorem}\label{MatroidVersion}
    Let $H$ be an Eulerian digraph, and let $M$ be the oriented graphic matroid associated to $H$.  Let $A_H$ be a totally unimodular matrix representing $M^*$, the oriented dual of $M$, and let $m$ be the size of a basis of $M^*$.  Then, 
\begin{equation} \label{eq} P_H(t) = \sum_{A' \text{ has property *}} Vol(Q_{A'})(t-1)^{\#col(A')-m}, \end{equation}
where a matrix $A'$ has property * if it is obtained by deleting a set of columns from $A_H$ without decreasing the rank of the matrix, and $Q_{A'}$ denotes the root polytope of $A'$.
\end{theorem}

The above theorem is inspired by a result of Li and Postnikov \cite{slicing}, which, in the case that $H$ is planar, relates slices of zonotopes to the right-hand side of \eqref{eq}.

\section{Background}

In this brief section, we give the background used throughout this abstract. We present additional background in Sections \ref{Sec:MPoly} and \ref{sec:thm2} when needed. 

\subsection{Notation and graph theory definitions}
\label{sec:notation}
 For any graph $G$, let $V(G)$ denote the vertex set of $G$ and $E(G)$ the edge set of $G$.  For a digraph $H$, we will denote the initial vertex of any $e \in E(H)$ by $\init(e)$ and the final vertex of $e$ by $\fin(e)$.  The number of edges with initial vertex $v$ will be denoted $\odeg(v)$, and the number of edges with final vertex $v$ will be denoted $\indeg(v)$. The digraph $H$ is \textbf{Eulerian} if it is connected and at each vertex $v\in V(H)$, $\indeg(v)=\odeg(v)$.  A planar Eulerian digraph is called an \textbf{alternating dimap} if its planar embedding is such that, reading cyclically around each vertex, the edges alternate between incoming and outgoing. We will interchangeably use the terms ``faces'' and ``region'' of a planar graph. 

\subsection{Special alternating links}\label{sec:special1}  We follow the construction for special alternating links presented by Juh\'asz, K\'alm\'an, and Rasmussen \cite{jkr} and  by K\'alm\'an and Murakami \cite{murakami} to associate a positive special alternating link $L_G$ to a planar bipartite graph $G$. Let $M(G)$ be the \textbf{medial graph} of $G$: the vertex set of $M(G)$ is the set $\{v_e \ | \ e\in\Edg(G)\}$, and two vertices $v_e$ and $v_{e'}$ of $M(G)$ are connected by an edge if the edges $e$ and $e'$ are consecutive in the boundary of a face of $G$. We think of a particular planar drawing of $M(G)$ here:  the midpoints of the edges of $G$ are the vertices of $M(G)$. Thinking of $M(G)$ as a flattening of a link, there are two ways to choose under and overcrossings at each vertex of $M(G)$ to make it into an alternating link $L_G$.  We select the over and undercrossings and orient $L_G$ so that each crossing is positive.  Every positive special alternating link admits a diagram of the form $L_G$ for some planar bipartite graph $G$. \Cref{fig:bipandlink} shows an example of this construction.



\begin{figure}
\centering
\includegraphics[height=5cm]{bip_and_link.pdf}
\caption{A planar bipartite graph along with its positive special alternating link $L_G$.}
\label{fig:bipandlink}
\end{figure}

 \section{Log-concavity of the Alexander polynomial of special alternating links} \label{Sec:MPoly}

The purpose of this section is to explain the idea of  the present authors' theorem \cite[Theorem 1.2]{paper1}:

\begin{thm1} The coefficients of the Alexander polynomial $\Delta_L(-t)$ of a special alternating link $L$ form a log-concave sequence with no internal zeros. In particular, they are trapezoidal.  
\end{thm1}

To do this, we review Crowell's model for the Alexander polynomial of an alternating link and its multivariate generalization that the present authors introduced in ~\cite{paper1}.


 \subsection{Crowell's model and its multivariate generalization}\label{sec:crowell_model} We begin with an overview of Crowell's model \cite{Crowell}. Let $L$ be an alternating link, and let $\mathcal{G}(L)$ be the planar graph obtained by flattening the crossings of an alternating diagram of  $L$;  the crossings of $L$ are the vertices of $\mathcal{G}(L)$ while the arcs between the crossings are the edges of $\mathcal{G}(L)$.  Note that $\mathcal{G}(L)$ is a planar  $4$-regular graph. Next, we assign directions to the edges of $\mathcal{G}(L)$ -- but not those coming from the orientation of the link -- as well as weights in the following way:
 
 \bigskip
 
\begin{center} \begin{tikzpicture}
\draw[black, thick] (1,0) -- (1,.9);
\draw[black, thick] (1,1.1) -- (1,2);
\draw[-stealth,black, thick] (0,1) -- (2,1);
\draw[-stealth,black,thick] (5,0)--(5,1);
\draw[-stealth,black,thick] (5,2)--(5,1);
\draw[black,thick] (4,1) --(6,1);
\node at (3,1.2) {becomes};
\node at (4.8,1.5) {$1$};
\node at (4.7,.5) {$-t$};
\end{tikzpicture} \end{center} 

Denote by $\overrightarrow{\mathcal{G}(L)}$ the oriented weighted graph obtained from $\mathcal{G}(L)$ in this fashion. Let $\var(e)$ be the weight $-t$ or $1$ assigned to the edge $e \in E(\overrightarrow{\mathcal{G}(L)})$. An \textbf{arborescence} rooted at $r$ is a spanning tree with a unique directed path from the root $r$ to any vertex. 

\begin{theorem}[\protect{\cite[Theorem 2.12]{Crowell}}]
    \label{Thm:CrowellModel} Given an alternating diagram of the link $L$, fix an arbitrary vertex $r \in V(\overrightarrow{\mathcal{G}(L)})$. Denote by $\mathcal{A}(L,r)$ the set of arborescences of $\overrightarrow{\mathcal{G}(L)}$ rooted at $r$. The Alexander polynomial of $L$ is
  
    \[\Delta_L(t)=\sum_{\substack{T\in \mathcal{A}(L,r)}} \prod_{e \in E(T)} \var(e). \]
\end{theorem}
 
\Cref{Thm:CrowellModel} reveals the possibility of a multivariate generalization of the Alexander polynomial by assigning a new variable weight to each edge of $\overrightarrow{\mathcal{G}(L)}$. Our goal is to make a Lorentzian generalization of the Alexander polynomial in such a way that the (denormalized) Lorentzian property carries over to the homogenization of the Alexander polynomial $\Delta_{L_G}(-t)$ for any planar bipartite graph $G$. This, in turn, would imply the log-concavity of the coefficients of $\Delta_{L_G}(-t)$.
 
We note that the oriented graph $\overrightarrow{\mathcal{G}(L_G)}$ is an alternating dimap. Any alternating dimap $D$ is two-face colorable.  The edges surrounding faces in one color class are clockwise oriented cycles, and the edges surrounding the other faces are counterclockwise oriented cycles. In \cite[Lemma  3.1]{paper1}, the present authors show the following: 
 
 \begin{lemma}\label{inspire} Let $G$ be a planar bipartite graph. Suppose $R$ is the set of all regions of $\overrightarrow{\mathcal{G}(L_G)}$ whose boundaries are clockwise oriented cycles.  Then, $R$ is either precisely the set of regions associated to vertices of $G$ or the set of regions associated to vertices in its planar dual $G^*$.  Furthermore, the boundary of every face in $R$ is either labeled with a $1$ on every edge or with a $-t$ on every edge.  
\end{lemma}


In light of \Cref{inspire}, we consider a generalization of the Alexander polynomial  $\Delta_{L_G}(-t)$ as in \cite[Definition 3.3]{paper1} and \cite[Definition 3.4]{paper1} of the present authors' work:

 \begin{definition}\label{var}   Denote the set of clockwise oriented regions of the alternating dimap $D$ by $R(D)$.  Let $R(D)=\{R_1, \ldots, R_k\}$. Each edge $e \in E(D)$ belongs to the boundary of exactly one region in $R(D)$. For each edge $e$ in the boundary of $R_i$, $i \in [k]$, assign the variable $\var(e)=x_i$.  See \Cref{fig:posspec} for an example. 
\end{definition}

\begin{figure}
\centering
\includegraphics[height=6cm]{dimap_out.pdf}
\caption{Left: the graph $\protect\overrightarrow{\mathcal{G}(L_G)}$ for the positive special alternating link in Figure \protect\ref{fig:bipandlink} with edge variables in Crowell's convention. Center: $\protect\overrightarrow{\mathcal{G}(L_G)}$ with edge variables as in Definition \protect\ref{var}. Right: an arborescence rooted at $r$ and the associated monomial.}
\label{fig:posspec}
\end{figure}

\begin{definition}\label{mpoly} Let $D$ be an alternating dimap, and define $\var(e)$, $e \in E(D)$, as in \Cref{var}. Fix a vertex $r\in V(D)$. The \textbf{$M$-polynomial of D} is the polynomial \begin{equation} M_{D,r}(x_1, \ldots, x_k)=\sum_{A} \prod_{e\in E(A)} \var(e) \end{equation}
where the sum is over all arborescences $A$ of $D$ rooted at $r$. 
\end{definition}

We point out that  $M_{D,r}(x_1, \ldots, x_k)$ depends only on the dimap $D$ and not on the choice of root $r$. For this reason, we denote it simply by $M_{D}({\bf x})$ for the rest of this section. The polynomial we term the $M$-polynomial appeared as a determinant in works by  Juh\'asz, K\'alm\'an, and Rasmussen \cite{jkr} and by K\'alm\'an \cite{tamas} with a different, but closely related, prelude. We conclude this section with the following theorem, which appears as \cite[Theorem 3.5]{paper1} in the present authors' work:

 
 \begin{theorem}\label{thm:spec} Let $G$ be a planar bipartite graph, and assign $\overrightarrow{\mathcal{G}(L_G)}$ the orientation and labeling from Crowell's model as described in \Cref{sec:crowell_model}. Let $\{R_1, \ldots, R_l\}$ and $\{R_{l+1}, \ldots, R_k\}$ be the clockwise oriented regions of $\overrightarrow{\mathcal{G}(L_G)}$ labeled with $-t$'s and $1$'s respectively. Then, 
 
\begin{equation} \label{spec} \Delta_{L_G}(-t)=M_{\overrightarrow{\mathcal{G}(L_G)}}(t, \ldots,t, 1,\ldots, 1) \end{equation} 
 where we set $x_1=\cdots=x_l=t$ and $x_{l+1}=\cdots=x_k=1$ in $M_{\overrightarrow{\mathcal{G}(L_G)}}.$ 
 
 Similarly, 
 \begin{equation} \label{qt} {\rm Homog}_q(\Delta_{L_G}(-t))=M_{\overrightarrow{\mathcal{G}(L_G)}}(t, \ldots,t, q,\ldots, q), \end{equation} 
 where ${\rm Homog}_q(\Delta_{L_G}(-t))$ denotes the $q$-homogenization of $\Delta_{L_G}(-t)$ and  we set $x_1=\cdots=x_l=t$ and $x_{l+1}=\cdots=x_k=q$ in $M_{\overrightarrow{\mathcal{G}(L_G)}}.$ 
 

 
 \end{theorem}





\subsection{Proof Strategy for \texorpdfstring{\Cref{log-concave}}{Theorem 1.2}}

The goal of this section is to outline the proof in the present authors' work \cite[Theorem 4.1]{paper1} of the following result:

\begin{theorem} \label{thm:denorm} For any alternating dimap $D$, the polynomial $M_{D}({\bf x})=M_{D,r}({\bf x})$ is independent of the choice of root $r \in D$. Moreover, $M_{D}({\bf x})$ is denormalized Lorentzian.
\end{theorem}

This, together with \Cref{thm:spec} and results from Lorentzian theory \cite{bh2019, pak}, settle \Cref{log-concave}. For brevity, we will not define what it means for a polynomial to be \textit{denormalized Lorentzian}. Rather, we invoke results in the theory of Lorenztian polynomials and refer the reader to \cite{bh2019} and \cite{pak} for further background. 

Recall that the \textbf{support} of a polynomial $f \in \mathbb{R}[x_1, \ldots, x_n]$ is  the set $\text{supp}(f) \subseteq \mathbb{N}^n$ of all tuples $(\alpha_1,\ldots,\alpha_n)$ such that the monomial $x_1^{\alpha_1}\cdots x_n^{\alpha_n}$ has nonzero coefficient in $f$. If the convex hull of $\text{supp}(f)$ is a generalized permutahedron -- a polytope all of whose edges are all parallel to $e_i-e_j$, where $e_i$ is the standard basis vector -- and if every lattice point in the convex hull of $\text{supp}(f)$ appears in some monomial of $f$, then $f$ is said to have \textbf{$M$-convex support}. A  polynomial with $0$ and $1$ coefficients whose support is $M$-convex is always denormalized Lorentzian. 

We first relate the support of the $M$-polynomial to another well-known Lorentzian polynomial. Let $g_D$ be the integer point enumerator, defined below, of the base polytope of the graphic matroid of $D$ considered without orientation. If we let $R_1, \ldots, R_k$ of $D$ be the regions bounded by the clockwise oriented cycles $C_1, \ldots, C_k$ and denote the edges of $C_i$ by $e_{i,1},\ldots,e_{i,|C_i|}$,  $i \in [k]$, then 
$$g_D(x_{1,1},\ldots,x_{n,|C_k|})=\sum_{T \in \mathcal{T}(D)} \prod_{e_{i,j} \in E(T)} x_{i,j}.$$  

Next, we specialize $g_D({\bf x})$ in a way that preserves the Lorentzian property:
 
$$f_D(x_1,\ldots,x_k)=\sum_{T \in \mathcal{T}(D)} \prod_{i=1}^k x_i^{a_i(T)},$$ where $a_i(T)$ is the number of edges of $T$ belonging to the cycle $C_i$, $i \in [k]$. Thus, we have the following lemma, which the present authors prove in \cite[Lemma 4.2]{paper1}:

\begin{lemma} \label{fD} Given an alternating dimap $D$, the polynomial $f_D$ is Lorentzian.  In particular, $f_D$ has $M$-convex support.
\end{lemma} 

Next, we see that for any $r \in D$, ${\rm supp}(f_D(x_1,\ldots,x_k))={\rm supp}(M_{D,r}(x_1,\ldots,x_k))$. To do this, we need K\'alm\'an's  lemma:

\begin{lemma}[\protect{\cite[see proof of Theorem 10.1]{tamas}}]\label{Lem:TreestoArbs}
Let $D$ be an alternating dimap.  Denote the cycles surrounding the clockwise oriented regions by $C_1, \ldots, C_k$.  Let $T$ be any spanning tree in $D$, and fix any $r \in V(D)$.  Let $a_i(T)$ be the number of edges of $T$ in the cycle $C_i$.  Then, there exists an arborescence $A$, rooted at $r$, such that $a_i(A)=a_i(T)$ for all $i \in [k]$. 
\end{lemma}

\begin{corollary}
\label{Cor:MPolySupp}
For any $r \in V$, ${\rm supp}(f_D(x_1,\ldots,x_k))={\rm supp}(M_{D,r}(x_1,\ldots,x_k)).$ In particular, ${\rm supp}(M_{D,r}(x_1,\ldots,x_k))$ is $M$-convex.
\end{corollary}

The above corollary, which appears as \cite[Corollary 4.4]{paper1} in the present authors' prior work, shows the $M$-polynomial is supported on a generalized permutahedron. It also implies that the support of the $M$-polynomial is entirely independent of the choice of root. K\'alm\'an proved a statement within  \cite[see proof of Theorem 10.1]{tamas} which yields that $M_{D,r}$ has $0$ and $1$ coefficients. Thus,  $M_{D,r}$ does not depend on the choice of $r$.

\begin{proof}[Proof of \Cref{thm:denorm}.] By \Cref{Cor:MPolySupp}, the support of $M_{D,r}({\bf x})$ is $M$-convex and independent of the choice of root $r$. Moreover, all coefficients of 
$M_{D,r}({\bf x})$ are $1$ on its support.  Thus, $M_{D,r}({\bf x})$ is independent of the choice of $r$, and we may denote it by $M_D({\bf x})$.  Since the $M$-polynomial has $M$-convex support and $0$ and $1$ coefficients, we conclude that $M_{D}({\bf x})$ is denormalized Lorentzian. \end{proof}

\Cref{thm:denorm} with other results lend themselves to a proof of \Cref{log-concave}.

 \section{The Alexander polynomial of an Eulerian digraph} \label{sec:thm2}

Recall that an \textbf{arborescence} rooted at $r$ is a spanning tree such that for every $v \in V(H)$, there is a unique directed path from $r$ to $v$. An \textbf{oriented spanning tree} rooted at $r \in V(H)$ is a spanning tree of $H$ such that for each vertex $v \in V(H)$, there is a unique directed path from $v$ to $r$.  A \textbf{$k$-spanning tree} rooted at $r \in V(H)$ is a spanning tree of $H$ such that reversing the orientation of exactly $k$ of its edges yields an oriented spanning tree rooted at $r$. With this terminology, $\{|V(H)|-1\}$-spanning trees are precisely arborescences, and $0$-spanning trees coincide with oriented spanning trees.   


\begin{definition}[\protect{\cite[Definition 1]{even}}] \label{def:genalex}
Denote by $c_k(H,r)$ the number of $k$-spanning trees rooted at $r$ in the Eulerian digraph $H$. The \textbf{Alexander polynomial of an Eulerian digraph} $H$ (and arbitrary $r \in V(H)$) is \begin{equation} \label{pdt} P_H(t)=\sum_{k=0}^{\infty} c_k(H, r)t^k.\end{equation} 
\end{definition}

To understand why this name is justified, recall that the planar dual of a planar bipartite graph $G$ is a planar Eulerian graph $H$. Note also that a planar Eulerian graph $H$ is readily orientable to become an alternating dimap if we consistently keep one color class of the bipartition of vertices of $G$ to the left and the other to the right (see \Cref{fig:bipandlink_kauff}). Recall also from \Cref{sec:special1} that any special alternating link is associated to a planar bipartite graph. Given a planar bipartite graph $G$, we may construct a unique positive special alternating link $L_G$ from it so that the projection of $L_G$ is the medial graph $M(G)$ of $G$. 
 

\begin{figure}
\centering
\includegraphics[height=5.75cm]{bip_and_link_kauff.pdf}
\caption{A planar bipartite graph $G$ along with its dual alternating dimap $H$ in dashed lines. See \Cref{fig:bipandlink} for the associated special alternating link $L_G$.}
\label{fig:bipandlink_kauff}
\end{figure}

The following theorem of Murasugi and Stoimenow then explains the naming in \Cref{def:genalex}:

\begin{theorem}[\protect{\cite[Theorem 2]{even}}] \label{thm2} For an alternating dimap $H$, the  polynomial  $P_H(t)$ equals the Alexander polynomial $\Delta_{L_{G}}(-t)$ for the special alternating link  $L_{G}$ associated to the planar dual $G$ of $H$. 
\end{theorem}

The present authors main contribution in this section is \cite[Theorem 1.7]{paper2} below:

\begin{thm2}
    Let $H$ be an Eulerian digraph, and let $M$ be the oriented graphic matroid associated to $H$.  Let $A_H$ be a totally unimodular matrix representing $M^*$, the oriented dual of $M$, and let $m$ be the size of a basis of $M^*$.  Then, 
\begin{equation} \label{eq2} P_H(t) = \sum_{A' \text{ has property *}} Vol(Q_{A'})(t-1)^{\#col(A')-m}, \end{equation}
where a matrix $A'$ has property * if it is obtained by deleting a set of columns from $A_H$ without decreasing the rank of the matrix, and $Q_{A'}$ denotes the root polytope of $A'$.
\end{thm2}

To make sense of the above theorem, we need to review the work of T\'othm\'er\'esz \cite{T22} on root polytopes of {co-Eulerian matroids}, which we do in the next subsection. 

\subsection{Root polytopes of oriented co-Eulerian matroids}\label{sec:root_poly}

In this section, we follow parts of  T\'othm\'er\'esz's \cite{T22} exposition and refer the reader there for more details. 

 A matroid $M$ is said to be \textbf{regular} if it is representable by a \textbf{totally unimodular matrix}, i.e., a matrix whose subdeterminants are all either $1$, $0$, or $-1$. Every real-representable matroid is naturally an oriented matroid. In particular, we orient a regular matroid $M$ by assigning the following bipartitions to its circuits. Let $A$ denote a totally unimodular matrix representing $M$ and $\{a_1, \dots, a_m\}$ its columns. For each circuit $C=\{i_1,\dots,i_j\}$ of a regular matroid with a corresponding linear dependence relation $\sum_{k=1}^j\lambda_k a_{i_k}=0$ of columns of $A$, we may partition its elements into two sets: $C^+=\{i_k \  | \ \lambda_k > 0\}$ and $C^-=\{i_k \ | \ \lambda_k < 0\}$. Scaling the expression $\sum_{k=1}^j\lambda_k a_{i_k}$ by a nonzero constant potentially interchanges $C^+$ and $C^-$, but the partition of $C$ into these two sets is well-defined up to this exchange.

Two regular oriented matroids $M_1$ and $M_2$ on groundset $E$ have \textbf{mutually orthogonal signed circuits} if for each pair of signed circuits $C_1={C_1}^+\sqcup {C_1}^-$ and $C_2={C_2}^+\sqcup {C_2}^-$ of $M_1$ and $M_2$, respectively, either $C_1\cap C_2 = \emptyset$, or $({C_1}^+ \cap {C_2}^+)\cup({C_1}^- \cap {C_2}^-)$ and $({C_1}^+ \cap {C_2}^-)\cup({C_1}^- \cap {C_2}^+)$ are both nonempty. Every regular oriented matroid $M$ admits a unique \textbf{dual oriented matroid} $M^*$ such that $M$ and $M^*$ have mutually orthogonal signed circuits.


\begin{definition}[\protect{\cite[Definition 3.4]{T22}}] 
    A regular oriented matroid is \textbf{co-Eulerian} if for each circuit $C$, $|C^+| = |C^-|$. 
\end{definition}

\begin{lemma}[\protect{\cite[Claim 3.5]{T22}}]
For an Eulerian digraph $H$, the oriented dual $M^*$ of the graphic matroid of $H$ is a co-Eulerian regular oriented matroid.
\end{lemma}

With this foundation, T\'othm\'er\'esz introduces the following definition and results:

\begin{definition}[\protect{\cite[Definition 3.1]{T22}}]
    Let $A$ be a totally unimodular matrix with columns $a_1, \dots, a_m$. The \textbf{root polytope} of $A$ is the convex hull $\mathcal{Q}_A := \emph{conv}(a_1, \dots, a_m)$.
\end{definition}

T\'othm\'er\'esz demonstrates that for any pair of totally unimodular matrices $A$ and $\tilde{A}$ representing the same regular oriented matroid $M$, there is a lattice point-preserving linear bijection between $t\cdot\mathcal{Q}_A$ and $t\cdot\mathcal{Q}_{\tilde{A}}$ for any $t\in\mathbb{Z}$.  In this way, the definition of a root polytope can be extended to regular oriented matroids.  The set of arborescences of an Eulerian digraph yields a triangulation of the root polytope of the dual matroid. Recall that an arborescence of $H$ rooted at $r\in\Ver(H)$ is a directed subgraph $A$ such that for each other vertex $v$ of $H$, there is a unique directed path in $A$ from $r$ to $v$.

\begin{proposition}[\protect{\cite[Proposition 3.8]{T22}}]
    For a regular oriented matroid represented by a totally unimodular matrix $A$ and a basis $B=\{i_1,\dots,i_j\}$, the simplex $\Delta_B := \emph{conv}(a_{i_1},\dots,a_{i_j})$ is unimodular. That is, its normalized volume is $1$.
\end{proposition}

\begin{theorem}[\protect{\cite[Theorem 4.1]{T22}}]
Let $H$ be an Eulerian digraph, and let $A_H$ be any totally unimodular matrix representing the oriented dual of the oriented graphic matroid of $H$. Let $r\in V(H)$ and $\mathcal{H} = \{B\subset E(H) \ | \ E(H) - B \ \text{is an arborescence of} \ H \ \text{rooted at} \ r\}$. Then $\{\Delta_B \ | \ B\in\mathcal{H}\}$ is a triangulation of $\mathcal{Q}_{A_H}$.
\end{theorem}

 
\begin{corollary}[\cite{T22}]
\label{VolMatroidCase}
    Let $H$ be an Eulerian digraph, and let $A_H$ be any totally unimodular matrix representing the oriented dual of the oriented graphic matroid of $H$. Let $r\in V(H)$.  Then,
    $$\emph{Vol} (\mathcal{Q}_{A_H}) = c_0(H,r).$$
\end{corollary}

\subsection{Proof Sketch of \texorpdfstring{\Cref{MatroidVersion}}{the matroid version}}
\label{we are now re}

By an inclusion-exclusion argument, the authors of the present paper proved \cite[Theorem 2.3]{paper2}, which states:

\begin{theorem}
\label{CountingArbs}
    Let $H$ be an Eulerian digraph, and fix any $r \in V(H)$.  Then,
    \[c_k(H,r)=\sum_{i=0}^{k}(-1)^i\sum_{\substack{\text{\emph{acyclic} } E' \subset E(H) \\ |E'|=k-i}} \binom{|V(H)|-1-(k-i)}{i}c_0(H/E',r). \]
\end{theorem}

The following result--\cite[Corollary 3.7]{paper2} in the present authors' prior work--is immediately proven with the above result and \Cref{VolMatroidCase}:

\begin{corollary}
    \label{CountingArbsVol}
    For an Eulerian digraph $H$, let $A_H$ denote a totally unimodular matrix representing the oriented dual of the graphic matroid of $H$. Then,
    $$c_k(H,r)=\sum_{i=0}^{k}(-1)^i\sum_{\substack{\text{acyclic } E' \subset E(H) \\ |E'|=k-i}} \binom{|V(H)|-1-(k-i)}{i}\emph{Vol} (\mathcal{Q}_{A_{H/E'}}).$$
\end{corollary}

 
Both \Cref{MatroidVersion} and the following corollary--\cite[Corollary 1.8]{paper2} in the present authors' work--are closely related to  Li and Postnikov's \cite{slicing} beautiful work on slicing zonotopes in which they explicitly consider the right-hand side of \eqref{apost}.
 
\begin{corollary} \label{cor:alexpoly}  The Alexander polynomial $\Delta_{L_{G}}(-t)$ of the special alternating link associated to the planar bipartite graph $G$ can be expressed as
\begin{equation}\label{apost} \Delta_{L_{G}}(-t) = \sum_{\substack{G' \subset G \\ G' \text{ connected}}} Vol(Q_{G'})(t-1)^{|E(G')|-|V(G)|+1}.\end{equation}
\end{corollary}

\acknowledgements{The second author is grateful to Tam\'as K\'alm\'an and Alexander Postnikov for many inspiring conversations over many years. The authors are also grateful to Mario Sanchez for his interest and helpful comments.}

\nocite{KP17}
\printbibliography



\end{document}

