%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{29}
%% 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}

\newcommand{\qcircle}{\mathbin{\text{\textcircled{\small $q$}}}}


\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corolary}
\newtheorem{p}[thm]{Proposition}

% \newtheorem*{thm*}{Theorem}
% \newtheorem*{thmm}{Theorem}

\theoremstyle{definition}
\newtheorem{de}[thm]{Definition}
\newtheorem{ex}[thm]{Example}

\usepackage{tikz-cd}

\usetikzlibrary{
arrows,
% decorations.pathreplacing,
% calligraphy,
% patterns,
% positioning,
% matrix,
% shapes.multipart, 
calc,
% bending
}
%\usepackage{array}
%\usepackage{tabularx}
%\usepackage{comment}

\usepackage{Figures}

\newcommand{\Sym}{\mathbb{S}}
\DeclareMathOperator{\sign}{sgn}

\DeclareMathOperator{\Image}{Im}

%\DeclareMathOperator{\sgn}{sgn}

%% define your title in the usual way
\title{Determinant of the distance matrix of a tree}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[E. Briand, L. Esquivias, Á. Gutiérrez, A. Lillo, and M. Rosas]{
Emmanuel Briand%\thanks{\href{mailto:ebriand@us.es}{ebriand@us.es} Supported partially by ...}
\addressmark{1}, 
Luis Esquivias%\thanks{\href{mailto:???}{???} Supported partially by ...}
\addressmark{2}\addressmark{3},
Álvaro Gutiérrez%\thanks{%\href{mailto:a.gutierrezcaceres@bristol.ac.uk}{a.gutierrezcaceres@bristol.ac.uk} Supported partially by ...}
\addressmark{2}\addressmark{4}, 
Adrián Lillo%\thanks{\href{mailto:???}{???} Supported partially by ...}
\addressmark{2}, \and
Mercedes Rosas\thanks{\href{mailto:mrosas@us.es}{mrosas@us.es}}\addressmark{2}
}

%% then use \addressmark to match authors to institutions here
\address{
  \addressmark{1}Departamento Matem{\'a}tica Aplicada 1, University of Seville, Seville \\
  \addressmark{2}Departamento de {\'A}lgebra, University of Seville, Seville \\
  \addressmark{3}Departamento de {\'A}lgebra, Geometr{\'i}a y Topolog{\'i}a, Universidad Complutense, Madrid \\
  \addressmark{4}Department of Mathematics, University of Bonn, Bonn\\
}


%% put the date of submission here
\received{October 1st, 2023}

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



%% 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 present a combinatorial proof of the  Graham--Pollak formula  for the determinant of the distance matrix of a tree, via sign-reversing involutions and the Lindström--Gessel--Viennot lemma.}

%% put your French abstract here, or comment this out if you don't have one
\resume{Nous présentons une preuve combinatoire de la formule de Graham et Pollak pour le déterminant de la matrice des distances d'un arbre, en utilisant des involutions et le lemme de Lindström--Gessel--Viennot.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Distance matrix of a tree.  Lindström--Gessel--Viennot's Lemma.
Sign-reversing involutions. 
Bijective Combinatorics.}

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

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

\definecolor{USred}{cmyk}{0,0,0,1}
\definecolor{USred2}{cmyk}{0,1.00,0.65,0.2}
\definecolor{USblue}{cmyk}{1.00,0.65,0,0}
\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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%   Start of 0_Introduction.tex  %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Introduction}

Consider a tree $T$ with vertices labeled from one to $n$, and edge set $E$.  Define the {\em distance} between vertices $i$ and $j$, denoted  by $d(i, j)$,  as number of edges in the unique path of $T$ connecting  $i$ and $j$. Define the {\em distance matrix} of $T$ as
$
M(T) = \left(d(i,j)\right)_{ 1 \le i,j\le n}.
$

In their influential 1971 paper \cite{GrahamPollak}, Graham and Pollak  established that the determinant of  the distance matrix of $T$  
obeys  the \textcolor{USred}{\em Graham--Pollak formula}:
\begin{equation}\label{eq: Graham--Pollak}
    \det M(T) = (-1)^{n-1}(n-1)2^{n-2}
\end{equation}
Observe that this implies that the determinant of  the distance matrix of  $T$ is solely dependent on its number of vertices, and not on its tree structure.

Multiple techniques drawn from linear algebra, ranging from Gauss elimination to
Charles Dodgson's condensation formula, have been used to prove the Graham--Pollak formula
\cite{DuYeh, GrahamPollak, TilliaThesis, YanYeh:2007,  ZhouDing}. 
However, the expression $(-1)^{n-1}(n-1)2^{n-2}$ suggests the existence of a signed enumeration problem solved by $\det M(T)$. 

Pursuing this trail has led us to a novel combinatorial proof of the Graham--Pollak formula that  relies on the existence of sign-reversing involutions, and on the celebrated Lindström--Gessel--Viennot lemma. Our journey concludes by establishing that our combinatorial proof provides a solid framework for many of the existing generalizations and
$q$-analogues of the Graham--Pollak formula, and facilitates the derivation of new ones.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%   Start of 1_Definitions.tex %%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Catalysts}\label{sec: catalysts}
{\em Where  we introduce the idea of a {\em catalyst} for a tree,  and demonstrate how $\det(T)$ does a signed enumeration of all catalysts of a fixed tree $T=([n],\, E)$.}\\

%Throughout the paper, we f
Fix a tree    $T = ([n],\, E)$. % with vertex set $[n]$ and edge set $E$, where $[n]$ denotes the set of integers between one and $n$. 
Let $E^{\pm} = \{(i,j)\ :\ \{i,j\}\in E\}$ denote the set of arcs supported on $T$.
Given  a permutation $\sigma$ in $\Sym_n$ and a map $f : [n] \rightarrow E^\pm$,  
the ordered pair  $(\sigma, f)$ is a   \textcolor{USred}{\em  catalyst for $T$} if for each vertex $i$, $f(i) = (v_i, v_{i+1})$ is a pair of successive vertices in the path $P(i, \sigma(i))$ (i.e., an arrow).
The \textcolor{USred}{\em  sign of  a catalyst} is  the sign of its underlying permutation. 


\begin{figure}[h]
    \centering
    \scriptsize
    \begin{tabular}{cccc}
        & \textbf{(a)} & \textbf{(b)} & \textbf{(c)} \vspace{0.5em} \\ 
        \includegraphics[width = 0.2\textwidth]{figT.pdf}%\figT    
        &  
    \includegraphics[width = 0.18\textwidth]{catalystUnital.pdf}%\catalystUnital 
    &
    \includegraphics[width = 0.18\textwidth]{catalystDisconnected.pdf}%\catalystDisconnected 
    &
    \includegraphics[width = 0.18\textwidth]{catalystParallel.pdf}%\catalystParallel 
    \\
    & $\kappa = (\sigma, f)$
    & $\kappa' = (\sigma', f')$
    & $\kappa'' = (\sigma'', f'')$
    \end{tabular}
    
    \caption{A tree $T$ and the diagrams of three  of its catalysts.
     We can recover a catalyst from its  diagram. E.g., from the first diagram we see that $\sigma(1) = 6$ and $f(1) = (1,2)$, that
     $\sigma(2) = 5$ and $ f(2) = (2,5)$, that $\sigma(3) = 8$ and $f(3) = (3,1)$, and so on.}
    \label{fig: catalysts}
\end{figure}
The determinant $\det M(T)$ does a signed enumeration of  all catalysts for $T$. This is so because $d(i,\sigma(i))$ counts the number of edges in the unique path $P(i,\sigma(i))$ in $T$. Indeed,
\begin{align}%\label{eq:prod}
\det M(T) = \sum_{\sigma \in \Sym_n} \sign(\sigma) \, d(1,\sigma(1))d(2,\sigma(2)) \ldots d(n,\sigma(n))\label{eq:P}   
= \sum_{\kappa\in K}\sign\kappa,
\end{align}
where we are summing over $K$, the set of all catalysts for $T$. 
It is worth noting that the definition of catalyst implies that its underlying permutation  must be a   {\em  derangement}, that is, a permutation without  fixed points. 

Partitioning catalysts by their underlying permutations proves ineffective in our search of a combinatorial proof of the Graham--Pollak formula, as in general, there are no cancellations between resulting summands. 




\section{Arrowflows and the Graham--Pollak formula}\label{sec: arrowflows}
{\em Where we present the definition of the arrowflow induced  on $T$ by a catalyst, and show how the Graham--Pollak formula becomes transparent when catalysts are partitioned according to them. }\\
  
  
An \textcolor{USred}{\em  arrowflow on $T$} is  a directed multigraph with vertex set  $[n]$, with exactly  $n$ arcs when counted with multiplicity,  and whose underlying simple graph is a subgraph of $T.$
By definition, given any catalyst $\kappa= (\sigma, f)$, 
the image of $f$, considered as a multiset,
%that is $ \{\!\{  f(i) \, |\, i \in [n]\}\!\}$,  
is always an arrowflow on $T$. We refer to it as {\em  arrowflow induced} by  $\kappa$.

We say that an arrowflow $A$ is connected when its underlying simple graph is. If $A$ is a connected arrowflow, there exist precisely two vertices  that belong to more than one arrow of $A$. It turns out that these two vertices always belong to precisely  two arrows, that we call the  {\em repeated arrows}. 
We say that the repeated arrows of a connected arrowflow are {\em parallel} when they point in the same direction, and  {\em anti-parallel} when they point in opposite directions. 

An arrowflow is said to be {\em unital} when it is connected and its repeated arrows are anti-parallel, as illustrated in Figure \ref{fig: arrowflows} (a). Otherwise, it is said to be {\em zero-sum}. There are two possible causes for an arrowflow to be zero-sum. Either the arrowflow is disconnected, as illustrated in 
 Figure \ref{fig: arrowflows} (b), or
the arrowflow is connected, but the repeated arrows are parallel,   as in
Figure \ref{fig: arrowflows} (c).



\begin{ex} \label{ex:arrowflows}
Figure \ref{fig: arrowflows} shows the three arrowflows induced by the three catalysts  of Figure \ref{fig: catalysts}. The first arrowflow (a) is unital. The second arrowflow (b) is zero-sum because it is disconnected. The last one (c) is zero-sum because arc $(1,2)$ appears twice.
\end{ex}

\begin{figure}[h]
    \centering
    \scriptsize
    \begin{tabular}{ccc}
        \textbf{(a)} & \textbf{(b)} & \textbf{(c)} \vspace{0.5em} \\
    \arrowflowUnital & 
    \arrowflowDisconnected    & 
    \arrowflowParallel
    \end{tabular}
    \caption{
    \textcolor{USred}{\textbf{(a)}} Unital,
    \textcolor{USred}{\textbf{(b)}} disconnected zero-sum,
    \textcolor{USred}{\textbf{(c)}} connected zero-sum arrowflows.     }
    \label{fig: arrowflows}
\end{figure}



It is crucial to observe that  different catalysts on $T$ can result on the same arrowflow.
On the other hand, it is worth pointing out that there exist arrowflows on $T$ that are not induced by any catalyst for $T$. We leave it to the reader to come up with such examples.


We define  the \textcolor{USred}{\em  arrowflow class of  $A$}, denoted by $C(A)$,  as the set of catalysts inducing $A$ on $T$.
An arrowflow class $C(A)$ is unital or zero-sum according to whether $A$ is  unital or zero-sum. 
Nonempty arrowflow classes define a partition $K = \bigsqcup_A C(A)$ of  the set $K$ of all catalysts for $T$, that we call the \textcolor{USred}{\em arrowflow partition  of $K$}.
It allows us to rewrite Equation~\eqref{eq:P} as
\begin{align} \label{main_eq}
\det M(T) = \sum_{\substack{A\\ \text{arrowflow}} }\sum_{\kappa \in C(A)} \sign(\kappa),
\end{align}
where the first sum is taken over all arrowflows on $T$, and the second one over all catalysts $\kappa$ in the arrowflow class $C(A)$. 

\begin{thm} \label{lem:crucial}
The arrowflow partition defines an optimal way of partitioning the set of catalysts for $T$. More precisely, if $C(A)$ is an arrowflow class, then
\begin{align}\label{crucial_result}
\sum_{\kappa \in C(A)} \sign(\kappa) = 
\begin{cases}
(-1)^{n-1} & \text{ if } A \text{ is a unital arrowflow,}\\
0 & \text{ if } A  \text{ is a zero-sum arrowflow.}
\end{cases}
\end{align}
\end{thm}

The proof of this  result will unfold in the following two sections.  

We close this section by showing how a combinatorial proof of the Graham--Pollak formula can be obtained by gathering all the elements of our reasoning.  First observe that
Theorem   \ref{lem:crucial} implies that there can be no cancellations between the different summands in Equation~\eqref{main_eq}. 
Therefore, it suffices to show that\[ 
\sum_{\substack{A {\text{ unital}}\\\text{arrowflow}}} (-1)^{n-1} 
= (-1)^{n-1 } (n-1) \, 2^{n-2}. \]
Or equivalently, that there exists $(n-1) \, 2^{n-2}$ unital arrowflows on $T$. This is immediate as the factor $(n-1)$ counts the number of ways of selecting the edge of $T$ that gives rise to  the anti-parallel repeated arrows, whereas factor $2^{n-2}$ counts the number of ways in which  the remaining $n-2$ edges can be oriented. Finally, to show  that the sign of a unital arrowflow class is $(-1)^{n-1}$,
we show that the underlying permutation of  the unique catalyst that survives the involution process is always an $n$-cycle.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%   Start of 2_Dissconected_NonStandard.tex  %%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Zero-sum arrowflows}
\label{sec: zero-sum}

{\em Where we present a sign-reversing involution without  fixed points on each zero-sum arrowflow class, and conclude that the signed sum of catalyst in such a class is always zero.}\\

This is achieved in Lemma \ref{prop zero-sum}, which  implies that  the signed sum of catalysts in a zero-sum arrowflow class $C(A)$ is zero. This  constitutes one half of Lemma \ref{lem:crucial}.


\begin{lem}\label{prop zero-sum}
Let $A$ be a  zero-sum arrowflow on $T$.   If $A$ is connected, let  $i$ and $j$  be the two preimages of  the repeated arrow $(a,b)$ of $A$. On the other hand, if $A$ is disconnected, we let 
$\{i,j\}$ be an edge of $T$ such that neither $(i,j)$ nor $(j,i)$ is in  $A$. Then, the map $\varphi : {C(A)} \to {C(A)}$
that sends the catalyst
$(\sigma,f) $ to the catalyst $(\sigma \circ (i ~ j),f \circ (i ~j))$ 
is a sign-reversing involution without fixed points.
\end{lem}

%In both Figure \ref{fig: arrowflows} (b) and (c), the distinguished edge is $\{1,2\}$.
\begin{figure}[h]
    \centering
    \includegraphics[height = 5em]{DoubleEdge.pdf}
    \caption{Involution $\varphi$ acting on a zero-sum connected arrowflow $A$. }
    \label{fig: double edge}
\end{figure}

\begin{proof}[Sketch of proof.]



It is enough to show that $f(i)$ is an arc in both $P(j,\sigma(i))$ and  $P(i,\sigma(i)).$ Observe that if $A$ is connected, then  $i,j$ and $a$ lie in one connected component of the graph obtained by deleting from $T$  edge $ \{a, b\}$, while $\sigma(i), \sigma(j)$ and $b$ lie in the other one. See Figure \ref{fig: double edge}.


On the other hand, when $A$ is disconnected, then $P(j,\sigma(i))$ and $P(i,\sigma(i))$ differ in  exactly one arc, either $ (i,j )$ or $(j,i)$. Therefore, since $f(i)$ is neither of them, we conclude that $f(i)$ belongs to both paths. See Figure \ref{fig: disconnected}.
\begin{figure}[h]
    \centering
    \includegraphics[width=\textwidth]{Disconnected.pdf}
    \caption{Involution $\varphi$ acting on zero-sum disconnected arrowflow $A$.}
    \label{fig: disconnected}
\end{figure}

%Hence, in both situations, the involution is well-defined.
\end{proof}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%   Start of 3_Standard.tex  %%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Unital arrowflows}\label{sec: standard}
{\em Where we rely on the    Lindström--Gessel--Viennot Lemma to compute the signed sum of all catalysts in  a unital arrowflow class.}\\

We rely on the following version of the  Lindström--Gessel--Viennot lemma here.
    \begin{lem}[Lindström \cite{Lindstrom}, Gessel--Viennot \cite{Gessel-Viennot}]
        Let $\mathcal{R}$ be an acyclic directed graph. Distinguish two sequences  of nodes  $(v(1),\ldots,v(n))$ and $(v'(1), \ldots,v'(n))$ with no repeated nodes in either of them.        Let $\mathcal{P}$ be the set of all sequences of paths
        $(P_{1}, ..., P_{n})$ for which there exists a permutation $\sigma_P\in\Sym_n$ such that, 
        for each $i$ in $[n]$, the path $P_i$ stars at $v(i)$  and finishes at $v'(\sigma(i))$.
        Then,
        \[
        \sum_{\substack{(P_1, ..., P_n) \in \mathcal{P}}} \sign(\sigma_P) = \sum_{\substack{(P_1, ..., P_n)\in \mathcal{P}\\\text{non-intersecting}}} \sign(\sigma_P).
        \]
    \end{lem}

We break down our argument into three parts. First, we prepare for the application of the Lindström--Gessel--Viennot Lemma and create an acyclic directed graph,  the {\em route map} $\mathcal{R}_A,$  from any unital arrowflow $A$ on $T.$ 
Subsequently, we establish a sign-preserving bijection that sends each catalyst in $C(A)$ to a family of $n$ paths on $\mathcal{R}_A$, which we refer to as \emph{$n$-paths}.  The application of the Lindström--Gessel--Viennot Lemma reduces our original quest to the problem of finding a description of the non-intersecting $n$-paths.
Finally, we establish that in each unital arrowflow class, there exists exactly one catalyst $\kappa$ that generates a non-intersecting $n$-path, and that its underlying permutation of $\kappa$ is always an $n$-cycle. Therefore,  the sole surviving catalyst,  has sign $(-1)^{n-1}$.\\


 \noindent
{\bf  5.1  \ \ \  The route map $\mathcal{R}_A$}.
To construct $\mathcal{R}_A$, the route map of $T$, we proceed in several steps. First, we use arrowflow $A$ to define a plane rooted  directed tree $T_0$. Then, we define the {\em  Southern hemisphere,} an acyclic directed graph; and its anti-isomorphic counterpart, the {\em  Northern hemisphere}. Finally, we add bridges connecting both hemispheres
and pointing from South to North.

\begin{enumerate}[label=Step \arabic{enumi}.,ref=Step \arabic{enumi}]
\label{sec: plane rooted trees}\label{ss:route}
\item 
{\em Construct a   rooted directed tree $A_0$ from   $A$.} \label{it:rooted}

Let  $e = \{a, b\}$ be the edge of $T$ connecting the two vertices appearing in the repeated edge of  $A$. We construct a \textcolor{USred}{\em rooted directed tree $A_0$} from $A$ by
adding a new vertex $r$ as a root and substituting the arcs $(a, b)$ and $(b, a)$ by $(r,b)$ and $(r,a)$ respectively. This construction induces a bijection between arcs of $A$ and $A_0$.
An arc of $A_0$  will be said to be \emph{ascending} if it points to the root, and \emph{descending} if it points away from the root. 
A child node $u$ of a parent node $v$ is termed \emph{ascending} when the associated arc for the edge $\{u, v\}$ is ascending, and \emph{descending} when it is descending. See Figures \ref{T0} (a) and (b). 

We denote  the underlying undirected  rooted tree of $A_0$ by $T_0$.

\item {\em Give a   compatible plane structure  to the 
rooted directed tree   $A_0$.} \label{it:plane}

A plane structure for $A_0$ is said to be \textcolor{USred}{\em compatible} if for each node $v$ with children $u_1, \ldots, u_k$,  every ascending child of $v$ lies \emph{to the left} of every descending child. In general there exist multiple compatible plane structures on $A_0$. We just choose one of them. See Figure \ref{fig: plane rooted tree} (c).

\begin{figure}[h]
    \centering
    \scriptsize
    \begin{tabular}{ccc}
        \textbf{(a)} & \textbf{(b)} & \textbf{(c)} \vspace{0.5em} \\
        \includegraphics[width = 0.2\textwidth]{arrowflowUnital.pdf}
        %\arrowflowUnital
        & 
        \includegraphics[width = 0.2\textwidth]{RootedPlaneB.pdf} & 
        \includegraphics[width = 0.2\textwidth]{RootedPlaneC.pdf} 
    \end{tabular}
    \caption{
    \textcolor{USred}{\textbf{(a)}} A unital arrowflow $A$ with repeated edge $\{1,2\}$.
    \textcolor{USred}{\textbf{(b)}} The rooted directed tree $A_0$ with root $r$.
    \textcolor{USred}{\textbf{(c)}} A compatible plane structure for $A_0$.}
    \label{fig: plane rooted tree}\label{Running_example1}\label{T0}
\end{figure}

The underlying rooted tree $T_0$ inherits a plane rooted tree structure. The neighbors of a vertex $i$ of $T_0$ are ordered starting with the children of $i$ in increasing order (as in the plane structure of $T_0$), and ending with the parent.

\item {\em Construct the   Southern hemisphere of   $T_0$. } \label{it:south}

The \textcolor{USred}{\em  Southern hemisphere $\mathcal{S}(T_0)$} of an undirected plane rooted tree $T_0$ is a directed multigraph whose vertex set is composed of three types of nodes ($v$-node, $e$-node, and $s$-node).
%To construct the set of nodes of $\mathcal{S}(T_0)$ we proceed as follows.
Each node $i$ of $T_0$, including the root, contributes with  a node $v(i)$.   
Each edge $\{i,j\}$ of $T_0$, contributes  two nodes $e(i,j)$ and $e(j,i)$. Finally, we add 
two nodes $s_i(j_{k-1}, j_k)$ and $s_i(j_k, j_{k-1})$ for each vertex $i$ of $T_0$ and each pair of consecutive neighbors $j_{k-1}, j_k$ of $i$. 
%We refer to these nodes as $v$-nodes, $e$-nodes, and  $s$-nodes, respectively.
See Figure \ref{fig: route map}.
%, and note that $e$-nodes and $s$-nodes are represented by arrows.

The arcs of the route map connect these nodes in a natural way, as to allow one to understand the paths of $T_0$ as paths in the route map.  The explicit construction of the set of arcs can be daunting, but these arcs do not need to be included in the graphical representations of $\mathcal{S}(T_0)$ as they can be inferred from the set of nodes.
   
To construct the set of arcs of $\mathcal{S}(T_0)$  we add, for each $i$,   two arcs between $s$-nodes for each three consecutive neighbors $j_{k-1}, j_k, j_{k+1}$, 
%four arcs between $s$-nodes and $e$-nodes for each pair of consecutive neighbors $j_k, j_{k+1}$,
an arc $\left(v(i), s_i(j_1, j_2)\right)$ for each node $i$ that is not a leaf, and an arc $\left(v(i), e(i, j_1)\right)$ for each node $i$.
Additionally, from each $e$-node $e(j,i)$ there is an arc to (at most) two $s$-nodes around $i$, and conversely from each $s$-node $s_i(j_k, j_{k+1})$ to its corresponding $e(i, j_{k+1})$ node.
    
\begin{figure}[h]
    \centering\scriptsize
    \begin{tabular}{ccc}
        \textbf{(a)} & \textbf{(b)} & \textbf{(c)} \vspace{0.5em} \\
        \includegraphics[width = 0.2\textwidth]{RouteMapA.pdf} & 
        \includegraphics[width = 0.2\textwidth]{RouteMapB.pdf} & 
        \includegraphics[width = 0.2\textwidth]{RouteMapC.pdf} 
    \end{tabular}
    \caption{
    Highlighted, the sets of
    \textcolor{USred}{\textbf{(a)}}  $v$-nodes,
    \textcolor{USred}{\textbf{(b)}}  $e$-nodes, and
    \textcolor{USred}{\textbf{(c)}}  $s$-nodes of $\mathcal{S}(T_0)$.}
    \label{fig: route map}\label{Running_example2}
\end{figure}

    
\item {\em Construct the Northern hemisphere, an anti-isomorphic copy of the Southern hemisphere.} \label{it: north}

Let $T_0$ be an undirected plane rooted tree, let $T_{0}'$ be its \textcolor{USred}{\em mirror image}; a copy of $T_{0}$ in which local orders are inverted.   The \textcolor{USred}{\em Northern hemisphere} $\mathcal{N}(T_{0})$ of $T_{0}$ is constructed from $\mathcal{S}(T_{0}')$  by replacing  each arc $\left(v(i), e(i,j_1)\right)$ by the arc $\left(e(j_1, i), v(i)\right)$, and, whenever $i$ is not a leaf,  replacing  arc $\left(v(i), s_i(j_1, j_2)\right)$ by the arc $\left(s_i(j_2, j_1), v(i)\right).$
 We denote nodes of $\mathcal{N}(T_{0})$ using primed letters.



\item {\em Construct the route map $\mathcal{R}_A$.}

The  \textcolor{USred}{\em route map $\mathcal{R}_A$} of the unital arrowflow $A$ is the directed multigraph obtained by adding to $\mathcal{S}(T_{0})\cup \mathcal{N}(T_{0})$ 
an arc $\left(e(u,v), e'(u,v)\right)$ for each arc $(u,v)$ of $A_0$.
These arcs are referred to as the \textcolor{USred}{\em bridges} between hemispheres of   $\mathcal{R}_A$.  
\end{enumerate}

The key property of the route map $\mathcal{R}_A$   is that it is always  acyclic. The Southern hemisphere $\mathcal{S}(T_0)$ is acyclic because any cycle in $\mathcal{S}(T_0)$ would induce a cycle in the rooted  plane tree $T_0$. The Northern hemisphere $\mathcal{N}(T_0)$ is acyclic because it is an anti-isomorphic copy of $\mathcal{S}(T_0)$. Finally, the route map is acyclic because all the bridges point from South to North.\\

\noindent
{\bf 5.2 \ \ \ Catalyst and $n$-paths.}
Let $A$ be  a unital arrowflow, and  $(\sigma, f)$ be a catalyst in $C(A)$.
Let $\Lambda_i$ be the unique path of $\mathcal{R}_A$ going from $v(i)$ to $v'(\sigma(i))$ and passing through the bridge $(e(u_i,v_i),e'(u_i,v_i))$, where $(u_i,v_i)$ is the arc of $A_0$ defined by $ f (i)$. See Figure \ref{fig: lift of one path}.

\begin{figure}[h]
    \centering
    \scriptsize
    \begin{tabular}{ccc}
         \textbf{(a)} &\hspace{1cm} &\textbf{(b)}\vspace{0.5em} \\ 
            \includegraphics[width = 0.18\textwidth]{catalystUnitalOnePath.pdf}
            %\catalystUnitalOnePath
        & &
        \includegraphics[width = 0.2\textwidth]{LiftSouth.pdf} \includegraphics[width = 0.2\textwidth]{LiftNorth.pdf}
    \end{tabular}
    \caption{\textbf{(a)} A path $P(9,\sigma(9)=1)$ marked at $f(9) = (4,1)$. \textbf{(b)} The path $\Lambda_9$ of $\mathcal{R}_A$.}
    \label{fig: lift of one path}
\end{figure}



We define the {\em n-path induced by  catalyst $\kappa = (\sigma, f)$} on the route map $\mathcal{R}_A$   as $
\Lambda(\kappa)= \{\Lambda_1, \ldots, \Lambda_n\}
$, and say that $\kappa$ has been lifted to the $n$-path $\Lambda(\kappa)$.
One can recover the permutation $\sigma$ from $\Lambda(\kappa)$. Thus we define $\sign(\Lambda(\kappa))$ as $\sign(\sigma)$.

\begin{ex}
Let $\kappa$ be the catalyst of Figure \ref{fig: catalysts} (a). Figure \ref{Fig: lift} (b) illustrates the $n$-path induced by $\kappa$, where we mark path $\Lambda_i$  with subscript $i$. 
Moreover, since each node in the route map belongs to at most one path, it is an example of a non-intersecting $n$-path.
\end{ex}


 
\begin{figure}[h]
    \centering
    \scriptsize
    \begin{tabular}{ccc}
        \textbf{(a)} & & \textbf{(b)}\\
        \raisebox{.1\height}{\includegraphics[width = 0.18\textwidth]{catalystUnital.pdf}} & \hspace{1cm} &
        \includegraphics[width = 0.25\textwidth]{LiftA.pdf} 
        \includegraphics[width = 0.25\textwidth]{LiftB.pdf}
    \end{tabular}
        \caption{\textbf{(a)} A catalyst and \textbf{(b)} its induced $n$-path $\Lambda(\kappa)= \{\Lambda_1, \ldots, \Lambda_n\}$.
 }
    \label{Fig: lift}
\end{figure}




We say that an  $n$-path is  {\em full} when every bridge $(e(u, v), e'(u, v))$ belongs to exactly one of its paths. Since any $n$-path that is not full must contain an intersection at some bridge, non-intersecting $n$-paths are always full. Moreover, the lifting of any catalyst belonging to a unital arrowclass  is always full.

\begin{lem}\label{lem: lifting is bijective}
    The operation of lifting defines a permutation-preserving bijection between the set  of catalysts with unital arrowflow $A$ and the set of full $n$-paths of $\mathcal{R}_A$.
\end{lem}
\begin{proof}[Sketch of proof.]

To prove that the lifting map is a bijection, we define its inverse.
Any $n$-path $P$
defines a permutation $\sigma$, where $P_i$ is a path from $v(i)$ to $v'(\sigma(i))$.
On the other hand, we use the bridges of $P$ to define a map $f : [n] \to E^{\pm}$.
If the arc $e$ defining the bridge of $P_i$ does not include the root, we define 
$f(i) = e$. Otherwise, we let $f(i)$ be the repeated edge with the appropiate orientation.
It can be shown  that $(\sigma,f) \in C(A)$ and, that the map we just defined is the inverse  of the lifting map. 
Since the underlying permutation of a catalyst is the  permutation induced by its lifting, we conclude that
the lifting map is a permutation-preserving  bijection.
\end{proof}

 
Lemma \ref{lem: lifting is bijective} allows us to rewrite  Equation~\eqref{crucial_result}    as 
 $
\sum_{\kappa\in C(A)} \sign(\kappa) =
\sum \sign(\Lambda),
$
where the second sum is taken over the set of full $n$-paths on 
$\mathcal{R}_A.$\\

\noindent
{\bf 5.3 \ \  There is an unique catalyst  inducing a non-intersecting $n$-path.} Moreover, its underlying permutation is always an $n$-cycle.
\begin{p} \label{prop:nonintersecting}
    Let $A$ be a unital arrowflow on $T$. Consider all $n$-paths in the route map $\mathcal{R}_A$ induced by catalysts in $C(A)$.
    There exists precisely one catalyst inducing a non-intersecting $n$-path in $\mathcal{R}_A$. Its underlying permutation is an $n$-cycle. Therefore, its sign is $(-1)^{n-1}$.
\end{p}
\begin{proof}[Sketch of proof.]
    Fix a plane rooted tree $A_0$ and let $\Lambda$ be an $n$-path. Assume $\Lambda$ is the lift of catalyst $(\sigma, f)$.
 Consider the set $\mathcal{E}$ consisting of the $e$-nodes appearing in the paths of  $\Lambda$. We can show that $\mathcal{E}$ uniquely determines the catalyst $(\sigma, f)$.
 On the other hand, for each arc $(i,j)$ of $A_0$, the set $\mathcal{E}$ contains both $e(i,j)$ and $e'(i,j)$. Furthermore, if $\Lambda$ is non-intersecting, a counting argument allows us to show that $(i,j)$ is ascending if and only if $\mathcal{E}$ contains $e'(j,i)$, and  descending if and only if it contains $e(j,i)$. This gives uniqueness.
    
 The argument concludes by noting that the underlying permutation of the sole catalyst inducing a non-intersecting $n$-path is always an $n$-cycle, and that  the depth-first search algorithm allows us to explicitly describe this cycle, as illustrated in Figure \ref{deep_first}. 
\end{proof}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.25\textwidth]{DepthFirst.pdf}
        \caption{Applying the depth-first search algorithm to this rooted tree results in the word $r \, 1  \, 3  \, 1 \, 4 \, 8 \, 4 \, 7 \, 4 \, 9 \, 4  \, 1  \, r  \, 2  \, 6  \, 2  \, 5  \, 2 \, r$,  which we identify with the cycle
        $(3\, 8\, 4\, 7\, 9\, 1\, 6\, 2\, 5)$. }
    \label{deep_first}
\end{figure}

\begin{ex} Figure
\ref{deep_first} illustrates how the depth-first search algorithm describes the non-intersecting path in the route map $\mathcal{R}_A$
of our running example.
 

\end{ex}

The   Lindström--Gessel--Viennot
Lemma \cite{Gessel-Viennot, Lindstrom} allows us to conclude that when we perform the signed sum of all catalysts in a unital arrowflow class, catalysts that induce intersecting $n$-paths on $\mathcal{R}_A$ cancel each other out.
Finally, since the unique non-intersecting $n$-path has as its underlying permutation an $n$-cycle,  the signed sum of catalysts in a unital arrowflow class is equal to  $(-1)^{n-1}$, which concludes the proof of Lemma \ref{lem:crucial}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%   Start of 4_Generalizations.tex  %%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Beyond the Graham--Pollak formula}\label{sec: generalizations}
{\em Where we show  that our combinatorial proof of the Graham--Pollak formula not only establishes a solid framework for the understanding of the existing generalizations but also paves the way for the creation of new ones. }\\

Various generalizations of the Graham--Pollak formula exist in the literature. In \cite{BapatKirklandNeumann}, a version of this formula is presented for simple trees with weighted edges, while the situation of arc-weighted trees is treated in \cite{BapatLalPati2009}. In both cases, the weight of a path  is defined as the sum of the weights of its edges.
In contrast, using $q$-integers to define the vertex distance results in $q$-analogues of the results. Simple trees obey the $q$-Graham--Pollak formula $ (-1)^{n-1}(n-1)(1+q)^{n-2}$  \cite[Cor. 2.3]{YanYeh:2007}, and a $q$-analogue for trees weighted with integers is given in \cite[Thm. 2.4]{YanYeh:2007}. 
There also exist $q$-analogues for the Graham--Pollak formula when $T$ is arc-weighted with integers \cite[Thm. 3.1]{BapatLalPati2009}, or over a commutative ring \cite[Thm. 4]{ZhouDing}, or with matrices over a commutative ring \cite[Thm. 7]{ZhouDing}.

We  present a new generalization of the Graham--Pollak formula. Towards this end, we define a {\em $q$-sum},  denoted by $\qcircle$,  as
$
a \qcircle b = a + b + (q-1)ab.
$
This operation allows us to simplify \cite[Thm. 2.4]{YanYeh:2007}, by noting that $[1]_q = 1$ and $[a+b]_q = [a]_q\qcircle [b]_q$.
More crucially, the $q$-sum operation is well-defined over any commutative ring, and not just integers. This makes our setting more general.

Let $e^+$ and $e^-$ be the arcs originating from  edge $e$, and let $E^{\pm}$ be the set of arcs of $T$.
Let $R$ be a commutative ring, and  $\alpha:E^{\pm}\to R[q]$ be a weight function. Let  the $(i_k,i_{k+1})$'s be the arcs in the unique path from $i=i_0$ to $j=i_{d(i,j)}$. Define the {\em $q$-distance} between vertices $i$ and $j$ as
$
d_q(i,j) =  \alpha (i, i_1)
\qcircle
\alpha( i_1, i_2 )
\qcircle \cdots \qcircle
\alpha (i_{d(i,j)-1}, j).
$
For any arc $a$ of $E^{\pm}$, we write $\alpha_a$ for $\alpha(a)$. Then, the following theorem holds.

\begin{thm}\label{thm: Luis}
The determinant of the $d_q$-distance matrix of a tree $T$ is
    \[
    (-1)^{n-1} \sum_{e\in E} \Big(\alpha_{e^+}\alpha_{e^-}\prod_{\substack{f\in E\\ f\ne e}} (\alpha_{f^+}\qcircle \alpha_{f^-})\Big).
    \]
 
\end{thm}

Before discussing this result's proof, it's worth noting that the same argument  provides a combinatorial proof for the very general Choudhury--Khare formula \cite[Thm. A]{CK19}.
It is interesting to note that  while the Choudhury--Khare's generalization  is, in some precise sense, the most general possible \cite[Example 1.13]{CK19}, Theorem \ref{thm: Luis} stands independently from this framework. It represents the most natural simultaneous generalization of \cite[Thm. 4]{ZhouDing} and \cite[Thm. 2.4]{YanYeh:2007}, as depicted in the diagram appearing in  Figure \ref{fig: generalizations}.


\begin{figure}[h]
    \centering
    \vspace{-1em}
    \[
    \begin{tikzcd}[column sep=large]
    {\substack{\text{\cite[p. 2511]{GrahamPollak}}\\\text{Graham--Pollak}}} &
    {\substack{\text{\cite[Cor. 2.5]{BapatKirklandNeumann}}\\\text{weighted edges}}} \arrow[l, "\alpha_{ij} = 1"'] &
    {\substack{\text{\cite[Thm. 4]{ZhouDing}}\\\text{weighted arcs}}} \arrow[l, "\alpha_{ij} = \alpha_{ji}"'] \\
    {\substack{\text{\cite[Cor. 2.3]{YanYeh:2007}}\\\text{$q$-Graham--Pollak}}} \arrow[u, "q=1"]&
    {\substack{\text{\cite[Thm. 2.4]{YanYeh:2007}}\\\text{weighted edges, $q$-sum  }}} \arrow[l, "\alpha_{ij} = 1"'] \arrow[u, "q=1"]&
    {\substack{\text{Thm. \ref{thm: Luis}}\\\text{weighted  arcs, $q$-sum}}} \arrow[l, "\alpha_{ij} = \alpha_{ji}"'] \arrow[u, "q=1"]
    \end{tikzcd}
    \]\vspace{-1em}
    \caption{Relationship between the formulas found in the literature.}
    \label{fig: generalizations}
\end{figure}

Both Theorem \ref{thm: Luis} and  the Choudhury--Khare formula \cite[Thm. A]{CK19} readily follow from our combinatorial construction. In both situations, we want to compute the determinant of an appropriate matrix $M'(T)$. Towards this end, we define a weight function on the catalyst set of $T$, in such a way that the determinant of  $M'(T)$ does the weighted  ($q$-) sum of all catalysts, as in Equation \ref{main_eq}. 

To show that the weighted  ($q$-) sum of all catalysts in a zero-sum arrowflow class is zero, we show  that the involution $\varphi$ defined in Section \ref{sec: zero-sum} is weight-preserving.
On the other hand, we use the constructions presented in Section \ref{sec: standard} to compute the weighted  ($q$-) sum of all catalysts in a unital arrowflow class.   For this, we assign weights to the edges of the route map $\mathcal{R}_A$, and show that the lifting map is weight-preserving. A weighted version of the Lindström--Gessel--Viennot Lemma allows us to conclude that  $\det M'(T)$ does a weighted ($q$-) sum of non-intersecting $n$-paths within $\mathcal{R}_A$.
 Finally, we use the characterization of the sole catalyst inducing a non-intersecting $n$-path on $\mathcal{R}_A$ obtained in Proposition \ref{prop:nonintersecting}  to deduce the desired formula for the determinant of $M'(T)$.

%\newpage

\acknowledgements{
We  dedicate this work to Ira Gessel as a token of our gratitude for his lecture on the Lindström--Gessel--Viennot lemma, which he virtually  delivered at the University of Seville in March of 2022. The senior authors would also like to express their gratitude to Xavier Viennot for the entrancing memories of his lectures.\\

This work has been partially    supported    by    the    Grant    PID2020-117843GB-I00    funded    by MICIU/AEI/10.13039/501100011033 and by P2001056 (Junta de Andalucía,  FEDER, PAIDI2020).}

\printbibliography



\end{document}
