%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{tikz}
\usepackage{tikzit}
\input{style.tikzstyles}
\usetikzlibrary{patterns}
\newtheorem{thm}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{conj}{Conjecture}
\newtheorem{cor}[thm]{Corollary}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{ex}{Example}
\theoremstyle{definition}
\newtheorem{defn}{Definition}

\usepackage{lipsum}
\usepackage{tikz}
\usepackage{enumitem}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calC}{\mathcal{C}}
\DeclareMathOperator{\wt}{wt}


%% define your title in the usual way
\title{Rooted Clusters for Graph LP Algebras}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[E.~Banaian, S.~Chepuri, E.~Kelly, and S.~W.~Zhang]{Esther~Banaian\thanks{\href{mailto:banai003@umn.edu}{banai003@umn.edu}}\addressmark{1},
Sunita Chepuri\thanks{\href{mailto:chepu003@umn.edu}{chepu003@umn.edu}. Partially supported by NSF Grant No. DMS-1439786.}\addressmark{2},
Elizabeth Kelley\thanks{\href{mailto:kelleye@illinois.edu}{kelleye@illinois.edu}. Partially supported by NSF Grant No. DMS-1937241.}\addressmark{3},
\and
Sylvester~W.~Zhang\thanks{\href{mailto:swzhang@umn.edu}{swzhang@umn.edu}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of Minnesota, Minneapolis, MN, USA \\ \addressmark{2}Department of Mathematics, University of Michigan, Ann Arbor, MI, USA \\
\addressmark{3}Department of Mathematics, University of Illinois Urbana-Champaign, Champaign, IL, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}
%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{LP algebras, introduced by Lam and Pylyavskyy, are a generalization of cluster algebras. These algebras are known to have the Laurent phenomenon, but positivity remains conjectural. Graph LP algebras are finite LP algebras encoded by a graph. For the graph LP algebra defined by a tree, we define a family of clusters called \emph{rooted clusters}. We prove positivity for these clusters by giving explicit formulas for each cluster variable. We also give a combinatorial interpretation for these expansions using a generalization of $T$-paths.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet

\keywords{Cluster Algebras, Laurent Phenomenon Algebras, Positivity}

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

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want

\usepackage[backend=bibtex]{biblatex}
\addbibresource{main.bib}

%% note the \printbibliography command at the end of the file which goes with these biblatex commands


\begin{document}

\maketitle

\section{Introduction}
Cluster algebras were introduced by Fomin and Zelevinsky~\cite{FZ-02} as a tool for studying total positivity and dual canonical basis of algebraic groups, and have since been linked to quiver representations, integrable systems, Poisson geometry, Teichm\"uller theory, mathematical physics, and other topics.
They are commutative rings with a family of distinguished generators called \emph{cluster variables}.  The cluster variables occur in overlapping subsets of fixed size called \emph{clusters}.  Given a cluster $\calC$, we can obtain a unique distinct cluster $\calC'$ by a process called \emph{mutation} where one cluster variable in $\calC$ is replaced with a different cluster variable.  The two cluster variables involved in this process are related by a \emph{binomial exchange relation}; that is, their product can be expressed as a binomial in terms of the other variables in $\calC$ (or, equivalently, in $\calC'$).

Cluster algebras have several important features, including the following.
\begin{enumerate}[label={(\arabic*)}]
    \item (\emph{Laurent phenomenon}) Given a fixed choice of cluster $\calC=(x_1,\dotsc,x_n)$, every cluster variable can be written as a Laurent polynomial in $x_1,\dotsc,x_n$. \label{laurent}
    \item (\emph{Positivity}) The Laurent polynomial in \ref{laurent} has positive coefficients.
\end{enumerate}

Lam and Pylyavskyy introduced Laurent phenomenon (LP) algebras as a generalization of cluster algebras~\cite{LP-12}. In an LP algebra, the restriction that exchange relations be binomial is relaxed to allow arbitrary irreducible polynomials.
Lam and Pylyavskyy proved that the Laurent phenomenon holds for LP algebras and conjectured that positivity holds as well.

Graph LP algebras are a particularly nice class of LP algebras having exchange relations that can be encoded in a graph.  Lam and Pylyavskyy explored graph LP algebras in depth in~\cite{LP-16} and gave simple descriptions of all of the clusters along with several formulas for computing the cluster variables. However, positivity for graph LP algebras remains conjectural. In this paper, we describe progress towards that conjecture.

We begin by introducing \emph{rooted clusters} for graph LP algebras. Our first main result, which we prove by giving explicit formulas for every cluster variable in terms of each rooted cluster, is positivity for such clusters.

\begin{thm}\label{thm:main1}
If $\Gamma$ is a tree and $\calC$ is a rooted cluster for $\Gamma$, then every cluster variable in the graph LP algebra associated to $\Gamma$ can be expressed as a Laurent polynomial with positive coefficients in the elements of $\calC$.
\end{thm}

We then introduce a generalization of Schiffler's $T$-paths for type $A$ cluster algebras~\cite{S-08} for our setting.  

\begin{thm}\label{thm:main2}
Let $\Gamma$ be a tree and $\calC$ be a rooted cluster for $\Gamma$.
If $S$ is a connected subset of vertices of $\Gamma$, then the cluster variable $Y_S$ has the combinatorial expansion formula $$Y_S=\sum_{\substack{\text{complete hyper}\\
T\text{-paths }\alpha\text{ for }S}}\wt(\alpha).$$
\end{thm}

We will begin in \Cref{sec:LP} by giving more background graph on LP algebras and introducing rooted clusters.  \Cref{sec:Formulas} gives formulas for the cluster variables in terms of a rooted cluster $\calC$ and sketches the proof of \Cref{thm:main1}.  We begin \Cref{sec:HyperTPaths} with background on $T$-paths for type $A$ cluster algebras and then define hyper $T$-paths.  This section culminates with a summary of the proof of \Cref{thm:main2}.  We conclude with a few thoughts about future work.


\section{Preliminaries}\label{sec:LP}

Laurent phenomenon (LP) algebras were defined by Lam and Pylyavskyy in~\cite{LP-12}.  A seed for an LP algebra consists of $n$ \emph{cluster variables} each with an associated \emph{exchange polynomial}.  We can \emph{mutate} at any cluster variable to obtain a new seed.  An LP algebra is a ring generated by all the cluster variables we can obtain from some initial seed by mutation.  This paper will focus on a subset of LP algebras called \emph{graph LP algebras}. As these LP algebras can be defined in an equivalent and simpler way (see \Cref{thm:graph-LP-defn}), we will not include a full definition of LP algebras here and instead direct interested readers to~\cite{LP-12}.

For every undirected graph $\Gamma$, we obtain a graph LP algebra $\mathcal{A}_\Gamma$.  The initial seed for $\mathcal{A}_\Gamma$ is encoded by the edges of the graph.

\begin{defn}\label{defn:graph-LP}
Let $\Gamma$ be an undirected graph on $[n]:=\{1,\cdots,n\}$ and $R=\Z[A_1,\dotsc,A_n]$. Then the \emph{graph LP algebra} $\mathcal{A}_\Gamma$ is the LP algebra generated by initial seed 
$$ \left\{\left(X_i,A_i+\sum_{i\text{ adjacent to }j}X_j\right)\right\}_{1\leq i\leq n}$$
\end{defn}

Lam and Pylyavskyy prove that these LP algebras have a particularly nice structure using nested collections.

\begin{defn}\label{defn:nested-coll}
Let $\Gamma$ be an undirected graph on $[n]$.  A family of subsets of $[n]$, $\calS=\{S_1,\dotsc,S_k\}$, is a \emph{nested collection} if
\begin{itemize}
    \item for any $i,j\leq k$, either $S_i\subseteq S_j$, $S_j\subseteq S_i$, or $S_i\cap S_j=\emptyset$, and
    \item if $S_{i_1},\dots S_{i_\ell}$ are pairwise disjoint, then $S_{i_1},\dots S_{i_\ell}$ are exactly the connected components of $\bigcup_{j=1}^\ell S_{i_j}$.
\end{itemize}
We say $\calS$ is a \emph{maximal nested collection on $S$} if $\bigcup_{i=1}^k S_i=S$ and there is no $S'\subseteq S$ such that $\{S_1,\dotsc,S_k,S'\}$ is a nested collection.
\end{defn}

If $\Gamma$ is a graph on $[n]$ and $\calS$ is a maximal nested collection on $S=[n]$, we will generally say that $\calS$ is a maximal nested collection without specifying $S$.

\begin{ex}\label{ex:nested-coll}
Let $\Gamma$ be the following graph:
\begin{center}
\begin{tikzpicture}
\node at (-1,0.3) {1};
\node at (0,0.3) {2};
\node at (1,0.3) {3};
\node at (2,0.8) {4};
\node at (2,-0.8) {5};
\draw [line width=0.25mm, fill=black] (-1,0) circle (0.75mm);
\draw [line width=0.25mm, fill=black] (0,0) circle (0.75mm);
\draw [line width=0.25mm, fill=black] (1,0) circle (0.75mm);
\draw [line width=0.25mm, fill=black] (2,0.5) circle (0.75mm);
\draw [line width=0.25mm, fill=black] (2,-0.5) circle (0.75mm);
\draw (-1,0) -- (0,0)
(0,0) -- (1,0)
(1,0) -- (2,0.5)
(1,0) -- (2,-0.5);
\end{tikzpicture}
\end{center}

Then $\calS=\{\{1\},\{3\},\{1,2,3,4\}\}$ is a nested collection on $S=\{1,2,3,4\}$.  However, it is not maximal because adding the set $S'=\{1,2,3\}$ still yields a nested collection.

As a nonexample, consider $\calS=\{\{1\},\{1,2\},\{3\},\{1,2,3,4\}\}$.  We can see that this is not a nested collection by looking at the disjoint sets $\{1,2\}$ and $\{3\}$. The union of these sets is $\{1,2,3\}$, which has only one connected component.  
%In order for this collection to be nested, $\{1,2,3\}$ would have to have $\{1,2\}$ and $\{3\}$ as connected components.
\end{ex}

\begin{thm}[{\cite[Theorem 1.1]{LP-16}}]\label{thm:graph-LP-defn}
Let $\Gamma$ be an undirected graph on $[n]$.  Define the matrix $\mathfrak{N}=(\mathfrak{n}_{ij})$ by $$\mathfrak{n}_{ij}=\begin{cases}
{\displaystyle \frac{ A_i+\sum_{i\textup{ adjacent to }j}X_j}{X_i}} & i=j, \\
-1 & i\textup{ adjacent to }j, \\
0 & \textup{otherwise}.
\end{cases}$$  Then the graph LP algebra $\mathcal{A}_\Gamma$ has cluster variables $\{X_1,\dotsc,X_n\}\cup\{Y_S\ |\ S\subset[n]\text{ is connected}\}$ where $Y_S$ is the determinant of the submatrix of $\mathfrak{N}$ obtained by taking only rows and columns indexed by $S$.  The clusters for $\mathcal{A}$ are of the form $\{X_{i_1},\dotsc,X_{i_k}\}\cup\{Y_S\ |\ S\in \calS\}$ where $\calS$ is a maximal nested collection on $[n]\setminus\{i_1,\dotsc,i_k\}$.
\end{thm}


In a slight abuse of notation, we will generally write $Y_{s_1\cdots s_r}$ as shorthand for $Y_{\{s_1,\dotsc,s_r\}}$.

\begin{ex}\label{ex:graph-LP}
Let $\Gamma$ be the graph from \Cref{ex:nested-coll}.  One example of a valid cluster for $\mathcal{A}_\Gamma$ is $\{X_2, Y_1, Y_5, Y_{35}, Y_{345}\}$.  This is because $\{\{1\}, \{5\}, \{3,5\}, \{3,4,5\}\}$ is a maximal nested collection on $\{1,3,4,5\}$.  In this case, the $\mathfrak{N}$ matrix is:
$$
\mathfrak{N}=
\begin{bmatrix}
\frac{A_1+X_2}{X_1} & -1 & 0 & 0 & 0 \\
-1 & \frac{A_2+X_1+X_3}{X_2} & -1 & 0 & 0 \\
0 & -1 & \frac{A_3+X_2+X_4+X_5}{X_3} & -1 & -1 \\
0 & 0 & -1 & \frac{A_4+X_3}{X_4} & 0 \\
0 & 0 & -1 & 0 & \frac{A_5+X_3}{X_5} \\
\end{bmatrix}
$$
We can use this to rewrite the $Y$-variables in our cluster.  For example,
$$
Y_{35}=\left|
\begin{matrix}
\frac{A_3+X_2+X_4+X_5}{X_3} & -1 \\
-1 & \frac{A_5+X_3}{X_5} \\
\end{matrix}
\right|
=\frac{A_3A_5+A_5X_2+A_5X_4+A_5X_5+A_3X_3+X_2X_3+X_3X_4}{X_3X_5}.
$$
\end{ex}

Lam and Pylyavskyy also completely describe the exchange relations for $\mathcal{A}_\Gamma$ (see~\cite[Lemmas~4.7 and~4.11]{LP-16}).

We focus on the case when $\Gamma$ is a tree.  In this setting, we can define a special type of cluster we call a \emph{rooted cluster} that has desirable properties.  There is one rooted cluster $\calC_v$ for each vertex $v$ of $\Gamma$.  In order to define this cluster, we think of $\Gamma$ as being rooted at $v$.  We then think of $\Gamma$ as a poset with the root $v$ being the maximal element and cover relations given by edges of $\Gamma$.  This leads us to establish the following notation:
\begin{itemize}
    \item Notice that if $i\neq v$, then $i$ is covered by exactly one vertex.  We call this vertex $i^+$.
    \item The set of elements covered by $i$ is denoted $\Gamma_{\lessdot i}^v$.  Similarly we have the sets $\Gamma_{\gtrdot i}^v$, $\Gamma_{< i}^v$, $\Gamma_{> i}^v$, $\Gamma_{\leq i}^v$, and $\Gamma_{\geq i}^v$ (note that $\Gamma_{\gtrdot i}^v=\{i^+\}$ if $i\neq v$).
\end{itemize}

\begin{defn}\label{defn:rooted-cluster}
Let $\Gamma$ be a tree on $[n]$.  Make $\Gamma$ into a rooted tree by choosing a vertex $v$ to be the root.  Then for each vertex $x$ in $\Gamma$, let $I_x=\Gamma_{\leq x}^v$.  The \emph{rooted cluster} $\calC_v$ is $\{I_x\}_{x\in[n]}$.
\end{defn}

\begin{ex}\label{ex:rooted-cluster}
Consider the tree in \Cref{fig:exampletree}. The cluster $\calC_3$ consists of $I_1 = \{1\}, I_2 = \{1,2,5\}, I_3 = \{1,2,3,4,5\}, I_4 = \{4\}$, and $I_5 = \{5\}$. One can check that these sets form a nested collection, and that it is not possible to add another set compatible with all others. If we root at $2$ instead, then $\mathcal{C}_2$ consists of the sets $I_1 = \{1\}, I_2 = \{1,2,3,4,5\}, I_3 = \{3,4\}, I_4 = \{4\}$, and $I_5 = \{5\}$.
\end{ex}

\begin{figure}
\begin{center}
\begin{tikzpicture}
\node at (-0.3,0) {1};
\node at (0.8,1) {2};
\node at (0.3,2) {3};
\node at (-0.8,1) {4};
\node at (1.3,0) {5};
\draw [line width=0.25mm, fill=black] (0,2) circle (0.75mm);
\draw [line width=0.25mm, fill=black] (-0.5,1) circle (0.75mm);
\draw [line width=0.25mm, fill=black] (0.5,1) circle (0.75mm);
\draw [line width=0.25mm, fill=black] (0,0) circle (0.75mm);
\draw [line width=0.25mm, fill=black] (1,0) circle (0.75mm);
\draw (0,2) -- (0.5,1)
(0,2) -- (-0.5,1)
(0.5,1) -- (0,0)
(0.5,1) -- (1,0);
\end{tikzpicture}
\end{center}
\caption{We can picture the cluster rooted at vertex 3 by taking subsets which are closed going down. For example, $I_2 = \{1,2,5\}$ and $I_5 = \{5\}$.}\label{fig:exampletree}
\end{figure}

\section{Formulas}\label{sec:Formulas}

Although \Cref{thm:graph-LP-defn} and the exchange relations for graph LP algebras give formulas for all cluster variables, these formulas are not guaranteed to be in terms of the variables of any particular cluster.  In this section, we provide formulas for each of the $X_i$ and $Y_S$ cluster variables in terms of a rooted cluster $\calC_v$. Positivity for this case follows as an immediate consequence.

One useful observation, which simplifies the presentation of our formulas, is that:

\begin{lemma}\label{lem:in-cluster}
Let $\Gamma$ be a tree rooted at $v$ and $i$ a vertex of $\Gamma$.  Then $$Y_{\Gamma_{< i}^v}=\prod_{u\in\Gamma_{\lessdot i}^v}Y_{I_u}$$
and for $u\in\Gamma_{< i}^v$ we have,
$$Y_{\Gamma_{< i}^v\setminus\Gamma_{\geq u}^v}=\left(\prod_{w\in\Gamma_{\lessdot i}^v\setminus\Gamma_{\geq u}^v}Y_{I_w}\right)\left(\prod_{w\in\Gamma_{\lessdot u}^v}Y_{I_w}\right).$$ 
\end{lemma}

Using \Cref{thm:graph-LP-defn} and~\cite[Lemmas 4.7 and 4.11]{LP-16}, we obtain an expansion formula for $Y_S$ when $|S| = 1$. It follows from \Cref{lem:in-cluster} that this formula only includes $Y$-variables from $\mathcal{C}_v$.

\begin{prop}\label{prop:Y-single-formula}
Let $\Gamma$ be a tree rooted at $v$.  For every vertex $i$ of $\Gamma$,
$$Y_{\{i\}}=\frac{Y_{I_i}+\sum_{u\in\Gamma_{\lessdot i}^v}Y_{\Gamma_{< i}^v\setminus\{u\}}}{Y_{\Gamma_{< i}^v}}.$$
\end{prop}

\begin{ex}
\label{ex:Y-single-computation}
Consider the tree shown in \Cref{fig:exampletree} and the rooted cluster $\mathcal{C}_3$. Using the formula from Proposition 1, we compute
\[ Y_{\{ 2 \}} = \frac{Y_{I_2} + \sum_{u \in \Gamma^{3}_{\lessdot 2}} Y_{\Gamma^3_{<2} \backslash \{ u \}}}{Y_{\Gamma^3_{<2}}} = \frac{Y_{I_2} + Y_{\Gamma^{3}_{<2}\backslash \{ 1\}} + Y_{\Gamma^{3}_{<2}\backslash \{ 5\}}}{Y_{\Gamma^3_{<2}}} = \frac{Y_{\{ 1,2,5 \}} + Y_5 + Y_1}{Y_1Y_5}. \]
Later, we will see that this is consistent with the expansion computed via our hyper $T$-path construction.
\end{ex}

We then establish the following technical lemmas, which are used to obtain expansion formulas for $Y_S$ for arbitrary $S$.

\begin{lemma}\label{lem:Y-sum}
Let $\Gamma$ be a tree, $S$ be a connected subset of vertices, and $T=\{(a,b)\in S\times S\ |\ a=b^+\}$.  Then $$Y_S=\sum_{n=0}^{\left\lfloor\frac{|S|}{2}\right\rfloor}(-1)^n\sum_{A\in A(n)}\left(\prod_{x\in (S\setminus A')}Y_{\{x\}}\right)$$
where $A(n)=\{A\subseteq 2^T\ |\ |A|=n\text{ and }\{a,b\}\cap\{c,d\}=\emptyset \text{ for all } (a,b),(c,d) \in A \text{ satisfying}$ $(a,b)\neq(c,d)\}$ and for any $A\in A(n)$, $A'=\{s\ |\ s\text{ is part of a pair in }A\}$.
\end{lemma}

\begin{lemma}\label{lem:Y-term-containment}
Let $Y_S^{(n)}=\sum_{A\in A
(n)}\left(\prod_{x\in (S\setminus A')}Y_{\{x\}}\right)$.  If $t$ is a monomial that appears as a term in $Y_S^{(m+1)}$, then $t$ also appears in $Y_S^{(m)}$.
\end{lemma}

As a consequence of \Cref{lem:Y-term-containment}, the set of monomials that appear in the expansion of the sum in \Cref{lem:Y-sum} are exactly those that appear in the expansion of $\prod_{x \in S} Y_{\{ x \}}$. By counting the number of times each monomial appears in the expansion of the sum in \Cref{lem:Y-sum}, we obtain an expansion formula for all $Y_S$. To obtain an expansion formula for all $X_i$, we first apply \cite[Lemmas 4.7 and 4.11]{LP-16} to $S = \Gamma^v_{< i}$ to obtain a formula for $X_v$ and then induct on the distance from $i$ to the root vertex $v$.

\begin{thm}\label{thm:formulas}
Let $\Gamma$ be a tree rooted at $v$. For all vertices $i$ of $\Gamma$ and vertex subsets $S$, we have
\begin{align}
X_i &= \frac{\sum_{u\in\Gamma_{\geq i}^v}\left(\prod_{w\in\Gamma_{\geq i}^v\setminus\Gamma_{\geq u}^v} Y_{\Gamma_{< w}^v}\right)\left(\prod_{w\in\Gamma_{< u}^v} Y_{I_w}\right)\left(\sum_{w\in I_u}Y_{\Gamma_{< u}^v\setminus\Gamma_{\geq w}^v}A_w\right)}{\prod_{u\in\Gamma_{\geq i}^v}Y_{I_u}}, \label{eqn:X_formula}\\
Y_S &= \sum_{\substack{O\subseteq S\text{ containing all}\\\text{minimal elements of }\Gamma\text{ in }S}}\ \,\sum_{\substack{u \colon S\setminus O\to V(\Gamma)\\\ u(x)\in\Gamma_{\lessdot x}^v\setminus O}}\frac{\left(\prod_{x\in O}Y_{I_x} \right)\left(\prod_{x\in S\setminus O}Y_{\Gamma_{< x}^v\setminus\{u(x)\}} \right)}{\prod_{x\in S}Y_{\Gamma_{< x}^v}}. \label{eqn:Y_formula}
\end{align}
\end{thm}

\Cref{thm:main1} follows as a corollary of these expansion formulas, using \Cref{lem:in-cluster}.

\section{Hyper $T$-paths}\label{sec:HyperTPaths}

We reprove \cref{thm:main1} about positivity of the $Y$-variables via a combinatorial interpretation of the expansions of $Y_S$ in terms of a rooted cluster.  Our constructions are a generalization of \emph{$T$-paths}, which were originally introduced by Schiffler \cite{S-08} as a tool for finding cluster expansion formulas in type $A$ cluster algebras.

\subsection{$T$-paths for Type $A$ Cluster Algebras}\label{sec:T-path-bg}

Type $A$ cluster algebras are modeled by triangulations of an $(n+3)$-gon, with each initial seed corresponding to a unique initial triangulation. Consider an $(n+3)$-gon with vertices labeled $1, \dots, n+3$ and a fixed triangulation $T = \{ T_1, \dots, T_n, T_{n+1}, \dots, T_{2n+3} \}$ where $T_1, \dots, T_n$ are interior diagonals and $T_{n+1},\dotsc, T_{2n+3}$ are boundary edges. Let $i$ and $j$ be non-adjacent boundary vertices and let $M_{i,j}$ denote the interior diagonal connecting $i$ and $j$. Fix an orientation on $M_{i,j}$ and let $i = p_0, p_1, \dots, p_{d}, p_{d+1} = j$ be the ordered list of intersection points of $M_{i,j}$ and arcs of $T$. Then let $i_1, \dots, i_{d}$ be a list of indices such that intersection point $p_k$ lies on the arc $T_{i_k} \in T$. 
%Note that it is possible to have $i_j = i_k$ for $j \neq k$.
For $k \in [d]$, let $M_k$ denote the segment of the diagonal $M_{i,j}$ between the intersection points $p_k$ and $p_{k+1}$.

In \cite{MS-09}, Musiker and Schiffler define a \emph{complete $T$-path from $i$ to $j$} as a sequence $\alpha = ( t_1,\dotsc,t_{\ell(\alpha)})$ such that
\begin {itemize}
    \item[(T1)] $i = a_0,a_1, \dots,a_{\ell(\alpha)} = j$ are (not necessarily distinct) vertices of the $(n+3)$-gon,
    \item[(T2)] $t_k \in \alpha$ is an arc in the triangulation $T$ that connects vertices $a_{k-1}$ and $a_k$, and
    \item[(T3)] the even arcs are precisely the arcs crossed by $M_{i,j}$ in order, \textit{i.e.}~$t_{2k} = T_{i_k}$.
\end {itemize}

We denote the set of all complete $T$-paths from $i$ to $j$ as $\mathcal{T}_{ij}$. Given a complete $T$-path $\alpha$, the \emph{weight} of $\alpha$ is defined to be the Laurent monomial
\[ \wt(\alpha) := \left( \prod_{i \textrm{ odd}} \wt(t_{i}) \right)\left( \prod_{i \textrm{ even}} \wt(t_i) \right)^{-1} \]
where the weight of edge $t_i$ is given by $\wt(t_i) := x_{t_i}$. By summing over the set $\mathcal{T}_{ij}$, Schiffler \cite{S-08} then obtains an expansion formula for the cluster variable corresponding to $M_{i,j}$ in terms of the cluster seed corresponding to the triangulation $T$:
\[ x_{M_{i,j}} := \sum_{\alpha \in \mathcal{T}_{ij}} \wt(\alpha) \]
Although it is not immediately obvious, this cluster expansion formula is independent of the choice of orientation on $M_{i,j}$.  

\subsection{Construction and Examples}\label{sec:gen-T-paths}

In this section, we generalize the notion of $T$-paths to define \emph{hyper $T$-paths}. We first construct an auxiliary graph, $\Gamma_{\mathcal{C}}$. 

Let $\Gamma$ be a tree and $\mathcal{C}$ be a rooted cluster for $\Gamma$.  For each vertex $x$ of degree 1 in $\Gamma_{\mathcal{C}}$ we add an additional vertex $x'$ which is adjacent only to $x$.  Call this extended graph $\Gamma'$.  We will continue to think of $\Gamma'$ as a poset where $x'<x$ if $x$ is not the root and $x'>x$ if $x$ is the root.  For every $S\in\mathcal{C}$, let $S'$ be the set of vertices in $\Gamma'$ that are adjacent to a vertex in $S$ but are themselves not in $S$.  Add a hyperedge labelled $S$ which connects all the vertices of $S'$. As a convenient abuse of notation, we often refer to this hyperedge simply as $S$.  We refer to this new hypergraph as $\Gamma_{\mathcal{C}}$.  See \Cref{fig:example_hypergraph} for an example.



\begin{figure}[h]
\centering
\tikzfig{hypergraph_new}
\caption{The hypergraph associated to the tree from \Cref{fig:exampletree}. 
}
\label{fig:example_hypergraph}
\end{figure}


For $x$ a vertex in the rooted tree $\Gamma$, we will use $\mathcal{L}_x$ to denote to all minimal elements of $\Gamma'$ that are less than $x$.  Equivalently, $\mathcal{L}_x$ is the elements of $\Gamma'\setminus\Gamma$ that are less than $x$.

\begin{defn}
\label{def:hyperTpath}
Let $S$ be a connected subset of $\Gamma$.  A \emph{complete hyper $T$-path} for $S$ with respect to $\mathcal{C}$ is a set of nodes, labelled by vertices of $\Gamma_{\mathcal{C}}$, joined by connections labelled by hyperedges of $\Gamma_{\mathcal{C}}$ such that the diagram is connected and the following hold.
\begin{enumerate}
    \item If a connection is labelled by hyperedge $e$, it joins nodes labelled by all the endpoints of $e$ with multiplicity 1.
    \item There are a distinguished set of \emph{boundary nodes} labelled by elements of $S'$ with multiplicity 1.  Other nodes are called \emph{internal nodes}.
    \item Connections are specified to be \emph{even} or \emph{odd}.
    \item Boundary nodes are adjacent only to odd connections.
    \item Internal nodes labelled by elements of $S$ are adjacent to exactly one even and at least one odd connection.
    \item Internal nodes labelled by elements not in $S$ are adjacent to exactly one even and exactly one odd connection.
    \item If $x,y$ are below elements of $S$, any path in any complete hyper $T$-path from boundary node $x$ to boundary node $y$ uses even connections labelled, in order, by $I_x,I_{a_p},$ $I_{a_{p-1}},$ $\dots,$ $I_{a_1},I_{b_1},I_{b_2},\dotsc,I_{b_q},I_y$ where the shortest path from $x$ to $y$ in $\Gamma'$ is $x,a_p,$ $a_{p-1},$ $\dots,$ $a_1,x\vee y,b_1,b_2,\dotsc,b_q,y$ for $p,q \geq 0$.
    \item If $x$ is below an element of $S$ and $y$ above the maximal element of $S$, any path in any complete hyper $T$-path from the boundary node $x$ to the boundary node $y$ uses even connections labelled, in order, by  $I_x,I_{a_p},\ldots,I_{a_2}$, where the shortest path from $x$ to $y$ in $\Gamma'$ is $x,a_p,a_{p-1},\ldots,a_1,y$, $p \geq 1$. If $p = 1$, then a path from $x$ to $y$ uses the even connection $I_x$. 
    \item If $x,y$ are boundary nodes, where the shortest path from $x$ to $y$ in $\Gamma'$ is given by $x,a_p,\ldots,a_1,x\vee y, b_1, \ldots,b_q,y$ , then any path in any complete hyper $T$-path from $x$ to $y$ uses nodes labelled by elements of $\mathcal{L}_{x\vee y}$ and $a_p,$ $a_{p-1},$ $\dots,$ $a_1,x\vee y,b_1,b_2,\dotsc,b_q$, with any multiplicity. If one of the nodes, say $y$, is adjacent to the maximal element of $S$, then $x \vee y = y$ and $q = 0$. 
\end{enumerate}
\end{defn}

\begin{defn}
The \emph{weight} of a hyper $T$-path $\alpha$ is $$\wt(\alpha)=\left(\prod_{\text{odd connections }c} \wt(c)\right)\left(\prod_{\text{even connections }c} \wt(c)\right)^{-1}$$ where the weight of a connection labelled by a set $I_x$ is $Y_{I_x}$ and the weight of a connection labelled by an edge in $\Gamma'$ is 1.
\end{defn}

\begin{ex}\label{ex:hyperTPath}
Consider the graph $\Gamma$ in \Cref{fig:exampletree} with a cluster rooted at 3. Below we list the three hyper T-paths associated to the set $\{2\}$. %Unlabeled connections are edges in $\Gamma'$ and have weight 1.

\begin{tabular}{ccc}
\begin{tikzpicture}[scale = 0.6]
		\node (10) at (-7.25, 3.25) {$2$};
		\node (1) at (-5.5, 3.25) {$1'$};
		\node (2) at (-3.75, 2) {$2$};
		\node (4) at (-5.5, 0.75) {$5'$};
		\node (8) at (-4.25, 1) {$\color{red}I_5$};
		\node (11)  at (-7.25, 0.75) {$5$};
		\node (12) at (-6.3, 2.75) {$\color{red}I_1$};
		\node (13) at (-8, 2.75) {$\color{blue}I_1$};
		\node (22) at (-1.75, 2) {$3$};
		\node (0) at (-9,3.25){$1$};
		\draw [red, densely dashed] (2) to (4);
		\draw [blue] (0) to (10);
		\draw [red, densely dashed] (1) to (2);
		\draw [blue] (10) to (1);
		\draw [blue] (11) to (4);
		\draw [blue] (2) to (22);
\end{tikzpicture}
&
\begin{tikzpicture}[scale = 0.6]
		\node (0) at (-7.25, 3.25) {$1$};
		\node (1) at (-5.5, 3.25) {$1'$};
		\node (2) at (-3.75, 2) {$2$};
		\node (4) at (-5.5, 0.75) {$5'$};
		\node (8) at (-4.25, 3) {$\color{red}I_1$};
		\node (10) at (-7.25, 0.75) {$2$};
		\node (11)  at (-9, 0.75) {$5$};
		\node (12) at (-6.3, 1.25) {$\color{red}I_5$};
		\node (13) at (-8, 1.25) {$\color{blue}I_5$};
		\node (22) at (-1.75, 2) {$3$};
		\draw [blue] (2) to (4);
		\draw [blue] (0) to (1);
		\draw [red, densely dashed] (1) to (2);
		\draw [red, densely dashed] (10) to (4);
		\draw [blue] (11) to (10);
		\draw [blue] (2) to (22);
\end{tikzpicture}
&
\begin{tikzpicture}[scale = 0.6]
		\node (0) at (8,1) {$3$};
		\node (1) at (6,2){$1'$};
		\node (2) at (6,0) {$5'$};
		\node (3) at (4,1){$2$};
		\node (4) at (2,2){$1$};
		\node (5) at (2,0) {$5$};
		\node[above] at (5,1.5){$\color{red}{I_1}$};
		\node[below] at (5,0.5){$\color{red}{I_5}$};
		\node[above] at (7.2,1.3){$\color{blue}{I_2}$};
		\draw[blue] (0) to (7.2,1);
		\draw[blue] (7.2,1) to (1);
		\draw[blue] (7.2,1) to (2);
		\draw[red, densely dashed] (1) to (3);
		\draw[red, densely dashed] (2) to (3);
		\draw[blue] (3) to (4);
		\draw[blue] (3) to (5);
\end{tikzpicture}
\end{tabular}

From left to right, these $T$-paths have weight $\frac{1}{Y_{I_5}}, \frac{1}{Y_{I_1}}$ and $\frac{Y_{I_2}}{Y_{I_1}Y_{I_5}}$. This is consistent with the expansion of $Y_2$ computed by \Cref{prop:Y-single-formula}, shown in \Cref{ex:Y-single-computation}.

We also give one example of a $T$-path associated to the set $\{2,3\}$ from the same graph with the same rooted cluster. The $T$-path below has weight $\frac{1}{Y_{I_1}Y_{I_4}}$.

\begin{center}
\begin{tikzpicture}[scale = 0.6]
		\node [style=label] (0) at (-7.25, 3.25) {$1$};
		\node [style=label] (1) at (-5.5, 3.25) {$1'$};
		\node [style=label] (2) at (-3.75, 2) {$2$};
		\node [style=label] (3) at (1.75, 2) {$3$};
		\node [style=label] (4) at (-5.5, 0.75) {$5'$};
		\node [style=label] (5) at (3.75, 2) {$4'$};
		\node [style=label] (6) at (5.75, 2) {$4$};
		\node [style=label] (8) at (-4.25, 3) {$\color{red}I_1$};
		\node [style=label] (9) at (2.75, 1.5) {$\color{red}I_4$};
		\node [style=label] (10) at (-7.25, 0.75) {$2$};
		\node [style=label] (11) at (-9, 0.75) {$5$};
		\node [style=label] (12) at (-6.5, 1.25) {$\color{red}I_5$};
		\node [style=label] (13) at (-8, 1.25) {$\color{blue}I_5$};
		\node [style=label] (14) at (0, 3.25) {$5'$};
		\node [style=label] (15) at (0, 0.75) {$1'$};
		\node  (16) at (-0.5, 2) {};
		\node  (17) at (0.5, 2) {};
		\node [style=label] (19) at (-1.25, 1.25) {$\color{red}I_2$};
		\node [style=label] (20) at (1, 2.75) {$\color{blue}I_2$};
		\node [style=label] (22) at (-1.75, 2) {$3$};
		\draw [style=blue] (5) to (6);
		\draw [style=blue] (2) to (4);
		\draw [style=blue] (0) to (1);
		\draw [style=red, densely dashed] (3) to (5);
		\draw [style=red, densely dashed] (1) to (2);
		\draw [style=red, densely dashed] (10) to (4);
		\draw [style=blue] (11) to (10);
		\draw [style=red, densely dashed] (16.center) to (14);
		\draw [style=red, densely dashed] (16.center) to (15);
		\draw [style=blue] (14) to (17.center);
		\draw [style=blue] (17.center) to (3);
		\draw [style=blue] (17.center) to (15);
		\draw [style=red, densely dashed, densely dashed] (22) to (16.center);
		\draw [style=blue] (2) to (22);
\end{tikzpicture}
\end{center}
\end{ex}

\begin{remark}
The $T$-paths in \Cref{ex:hyperTPath} illustrate that these sometimes have adjacent odd and even connections with the same label. The contributions of these connections then cancels in the weight of the $T$-path. To avoid this, one could instead define \emph{reduced hyper $T$-paths}. Here, we find it simpler to work with complete hyper $T$-paths.
\end{remark}

Our main result in this section (\Cref{thm:main2}) is that the hyper $T$-paths provide a combinatorial interpretation of the expansion of a variable $Y_S$ with respect to a rooted cluster. Because the coefficients of this expansion formula count the number of hyper $T$-paths with a particular weight, they are manifestly positive integers. By \cref{eqn:X_formula}, this also implies that the coefficients of the $X$-variables are positive; thus, the hyper $T$-paths provide a second proof of \cref{thm:main1}.

The proof of \Cref{thm:main2} has similarities with the proof of \Cref{thm:formulas}. We first prove the theorem in the case of singleton sets; recall the description of the expansion of $Y_{\{i\}}$ in  \Cref{prop:Y-single-formula}. We then define valid \emph{pastings} of hyper $T$-paths and study which $T$-paths associated to $\{i\}$ and $\{j\}$ can be pasted, provided that $i$ and $j$ are adjacent in $\Gamma$. The pasting requirements mirrors the algebraic computations from the proof of \Cref{thm:main2}, leading us to our result. See \cite{banaian2021rooted} for complete proofs of both results.

\section{Future Directions}\label{sec:FutureDirections}
\subsection{From Rooted Clusters to Other Clusters}
We would like to extend our results to other clusters for trees. Our definition of rooted clusters is motivated by the algebraic formulas for the exchange relations~\cite[Lemmas 4.7 and 4.11]{LP-16}. For rooted clusters, the exchange relations give expansions in terms of the cluster variables in the initial seed. This is not, however, true for an arbitrary cluster.

Proving formulas algebraically for other types of  clusters will likely require an inductive argument, which seems to be easiest in star graphs because of their symmetry. 
\begin{conj}
Let $S_n$ denote the star graph on $n$ vertices whose central vertex is labeled by $1$. Let $\mathcal{C}$ be the cluster  $\{ \{3 \}, \{ 4 \}, \dots, \{ n \}, \{ 1, 3, 4, \dots n \} \}$. For any vertex subset $S$ such that $1 \in S$, we conjecture that
\begin{align*}
    Y_S = \begin{cases} 
        \frac{\prod\limits_{i \in S \backslash \{ 1, 2 \}} Y_i^2}{Y_{[n] \backslash \{ 1, 2 \}}} \left( \sum\limits_{i \not\in S} \prod\limits_{j \neq 1, 2, i} Y_j \right) + \frac{Y_{[n]}}{\prod\limits_{i \in [n] \backslash S} Y_i} + \frac{Y_{[n]}}{Y_{[n] \backslash \{ 2 \}}} \left( \sum\limits_{i \in [n] \backslash S} \frac{1}{Y_i} \right) & \textrm{if } 2 \not\in S \\ \\
        \frac{Y_{[n] \backslash \{ 2 \}}}{\prod\limits_{i \in [n] \backslash (S \cup \{ 2 \})} Y_i} + \left(\prod\limits_{i \in S \backslash \{ 1 \}} Y_i \right) \left( \sum\limits_{j \in [n] \backslash (S \cup \{ 2 \})} \frac{1}{Y_i} \right) & \textrm{if } 2 \in S
    \end{cases}
\end{align*}
If $1 \not\in S$, then $S$ either consists of a set of disconnected leaves or a single leaf. Because $\{ i \} \in \mathcal{C}$ for all $i \neq 2$, we then have 
\begin{align*}
    Y_s = \prod\limits_{i \in S} Y_i
\end{align*}
\end{conj}

We are also hopeful that we can extend our hyper $T$-path expansion formula to other types of clusters. For a type $A$ cluster algebra, $T$-paths can be used to find expansions for cluster variables in terms of any cluster.  Because the definitions of $T$-paths and hyper $T$-paths for path graphs are similar, this suggests that it might be possible to use hyper $T$-paths for other clusters when $\Gamma$ is an arbitrary tree.

Unfortunately, our current hyper $T$-path construction does not work for arbitrary clusters. One immediate problem is that Rules (7) and (8) would need to be rewritten to be more general.  That is, we would need to allow the even edges to be labelled by any set in the cluster that is incompatible with $S$. However, that change would be insufficient because we still would not have ``enough'' valid hyper $T$-paths.  
Further, the expansions of some cluster variables with respect to certain clusters contain monomials with squared terms in the denominator.  This is not possible with our current definition. Thus, it is clear that there is some other modifications are required for us to be able to extend our construction to other clusters.

\subsection{Snake Graphs}

In \cite{MSW}, Musiker, Schiffler and Williams provided an alternative combinatorial formula for type $A$ cluster algebras using perfect matchings on certain \emph{snake graphs}. For such cluster algebras, there exists a weight-preserving bijection between the set of (complete) $T$-paths associated to an arc and the set of perfect matching of its snake graph. Since our hyper $T$-path are generalizations of complete $T$-paths, we hope to extend this bijection to obtain a graph-theoretic formula analogous to \cite{MSW} for LP algebras from trees. 
We illustrate the rough idea in the following example.
\begin{figure}[h]
\centering
\tikzfig{Snake_Graph_new}
\quad\quad
\tikzfig{SG01new}
\caption{A generalized snake graph and one of its matchings.}
\label{fig:snake}
\end{figure}
\begin{ex}
On the left of \Cref{fig:snake}, we draw a snake graph associated to the set $\{2,3\}$ of the graph $\Gamma$ in \Cref{fig:example_hypergraph}. 
%
%
In its perfect matchings, the vertex 2 is allowed to have valence $2$. On the right of \Cref{fig:snake} is the perfect matching which has the same weight as the hyper $T$-path in \Cref{ex:hyperTPath}.
\end{ex}
Snake graphs may prove more tractable for non-rooted clusters; however, the full construction of a generalized snake graph is still in progress. We were able to complete the preceding example because all vertices in the underlying graph $\Gamma$ had degree three or less. When the vertices in $\Gamma$ have higher degree, it is unclear how to draw the snake graphs.


\acknowledgements{We would like to thank Pavlo Pylyavskyy for suggesting this problem, Trevor Karn for organizing the Minnesota Combinatorics Working Group, and Kayla Wright and Libby Farrell for generating initial computational data.}

\printbibliography

\end{document}
