\documentclass[finalversion]{FPSAC2025}
\articlenumber{45}
%\usepackage[margin=1in]{geometry}
%\usepackage{amsthm,xcolor, bm}
%\usepackage{latexsym,amssymb,amsfonts,amsmath,graphicx, url,mathtools}
%\usepackage[mathscr]{eucal}
%\usepackage{mathrsfs}
%\usepackage[vcentermath,enableskew]{youngtab}
\usepackage{color}
\usepackage{tikz,hyperref}
%\usepackage[margin=1in]{geometry}
%\usepackage{enumerate,textcomp, wasysym, enumitem}

%\usepackage{parskip}

\usepackage{amsmath}
\usepackage{amsfonts}

\usepackage[backend=bibtex, giveninits]{biblatex}

\addbibresource{main.bib}



\RequirePackage{xcolor}
\usepackage{tikz}
\usepackage{tikz-cd}
\usetikzlibrary{decorations.pathreplacing,decorations.markings}
\newcommand{\red}[1]{{\color{red}#1}}







\tikzset{
  % style to apply some styles to each segment of a path
  on each segment/.style={
    decorate,
    decoration={
      show path construction,
      moveto code={},
      lineto code={
        \path [#1]
        (\tikzinputsegmentfirst) -- (\tikzinputsegmentlast);
      },
      curveto code={
        \path [#1] (\tikzinputsegmentfirst)
        .. controls
        (\tikzinputsegmentsupporta) and (\tikzinputsegmentsupportb)
        ..
        (\tikzinputsegmentlast);
      },
      closepath code={
        \path [#1]
        (\tikzinputsegmentfirst) -- (\tikzinputsegmentlast);
      },
    },
  },
  % style to add an arrow in the middle of a path
  mid arrow/.style={postaction={decorate,decoration={
        markings,
        mark=at position .5 with {\arrow[#1]{stealth}}
      }}},
}



















\newtheorem{thm}{Theorem}[section]
\newtheorem{df}[thm]{Definition}
\newtheorem{eg}[thm]{Example}
\newtheorem{lm}[thm]{Lemma}
\newtheorem{coro}[thm]{Corollary}
\newtheorem{prp}[thm]{Proposition}
\newtheorem{prob}[thm]{Problem}
\newtheorem{rmk}[thm]{Remark}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{question}[thm]{Question}
\newtheorem*{theorem1*}{\Cref{thm:main}}
\newtheorem*{theorem2*}{\Cref{thm:specialize}}
 \newcommand{\acts}{\lefttorightarrow}
\newcommand{\C}{\mathbb{C}}
\newcommand{\1}{\mathbb{1}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\p}{\mathbb{P}}
\renewcommand{\S}{\mathfrak{S}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\GL}{\textup{GL}}
\newcommand{\End}{\textup{End}}
\renewcommand{\a}{\mathfrak{a}}
\renewcommand{\b}{\mathfrak{b}}
\renewcommand{\c}{\mathfrak{c}}
\newcommand{\cc}{\mathcal{C}}
\newcommand{\dd}{\mathcal{D}}
\newcommand{\m}{\mathfrak{m}}
\renewcommand{\p}{\mathfrak{p}}
\renewcommand{\P}{\mathfrak{P}}
\newcommand{\q}{\mathfrak{q}}
\renewcommand{\bar}{\overline}
\renewcommand{\hat}{\widehat}
\newcommand{\Hom}{\textup{Hom}}
\newcommand{\eps}{\varepsilon}
\newcommand{\Sym}{\mathrm{Sym}}
\newcommand{\wt}{\mathrm{wt}}

\title{Arborescences of Random Covering Graphs}

\author{\texorpdfstring{Muchen Ju, Junjie Ni, Kaixin Wang, and Yihan Xiao}{Muchen Ju, Junjie Ni, Kaixin Wang, and Yihan Xiao}}
\author[Ju, Ni, Wang \and Xiao]{\texorpdfstring{Muchen Ju\addressmark{1} , Junjie Ni\addressmark{2} , Kaixin Wang\addressmark{3}, \and Yihan Xiao\addressmark{4}}{Muchen Ju , Junjie Ni , Kaixin Wang, and Yihan Xiao}}
\address{\addressmark{1}Department of Mathematics, Fudan University, 220 Handan Rd, Shanghai, China \\ \addressmark{2}Department of Mathematics, Nankai University, 94 Weijin Rd, Tianjin, China \\ \addressmark{3}Department of Mathematics, Duke University, 113 Edens Dr, Box 99043, Durham, NC \\ \addressmark{4}School of Science, Shanghai University, 99 Shangda Rd, Shanghai, China}
\received{\today}
\date{July 2024}


\abstract{
A rooted arborescence of a directed graph is a spanning tree directed towards a particular vertex. A recent work of Chepuri et al.\ showed that the arborescences of a covering graph of a directed graph $G$ are closely related to the arborescences of $G$. In this paper, we study the weighted sum of arborescences of a random covering graph and give a formula for the expected value, resolving a conjecture of Chepuri et al.
}


\begin{document}

\maketitle

\section{Introduction}

%Why do we care about covering graphs
%Covering space is a fundamental concept in topology
%A graph $\tilde \Gamma$ is a covering graph of $\Gamma$ defined in the topological sense; see section XX for details
% in [xxx] Tucker&xxx gave a combinatorial characterization of coverign graphs using permutation voltages.

For a weighted directed graph $\Gamma$, an \emph{arborescence rooted at a vertex} $v$ is a spanning tree whose edges are directed towards $v$. The weight of an arborescence is the product of the edge weights. We define $A_v(\Gamma)$ to be the weighted sum of all arborescences rooted at $v$.

Covering graphs are central objects in topological graph theory motivated by the notion of covering spaces in topology. A weighted digraph $\tilde \Gamma$ is a covering graph of $\Gamma$ defined in the topological sense (see section \ref{section3} for details). The fundamental work of Gross--Tucker \cite{Tucker} gave a characterization of covering graphs by permutation voltage assignments.

In their study of $R$-systems, Galashin and Pylyavskyy \cite{Galashin} observed that the ratio of arborescences of a covering graph and its base graph $\frac{A_{\tilde v}(\tilde \Gamma)}{A_v(\Gamma)}$ is invariant of the choice of the root $v$. More recently, Chepuri et al. \cite{Sylvester} further investigated the ratio and proved that it is always an integer-coefficient polynomial in the edge weights of the base graph $\Gamma$ conjecturally with positive coefficients. Following up these works, we study the expected value of the ratio $\frac{A_{\tilde v}(\tilde \Gamma)}{A_v(\Gamma)}$ when $\tilde \Gamma$ is taken to be a random covering graph. Our main theorem is a formula for its expected value, affirming Conjecture 5.6 of \cite{Sylvester}. %In doing so, we carry out a more refined analysis of the ratio  $A_{\tilde v}(\tilde \Gamma)\over A_v(\Gamma)$ when $\tilde \Gamma$, providing potential insights to the positivity phenomenon.

\begin{thm}\label{main thm}
        Let $\Gamma = (V,E,\wt)$ be a weighted digraph, and $k$ be a positive integer. We choose a permutation voltage $\sigma_e$ in the symmetric group $ S_k$ for each edge $e\in E$ independently and uniformly at random. The random voltages allow us to construct our random $k$-fold covering graph $\tilde{\Gamma}$. Then 

        $$ \E\left[\frac{A_{\tilde v}(\tilde \Gamma)}{A_v(\Gamma)}\right] = \frac 1k \prod_{w\in V} \left( \sum_{\alpha \in E_s(w)} \wt(\alpha)\right)^{k-1}$$

        where $E_s(w)$ is the set of edges in $\Gamma$ with source $w$. 
\end{thm}

The paper is organized as follows. In section \ref{section2} we introduce the relevant background in graph theory, including the Matrix-Tree Theorem. In section \ref{section3}, we state the definition of covering graphs and review the theory of arborescence ratio in \cite{Sylvester}. In section \ref{section4} we prove our main result, \Cref{main thm}. %In section 5 we conclude our paper with a discussion of future directions.

\section{Background On Graph Theory}\label{section2}

In this paper, we consider directed multigraphs, or \emph{digraphs} for short. Unless otherwise stated, we consider digraphs with weighted edges.
\begin{df}
    Let $G = (V,E,\wt)$ be a weighted digraph with $V = \{v_1,\cdots,v_{|V|}\}$. For a vertex $v\in V$, define $E_s(v)$ to be the set of edges with source $v$ and $E_t(v)$ to be the set of edges with terminal $v$. The \emph{degree matrix} $D$ of $G$ is the $|V|\times |V|$ diagonal matrix with $$D[v_i, v_i] = \sum_{e\in E_s(v_i)} \wt(e)$$
    
    for all $v_i\in V$. The \emph{adjacency matrix} $A$ of $G$ is defined as $$A[v_i,v_j] = \sum_{e=(v_i\to v_j)} \wt(e) $$ for all $v_i,v_j \in V$. The \emph{Laplacian matrix} $L$ of $G$ is defined as $D-A$.
\end{df}

\begin{eg}\label{eg:basic}
    Let $G$ be a weighted digraph with vertex set $\{1,2,3\}$, with only one edge from $i$ to $ j$ (not necessarily distinct) in $V(G)$ with weight $x_{ij}$ for all $i,j \in \{1,2,3\}$. Then $$ D = \begin{bmatrix}
        x_{11} + x_{12} + x_{13} & 0 & 0 \\
        0 & x_{21} + x_{22} + x_{23} & 0 \\
        0 & 0 & x_{31} + x_{32} + x_{33}
    \end{bmatrix}$$

    $$ A = \begin{bmatrix}
        x_{11} & x_{12} & x_{13} \\
        x_{21} & x_{22} & x_{23} \\
        x_{31} & x_{32} & x_{33}
    \end{bmatrix}.$$

    Hence $$ L = D - A = \begin{bmatrix}
         x_{12} + x_{13} & -x_{12} & -x_{13} \\
        -x_{21} & x_{21} + x_{23} & -x_{23} \\
        -x_{31} & -x_{32} & x_{31} + x_{32} 
    \end{bmatrix}.$$
\end{eg}

Note that the Laplacian is always a singular matrix, since the sum of entries in each row is 0.

\begin{df}
    An \emph{arborescence} $T$ of a weighted digraph $\Gamma$ rooted at $v\in V$ is a spanning tree directed towards $v$. The \emph{weight} of an arborescence is the product of the weights of its edges:

    $$ \wt(T) = \prod_{e\in T} \wt(e).$$

    We define $A_v(\Gamma)$ to be the sum of weights of all arborescences.
\end{df}
The Matrix-Tree Theorem \cite{Fomin} relates the minors of the Laplacian and the arborescences. 
\begin{thm}  [Matrix-Tree Theorem \cite{Fomin}] 
    Let $G$ be a weighted digraph on $\{1,\cdots,n\}$.  Then 

    $$ A_i(G) = \det(L(G)_i^i) $$

    for all $i\in \{1,\cdots,n\}$. Here $L(G)_i^i$ is the Laplacian matrix $L(G)$ with row $i$ and column $i$ removed.
\end{thm}

\begin{eg}
    In example \ref{eg:basic} with $n=3$, 

    $$ L_1^1 = \begin{bmatrix}
        x_{21} + x_{23} & -x_{23}\\
        -x_{32} & x_{31} + x_{32}
    \end{bmatrix}.$$

    Then $$\det(L_1^1) = (x_{21}+x_{23})(x_{31}+x_{32}) - (-x_{23})(-x_{32}) = x_{21}x_{31} + x_{23}x_{31} + x_{21}x_{32} = A_1(G).$$

    The last equality holds since there are 3 arborescences rooted at $1$: namely $2,3\to 1, 2\to 3\to 1$ and $3\to 2\to 1$. 
\end{eg}


\section{Covering Graphs}\label{section3}






A \emph{$k$-fold cover} of a weighted digraph $\Gamma = (V, E,\wt)$ is a weighted digraph $\tilde{\Gamma} = (\tilde{V}, \tilde{E},\wt)$ that is a $k$-fold covering space of $G$ in the topological sense that preserves edge weight. That is, we require that a lifted edge in the covering graph to have the same weight as its corresponding base edge in the base graph. In order to use this definition, we need to find a way to formally topologize directed graphs in a way that encodes edge orientation. To avoid this, we instead give a more concrete alternative definition of a covering graph.

\begin{df}  Let $k$ be a positive integer and $\Gamma = (V,E,\wt)$ be a weighted digraph. A weighted digraph $\tilde{\Gamma} = (\tilde{V}, \tilde{E}, \wt)$ is a \emph{$k$-fold covering graph} of $\Gamma$ if there exists a projection map $\pi: \tilde{\Gamma} \rightarrow \Gamma$ such that
\begin{enumerate}[nosep]
    \item $\pi$ maps vertices to vertices and edges to edges;
    \item $|\pi^{-1}(v)| = |\pi^{-1}(e)| = k$ for all $v \in V, e \in E$;
    \item If $\tilde e\in \tilde E$ is an edge from $\tilde v$ to $\tilde w$, then $\pi(\tilde e) $ is an edge from $\pi(\tilde v)$ to $\pi(\tilde w)$;
    \item For all $\tilde{e} \in \tilde{E}$, we have $\wt(\tilde{e}) = \wt(\pi(\tilde{e}))$;
    \item $\pi$ is a local homeomorphism.  Equivalently, \[ |E_s(\tilde{v})| = |E_s(\pi(\tilde{v}))| \quad \text{ and } \quad |E_t(\tilde{v})| = |E_t(\pi(\tilde{v}))| \] for all $\tilde{v} \in \tilde{V}$.
\end{enumerate}
When we refer to $\tilde{\Gamma}$ as a covering graph of  $\Gamma$, we fix a distinguished projection $\pi: \tilde{\Gamma} \rightarrow \Gamma$. 
\end{df}

 We do not require a covering graph to be connected. However, disconnected graphs contain no arborescences, so our main quantity of interest $A_{\tilde v}(\tilde{\Gamma})$ is always $0$ in the disconnected case. 

\begin{df} Fix an integer $k$. A \emph{weighted permutation-voltage graph} $\Gamma = (V, E, \wt, \nu)$ is a weighted directed multigraph with each edge $e$ also labeled by a permutation $\nu(e) = \sigma_e\in S_k$, the symmetric group on $k$ letters. This labeling is called the \emph{voltage} of the edge $e$. Note that the voltage of an edge $e$ is independent of the weight of $e$.
\end{df}

\begin{df}\label{df:coveringGraph} Let $\Gamma = (V,E,\wt)$ be a weighted digraph with a permutation in $\sigma_e \in S_k$ for every $e\in E$, the \emph{$k$-fold covering graph $\tilde{\Gamma} = (\tilde{V}, \tilde{E}, \wt)$ associated to} $(\sigma_e)_{e\in E}$ is a digraph with vertex set $\tilde{V} = V \times \{1,2,\ldots,k\}$ and edge set
\begin{align*}
    \tilde{E}:=\left\{\left(v \times x, w \times \sigma_e(x)\right) : x \in \{1,\ldots,k\}, e=(v,w)\in E\right\}.
\end{align*}
For an edge $e=(v,w)$ of weight $\wt(e)$, all corresponding $\left(v \times x, w \times \sigma_e(x)\right)$ also have weight $\wt(e)$. 
\end{df}

\begin{thm}[\cite{Tucker}, Gross--Tucker's characterization]
    Every covering graph of $\Gamma$ can be constructed from a permutation voltage graph $\Gamma$. 
\end{thm}

By this characterization result, we can use only definition \ref{df:coveringGraph} to analyze $k$-fold covering graphs from now on.

\begin{eg}\label{ex:perm}
Let $\Gamma$ be the permutation-voltage graph shown in \Cref{fig:perm-voltage-graph}, where edges labeled $(w, \sigma)$ have edge weight $w$ and voltage $\sigma \in S_3$. Then we can construct a $3$-fold cover $\tilde{\Gamma}$, with vertices $(v, y) = v^y$ and with edges labeled by weight, is shown in \Cref{fig:perm-derived-graph}.
\input{covering_graph_by_Sylvester/Santa_hat}
\input{covering_graph_by_Sylvester/Santa_hat_covering}
\end{eg}










\newpage Given $v\in V(\Gamma)$, for any   $\tilde v \in V(\tilde \Gamma)$ that projects to $v$, $\frac{A_{\tilde v}(\tilde \Gamma)}{A_v(\Gamma)}$ is independent of $\tilde v$. We call this ratio $R(\tilde \Gamma)$. This ratio has an explicit formula in \cite{Sylvester} as follows.



\begin{df}\label{lowerright}
Let $\{v_1,\cdots,v_n\}$ be the set of vertices of our digraph $\Gamma$, let $\tilde \Gamma$ be a $k$-fold cover of $\Gamma$, where vertex $v_i$ is lifted to $v_i^1,\cdots,v_i^k$.
Define $n(k-1)\times n(k-1)$ matrices $D$ and $\mathcal{A}$ with basis vectors $v_1^2,\cdots,v_1^{k}, v_2^2,\cdots,v_2^{k}, \cdots, v_n^2, \cdots, v_n^{k}$,  as follows.
\[\mathcal{A}[v_i^t,v_j^r]=\sum_{e=(v_i^t\to v_j^r)}\wt(e)-\sum_{e=(v_i^t\to v_j^1)}\wt(e)\]
\[D[v_i^t,v_i^t]=\sum_{e\in E_s(v_i^t)}\wt(e)\]
for $1<t,r\leq k$ and $1\le i,j\le n$. Finally, we define
\[ \mathcal{L}(\tilde{\Gamma}):=D-\mathcal{A}\]
\end{df}

 to be the \emph{voltage Laplacian} of $\tilde{\Gamma}$.

\begin{thm}[\cite{Sylvester}]\label{bigboi}
	Let $\Gamma = (V, E, \wt)$ be an weighted digraph, and let $\tilde{\Gamma}$ be a $k$-fold cover of $\Gamma$ such that each lifted edge is assigned the same weight as its base edge. Denote by $\mathcal{L}(\Gamma)$ the voltage Laplacian of $\Gamma$. Then for any vertex $v$ of $\Gamma$ and any lift $\tilde{v}$ of $v$ in  $\tilde \Gamma$ , we have
	\begin{align*}
		\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_v(\Gamma)} = \frac{1}{k}\det  [\mathcal{L}(\tilde{\Gamma})].
	\end{align*}
\end{thm}













\begin{eg}
Returning to figures \ref{fig:perm-voltage-graph} and \ref{fig:perm-derived-graph} as an example. The voltage Laplacian can be written as a linear transformation on the basis vectors $v_1^2,v_1^3,v_2^2,v_2^3,v_3^2,v_3^3$, in this order, with matrix
 $$  \mathcal{L} = \begin{bmatrix}
        b & 0 & 0 & -b & 0 & 0 \\
        a & 2a+b & b & b & 0 & 0\\
        0 & 0 & c & 0 & -c & 0\\
        0 & 0 & 0 & c & 0 & -c \\
        -d & 0 & 0 & -e & d+e & 0\\
        0 & -d & -e & 0 & 0 & d+e\\
    \end{bmatrix}.$$
\end{eg}









\section{Proof of Theorem 1.1} \label{section4}

% Before we prove theorem \ref{main thm}, we revisit a classical proof of the Matrix-Tree Theorem.
% \subsection{Ideas for Proof of Matrix-Tree Theorem}

% Let $G$ be a weighted digraph with vertex set $\{1,\cdots,n\}$, with only one edge between each $i\to j$ in $V(G)$ with weight $x_{ij}$. Then 

%   $$ A_1(G) = \det(L_1^1) $$

% \begin{eg}
%     For $n=3$, 
%     $$ L_1^1 = \begin{bmatrix}
%         x_{21} + x_{23} & -x_{23}\\
%         -x_{32} & x_{31} + x_{32}
%     \end{bmatrix}$$
% \end{eg}

% We want to take a monomial of the form $m = x_{2j_2} x_{3j_3} \cdots x_{nj_n}$. This corresponds to a digraph $M$ with vertex set $\{1,\cdots,n\}$ and edges $t \to j_t$ for $t \in \{2,\cdots,n\}$. This digraph $M$ either has a cycle, or is an in-tree at $1$. 

% We can show the coefficient of $m$ in

% $$ \det(L_1^1) = \sum_{\substack{\sigma \in \Sym(\{2,\cdots,n\})} } sgn(\sigma) \prod_{j=2}^n L_{j,\sigma(j)}$$

% is $\begin{cases}
%     1 & \text{if the digraph } M \text{ is an in-tree at vertex } 1\\
%     0 & \text{otherwise}
% \end{cases}$ 

%\subsection{Proof of Theorem 1.1}
Recall that \Cref{main thm} gives a formula for the expected value of the arborescences ratio $\frac{A_{\tilde v}(\tilde \Gamma)}{A_v(\Gamma)}$ as follows
 $$ \E[R(\tilde{\Gamma})]=\E\left[\frac{A_{\tilde v}(\tilde \Gamma)}{A_v(\Gamma)}\right] = \frac 1k \prod_{w\in V} \left( \sum_{\alpha \in E_s(w)} \wt(\alpha)\right)^{k-1}$$

        where $E_s(w)$ is the set of edges in $\Gamma$ with source $w$. 

Call the vertices of the base digraph  $v_1,\cdots,v_n$ and edges $\{e = (v_i \to v_j, \sigma_e)\}.$

Recall $$ R(\tilde{\Gamma}):= \frac{A_{\tilde v}(\tilde \Gamma)}{A_v(\Gamma)}= \frac 1k \det \mathcal{L} = \frac 1k \det (D-\mathcal{A})$$ 

where $D,\mathcal{A}$ are square matrices with rows/columns labeled $v_1^2,\cdots,v_1^{k}, v_2^2,\cdots,v_2^{k}, $
\\ $\cdots, v_n^2, \cdots, v_n^{k}$, in this order.  


Here $D$ is a deterministic diagonal matrix satisfying $$D[v_i^t, v_i^t] = \sum_{e = (v_i\to v_j)} \wt(e)$$

and $\mathcal{A}$ is a random matrix with

$$ \mathcal{A}[v_i^t, v_j^r] = \sum_{e = (v_i\to v_j), \sigma_e(t) = r} \wt(e) - \sum_{e = (v_i\to v_j), \sigma_e(t) = 1} \wt(e) $$

where the $\sigma_e \in S_k$ are chosen independently and uniformly at random.

Thus, \Cref{main thm} is equivalent to showing that our random matrix $\mathcal{A}$ satisfies $$\E [\det(D-\mathcal{A})] = \det(D).$$ 


Define $S := \{v_1^2,\cdots,v_1^{k}, v_2^2,\cdots,v_2^{k}, \cdots, v_n^2, \cdots, v_n^{k}\} $.

For each edge $e$ of $\Gamma$, let $X_{e,a,b} = \1_{\{ \sigma_e(a)=b\}}$, then we can write 

$$\mathcal{A}[v_i^t, v_j^r] = \sum_{e = (v_i\to v_j)} \wt(e) (X_{e,t,r} - X_{e,t,1}) $$

where we group together $X_{e,t,r},X_{e,t,1}$; we naturally define $Y_{e,t,r} := X_{e,t,r} - X_{e,t,1}$.

\begin{eg}\label{eg:section4}
    Let $\Gamma$ be a digraph on one vertex, with two loops weighted $a,b$. For $k=3$, the matrix $\mathcal{L}=D-\mathcal{A}$ is
%     as follows:

% $$\begin{bmatrix}
%     a+b - a(X_{a,2,2}-X_{a,2,1}) - b(X_{b,2,2}-X_{b,2,1})   & - a(X_{a,2,3}-X_{a,2,1}) - b(X_{b,2,3}-X_{b,2,1})   \\
%     - a(X_{a,3,2}-X_{a,3,1}) - b(X_{b,3,2}-X_{b,3,1})   & a+b - a(X_{a,3,3}-X_{a,3,1}) - b(X_{b,3,3}-X_{b,3,1}) 
% \end{bmatrix}$$
$$\begin{bmatrix}
    a+b - aY_{a,2,2}- bY_{b,2,2}   & - aY_{a,2,3} - bY_{b,2,3}   \\
    - aY_{a,3,2} - bY_{b,3,2}  & a+b - aY_{a,3,3} - bY_{b,3,3}
\end{bmatrix}.$$
Similarly, the matrix $\L(\tilde\Gamma)$ of the digraph in example \ref{ex:perm} is of the form:
 $$   \L(\tilde\Gamma) =\begin{bmatrix}
         a+b - aY_{a,2,2} & - aY_{a,2,3} & -bY_{b,2,2} & -bY_{b,2,3} & 0 & 0 \\
        - aY_{a,3,2} & a+b-aY_{a,3,3} & -bY_{b,3,2} & -bY_{b,3,3} & 0 & 0\\
        0 & 0 & c & 0 & -cY_{c,2,2} & -cY_{c,2,3}\\
        0 & 0 & 0 & c & -cY_{c,3,2} & -cY_{c,3,3} \\
        -dY_{d,2,2} & -dY_{d,2,3} & -eY_{e,2,2} & -eY_{e,2,3} & d+e & 0\\
        -dY_{d,3,2} & -dY_{d,3,3} & -eY_{e,3,2} & -eY_{e,3,3}& 0 & d+e\\
    \end{bmatrix}.$$
\end{eg}

  To compute $\det(\L)$, we first choose a permutation $\rho$ on $S= \{v_i^t \mid 1\le i\le n, 2\le t\le k\}$ to expand; the product corresponding to $\rho$ is $$sgn(\rho)\prod\limits_{\substack{1\le i\le n \\ 2\le t\le k}} \mathcal{L}(\tilde{\Gamma})_{v_i^t, \rho(v_i^t)} .$$ 
  
   We define a \emph{term} to be either $\wt(e)$ that can be found on the diagonal of $\mathcal{L}(\tilde{\Gamma})$ or a $-\wt(e)Y_{e,*,*} $. We expand each $\mathcal{L}(\tilde{\Gamma})_{v_i^t, \rho(v_i^t)}$ into terms; for example, in example \ref{ex:perm}, $\mathcal{L}(\tilde{\Gamma})_{1,1} $ has three terms: $a,b$, and $-aY_{a,2,2}$.

We define a \emph{monomial} to be a product of terms that arise when we expand the product \[ \prod\limits_{\substack{1\le i\le n \\ 2\le t\le k}} \mathcal{L}(\tilde{\Gamma})_{v_i^t, \rho(v_i^t)}. \] For example, in example \ref{ex:perm}, we can have $\rho = (1,3,5,6,2,4)$, and we choose, respectively, terms $a,-bY_{b,3,2}$, $-cY_{c,2,2}$, $-cY_{c,3,3}$, $-dY_{d,2,3}$, $-eY_{e,3,3}$ from $\mathcal{L}_{1,1}$, $\mathcal{L}_{2,3}$, $\mathcal{L}_{3,5}$, $\mathcal{L}_{4,6}$, $\mathcal{L}_{5,2}$, $\mathcal{L}_{6,4}$. The corresponding monomial is, then, $-abc^2de Y_{b,3,2}Y_{c,2,2}Y_{c,3,3}Y_{d,2,3}Y_{e,3,3}$.

For a monomial, we define $F$ to be the set of $wt(e)$'s from the diagonal in the monomial. For each edge $e$, let $n_e$ be the number of terms of the form $-\wt(e) Y_{e,*,*}$ in the monomial, namely $-\wt(e) Y_{e,i_1,j_1},-\wt(e) Y_{e,i_2,j_2}, \cdots, -\wt(e)Y_{e,i_{n_e},j_{n_e}} $.  Thus, the monomial can be written as $$\left(\prod_{e' \in F} \wt(e')\right) \cdot  \prod_{e\in E}  \left(\prod_{l=1}^{n_e}(-\wt(e))Y_{e,i_l,j_l} \right)  .$$

Note that in the formula, both $i_1,\cdots,i_t$ and $j_1,\cdots,j_t$ are pairwise distinct, and take values in $\{2,\cdots,n\}$.

Observe $\det(\mathcal{L})$ is just a signed sum all of these monomials, where the sign comes from the sign of the permutation $\rho$.

Fix a sequence of nonnegative integers $(n_e)_{e\in E}$. We consider monomials where we choose exactly $n_e$ terms of the form $-\wt(e)Y_{e,*,*}$ for every $e\in E$. Every such monomial can be written as
$$ \left(\prod_{e' \in F} \wt(e')\right) \cdot  \prod_{e\in E} (-\wt(e))^{n_e} \cdot \left(\prod_{l=1}^{n_e} Y_{e,i_l,j_l} \right). $$
This means when we sum all these monomials, every term shares the same factor \[ \left(\prod_{e' \in F} \wt(e')\right) \cdot \prod_{e\in E} (-\wt(e))^{n_e}, \] so we only need to look at the expected value of the (signed) sum of the $\prod_{e\in E} \prod_{l=1}^{n_e} Y_{e,i_l,j_l} $.

If $n_e = 0$ for all $e\in E$, then we only choose terms of the form $\wt(e)$ in the monomial; we did not choose any term of the form $-\wt(e)Y_{e,*,*}$. In this case, we have chosen terms arising only from $D$, and we must have $\rho=id\in S_k$. Thus the sum of all these terms is $\det(D)$. We did not need to take an expectation, since these terms are deterministic.

It remains to show if there exists $e\in E$ such that $n_e>0$, then the corresponding sum is $0$.  



\begin{prp}\label{prp:expect}
    Let $e\in E$ be a fixed edge, $t \in \{1,\cdots,n-1\}$ be a fixed integer. Fix distinct $i_1,\cdots,i_t \in \{2,\cdots,n\}$, distinct $j_1,\cdots,j_t \in \{2,\cdots,n\}$ and a bijection $\pi \colon \{i_1,\cdots,i_t\} \to \{j_1,\cdots,j_t\}$. Then $$ \E\left[\prod_{l=1}^t Y_{e,i_l, \pi(i_l)}\right]$$ depends only on $t$; furthermore when $t=1$ the this is equal to 0.
\end{prp}

\begin{proof}
    Observe if $\tau \colon \{i_1,\cdots,i_t\} \to [k]$ is a map, then $$ \E\left[\prod_{l=1}^t X_{e,i_l, \tau(i_l)}\right] = \begin{cases}
    0 & \text{ if } \tau \text{ is not injective; } \\
    \frac{(k-t)!}{k! } & \text{ if } \tau \text{ is injective }
\end{cases}$$

Hence 
\begin{align*}
    & \E\left[\prod_{l=1}^t Y_{e,i_l, \pi(i_l)}\right] \\
    &= \E\left[\prod_{l=1}^t (X_{e,i_l, \pi(i_l)} - X_{e,i_l,1}) \right]\\ &= \E\left[ \prod_{l=1}^t X_{e,i_l, \pi(i_l)}\right] - \sum_{z=1}^t \E\left[\prod_{\substack{1\le l\le t \\ l\ne z}} X_{e,i_l,\pi(i_l)} \cdot X_{e,i_z,1}\right]  \\
    &= (1-t)\frac{(k-t)!}{k!}
\end{align*}

 
\end{proof}


For this choice of $(n_e)_{e\in E}$, choose an edge $e_0$ such that $n_{e_0}>0$. 






 




Case 1: The monomials have exactly one term of the form $Y_{e_0,*,*} $ , i.e. $n_{e_0}=1$. In this case, since the $\sigma_e$'s are independent random permutations, the expected value of every monomial factor through a term $\E[Y_{e_0,*,*} ]$, which is zero, so the contribution of this monomial to the expected value is 0.

Case 2: The monomials have $\ge 2$ terms of the form $Y_{e_0,*,*} $, i.e. $n_{e_0}\ge2$. 

Fix $i_1<\cdots<i_{n_{e_0}}\in \{2,\cdots,n\}$. Among the monomials associated to our fixed $(n_e)_{e\in E}$, we focus on the monomials that contain a product $\prod_{l=1}^{n_{e_0}} Y_{e_0,i_l,j_l}$ for some distinct integers $j_1,\cdots,j_{n_{e_0}} \in \{2,\cdots,n\}$. We will show the expected value of the signed sum of these monomials is zero. 

Again, by the independence of $\sigma_e$'s, we have $$ \E\left[ \prod_{e\in E} \prod_{l=1}^{n_e} Y_{e,i_l,j_l}\right] = \prod_{e\in E} \E\left[ \prod_{l=1}^{n_e} Y_{e,i_l,j_l}\right] = \E\left[ \prod_{l=1}^{n_{e_0}} Y_{e_0,i_l,j_l}\right] \cdot \prod_{e\in E\setminus \{e_0\}}\E\left[ \prod_{l=1}^{n_e} Y_{e,i_l,j_l}\right]$$

By \Cref{prp:expect}, 

$$\E\left[Y_{e_0,i_1,j_1}Y_{e_0,i_2,j_2}\prod_{l=3}^{n_{e_0}}Y_{e_0,i_l,j_l}\right] = \E\left[ Y_{e_0,i_1,j_2}Y_{e_0,i_2,j_1}\prod_{l=3}^{n_{e_0}}Y_{e_0,i_l,j_l} \right] $$ 

Thus, \begin{align*} 
 &\E\left[ Y_{e_0,i_1,j_1} Y_{e_0,i_2,j_2} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l}\right] \cdot \prod_{e\in E\setminus \{e_0\}}\E\left[ \prod_{l=1}^{n_e} Y_{e,i_l,j_l}\right] \\= &\E\left[ Y_{e_0,i_1,j_2} Y_{e_0,i_2,j_1} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l}\right] \cdot \prod_{e\in E\setminus \{e_0\}}\E\left[ \prod_{l=1}^{n_e} Y_{e,i_l,j_l}\right]
\end{align*}
  The term $ \prod_{e\in E} \prod_{l=1}^{n_e} Y_{e,i_l,j_l}$ appears in the signed sum from some permutation $\rho \in S_{n(k-1)}$. This necessarily means that $\rho(i_l)=j_l$ for all $e\in E, l=1,\cdots,n_{e}$, but $\rho$ is not necessarily unique. In the computation of the signed sum, We need to account this term for every such $\rho$.  
  % We now fix $\rho$. Observe that the term $Y_{e_0,i_1,j_2} Y_{e_0,i_2,j_1} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l} \prod_{e\in E\setminus \{e_0\}} \prod_{l=1}^{n_e} Y_{e,i_l,j_l} $ comes from the permutation $(i_1,i_2)\circ\rho$. Since the terms $Y_{e_0,i_1,j_1} Y_{e_0,i_2,j_2} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l} \prod_{e\in E\setminus \{e_0\}} \prod_{l=1}^{n_e} Y_{e,i_l,j_l} $  and $Y_{e_0,i_2,j_1} Y_{e_0,i_1,j_2} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l} \prod_{e\in E\setminus \{e_0\}} \prod_{l=1}^{n_e} Y_{e,i_l,j_l} $are in our sum, pair $$\left(\rho,Y_{e_0,i_1,j_1} Y_{e_0,i_2,j_2} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l} \prod_{e\in E\setminus \{e_0\}} \prod_{l=1}^{n_e} Y_{e,i_l,j_l} \right) $$ with $$ \left((i_1,i_2)\circ\rho,Y_{e_0,i_1,j_1} Y_{e_0,i_2,j_2} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l} \prod_{e\in E\setminus \{e_0\}} \prod_{l=1}^{n_e} Y_{e,i_l,j_l} \right).$$ This pairing is well-defined, and since the permutations in each pair have opposite signs, the signed sum of expected value of each pair is $0$. The conclusion follows.
  Now consider any particular choice of $\rho$. Observe that the term \[ Y_{e_0,i_1,j_2} Y_{e_0,i_2,j_1} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l} \prod_{e\in E\setminus \{e_0\}} \prod_{l=1}^{n_e} Y_{e,i_l,j_l} \] comes from the permutation $(i_1,i_2)\circ\rho$. Since the terms \[ Y_{e_0,i_1,j_1} Y_{e_0,i_2,j_2} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l} \prod_{e\in E\setminus \{e_0\}} \prod_{l=1}^{n_e} Y_{e,i_l,j_l} \; \text{ and } \; Y_{e_0,i_2,j_1} Y_{e_0,i_1,j_2} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l} \prod_{e\in E\setminus \{e_0\}} \prod_{l=1}^{n_e} Y_{e,i_l,j_l} \] are in our sum, we define a map $f$ that sends $$\left(\rho,Y_{e_0,i_1,j_1} Y_{e_0,i_2,j_2} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l} \prod_{e\in E\setminus \{e_0\}} \prod_{l=1}^{n_e} Y_{e,i_l,j_l} \right) $$ to $$ \left((i_1,i_2)\circ\rho,Y_{e_0,i_1,j_1} Y_{e_0,i_2,j_2} \prod_{l=3}^{n_{e_0}} Y_{e_0,i_l,j_l} \prod_{e\in E\setminus \{e_0\}} \prod_{l=1}^{n_e} Y_{e,i_l,j_l} \right).$$ Since $f$ is an involution, it defines a pairing. And since the permutations in each pair have opposite signs, the signed sum of expected value of each pair is $0$. The conclusion follows.

\begin{eg}

In example \ref{eg:section4}, we arrived at 
    $$\mathcal{L} = \begin{bmatrix}
    a+b - aY_{a,2,2} - bY_{b,2,2}   & - aY_{a,2,3} - bY_{b,2,3}   \\
    - aY_{a,3,2} - bY_{b,3,2}   & a+b - aY_{a,3,3} - bY_{b,3,3} 
\end{bmatrix}$$

The monomial $(-aY_{a,*,*})(-bY_{b,*,*})$ is associated to the sequence $n_a=n_b=1$. The monomial $(-aY_{a,*,*})(-aY_{a,*,*})$ is associated to the sequence $n_a=2, n_b=0$. The monomial $ (-aY_{a,*,*})b$ is associated to the sequence $n_a=1, n_b=0$. 

The sequence  $n_a=n_b=1$ is associated with four monomials: $$(-aY_{a,2,2})(-bY_{b,3,3}),  (-aY_{a,2,3})(-bY_{b,3,2}), (-aY_{a,3,2})(-bY_{b,2,3}), (-aY_{a,3,3})(-bY_{b,2,2})$$ The contribution of each monomial to the expected value is $0$ since $\E[Y_{a,i,j}]=0$.

The sequence  $n_a=2,n_b=0$ is associated with monomials \[ (-aY_{a,2,2})(-aY_{a,3,3}), (-aY_{a,2,3})(-aY_{a,3,2}). \] We pair the permutation $(id, Y_{a,2,2}Y_{a,3,3})$ with $((12),Y_{a,3,2}Y_{a,2,3})$. The signed sum of these is $0$. This corresponds to expanding 

$$ \E[ (-aY_{a,2,2})(-aY_{a,3,3}) - (-aY_{a,2,3})(-aY_{a,3,2})] = 0$$

as part of the computation of the expected value of the determinant of the matrix.
\end{eg}


\acknowledgements{We are grateful to Sylvester W. Zhang for introducing the problem and providing valuable guidance on the research. We thank Tao Gui for helpful conversations. We thank PACE 2024 for providing an unforgettable opportunity for us to conduct mathematical researches. This program is partially supported by NSFC grant 12426507.}


\printbibliography

\end{document}