text:
\begin{document}

\maketitle

\begin{abstract}

In 2011 Musiker, Schiffler and Williams obtained expansion formulae for cluster algebras from orientable surfaces \cite{musiker2011positivity}. For singly and doubly notched arcs these formulae required the notion of $\gamma$-symmetric perfect matchings and $\gamma$-compatible pairs of $\gamma$-symmetric perfect matchings, respectively. We simplify and unify these approaches by considering good matchings of \textit{loop} graphs.

\end{abstract}

\pagenumbering{arabic}

\tableofcontents

\section{Introduction}

Fomin and Zelevinsky's cluster algebras are a particular class of commutative algebras whose generators, \textit{cluster variables}, are obtained iteratively from an initial collection of (algebraically independent) variables. These cluster variables have some seemingly miraculous properties; even though they are defined recursively as rational functions, surprisingly, they are always Laurent polynomials in the initial variables \cite{fomin2002cluster}. In the context of cluster algebras from triangulated surfaces \cite{fomin2018cluster}, a setting in which cluster variables correspond to tagged arcs on the surfaces, Musiker, Schiffler, Williams significantly strengthened this result. Namely, they showed the coefficients of these Laurent polynomials are always non-negative \cite{musiker2011positivity} -- a particularly elusive conjecture at the time. Their beautiful result established a remarkable connection between monomials of the Laurent polynomial and perfect matchings of \textit{snake} graphs. For plain arcs this connection may be thought of as a perfect fit, as there is a bijection between the monomials and the collection of all perfect matchings of the associated snake graph (with respect to an initial ideal triangulation). However, for a general tagged arc this correspondence is somehow lost; one must consider much larger graphs and restrict attention to the so called `$\gamma$-symmetric' perfect matchings' or `$\gamma$-compatible pairs' of `$\gamma$-symmetric' perfect matchings.

In this paper, in an effort to find an optimal framework for all tagged arcs, we introduce the notion of \textit{loop} graphs. Roughly speaking this is the result of gluing the end(s) of a snake graph to an existing tile(s). The following theorem shows that \textit{good} matchings of loop graphs effectively describe the cluster variable expansion of any tagged arc, with respect to any tagged triangulation. \newline

\noindent \textbf{Main Theorem} (Theorem \ref{loopexpansion}). \textit{Let $(S,M)$ be a bordered surface. Let $T^{\circ}$ be an ideal triangulation with corresponding tagged triangulation $T = \iota(T^\circ)$. Let $\mathcal{A}$ be the associated cluster algebra with principal coefficients with respect to $\Sigma_T = (\mathbf{x}_T,\mathbf{y}_T,B_T)$. Suppose $\gamma$ is a tagged arc whose underlying plain arc $\gamma^{\circ}$ is not in $T$, and suppose that $\gamma$ is not notched at any puncture enclosed by a self-folded triangle in $T$ (for technical reasons, if $\gamma$ is doubly notched then we also assume $(S,M)$ is not twice-punctured and closed). Then the Laurent expansion of $x_{\gamma} \in \mathcal{A}$ with respect to $\Sigma_T$ is given by:}

\begin{equation}
\label{main theorem}
x_{\gamma} = \frac{1}{cross(\gamma, T^{\circ})}\sum_{P} x(P)y(P).
\end{equation}

\noindent \textit{where the sum is taken over all good matchings $P$ of the loop graph $\mathcal{G}_{\gamma,T}$.} \newline \indent

We believe the above result will be particularly useful in obtaining skein relations between (generalised) tagged arcs and closed curves on $(S,M)$. As a direct consequence one could then use this to obtain bases for all (full rank) cluster algebras arising from surfaces [Appendix A, \cite{musiker2013bases}]. \newline \indent

At first glance the conditions imposed on the Main Theorem may seem quite restrictive. However, we will now explain that the only real restriction comes from the exclusion of doubly notched arcs on twice punctured closed surfaces.

The general case is wishing to write a cluster variable $x_{\gamma}$ with respect to a tagged triangulation $T$, where $\gamma$ is a tagged arc. That being said, this can always be reduced to the case where $T = \iota (T^{\circ})$ and $\gamma$ is not notched inside a self-folded triangle in $T^{\circ}$ by the following symmetry. Let $\gamma$ be a tagged arc and let $\gamma'$ be the tagged arc obtained from reversing the tagging of $\gamma$ at each endpoint incident to a puncture. Similarly, let $T$ be a tagged triangulation and let $T'$ be the tagged triangulation obtained from reversing the tagging of $T$ at each puncture. Then the function $x_{\gamma}$ written with respect to $T$ is precisely the function $x_{\gamma'}$ written with respect to $T'$ (this is easily verified directly from the definitions given in Section \ref{Cluster algebras from surfaces}). \newline \indent Note that the Main Theorem also demands that the underlying plain arc $\gamma^{\circ}$ is not in $T$. Nevertheless, a (positive) Laurent expansion may still be obtained from equation (\ref{main theorem}) if $\gamma^{\circ} \in T$ by the following two approaches. If $\gamma$ is a singly notched arc at a puncture $p$ then we may use the equality $x_{\ell_p} = x_{\gamma}x_{\gamma^{\circ}}$ and write $x_{\gamma}$ using equation (\ref{main theorem}) applied to the arc $\ell_p$. If $\gamma$ is doubly notched then a formula is obtained by considering the expansion $x_{\gamma}$ of $\gamma$ with respect to $\mu_{\gamma^{\circ}}(T)$, and showing that $x_{\gamma^{\circ}}$ is a factor of this expression -- this property is easily observed directly from the loop graph $\mathcal{G}_{\gamma,\mu_{\gamma^{\circ}}(T)}$. \newline \indent
Finally, regarding the choice of coefficients, by the `separation of additions' formula of Fomin and Zelevinsky \cite{fomin2007cluster}, it is enough to consider only principal coefficients. Indeed, if $z$ is a cluster variable in a cluster algebra (with any choice of coefficients), their result states $z$ is obtained by a certain specialisation (and rescaling) of the corresponding cluster variable in the cluster algebra with principal coefficients. \newline \indent Therefore, as in the work of Musiker, Schiffler, Williams \cite{musiker2011positivity}, the only case for which the Main Theorem does not produce an explicit Laurent expansion is when $\gamma$ is a doubly notched arc on a twice punctured closed surface, and $T$ is an ideal triangulation without a self-folded triangle (or equivalently, $\gamma$ is a plain arc and $T$ is a tagged triangulation for which all endpoints of arcs are notched). Note that by the groundbreaking works of Gross, Hacking, Keel, Kontsevich \cite{gross2018canonical}, or Lee, Schiffler \cite{lee2015positivity}, the Laurent expansion must have non-negative coefficients; it is just not known whether equation (\ref{main theorem}) holds. \newline

\indent The paper is organised as follows. Section 2 gives a very brief overview of cluster algebras and their relation to triangulated surfaces. In Section 3 we recall the construction of snake graphs, and introduce a like-minded generalisation called \textit{loop graphs}. In Section 4 we then show how one can associate these loop graphs to tagged arcs, with respect to ideal triangulations. The main result of the paper is given in Section 5, which shows that one can compute cluster variable expansions via good matchings of loop graphs, for any surface cluster algebra. The proof of this result is given in Section 6, which revolves around reinterpreting statements about `$\gamma$-symmetric' perfect matchings and `$\gamma$-compatible pairs' of `$\gamma$-symmetric' perfect matchings, as statements about good matchings of loop graphs. Finally, in Section 7 we show the collection of good matchings of any (surface) loop graph can be naturally endowed with a lattice structure.

\section*{\large \centering Acknowledgements}

The author is grateful for the generous support they received from Prof. Christof Geiss' CONACyT-239255 grant, Prof. Daniel Labardini-Fragoso's grants: CONACyT-238754 and C\'{a}tedra Marcos Moshinsky, and their postdoctoral fellowship at IMUNAM. The author also thanks Anna Felikson for helpful comments improving the readability of the text.

\section{Preliminaries}

\subsection{Cluster algebras}

This section provides a brief review of (skew-symmetric) cluster algebras of geometric type. Let $n \leq m$ be positive integers. Furthermore, let $\mathcal{F}$ be the field of rational functions in $m$ independent variables. Fix a collection $X_1,\ldots,X_n, x_{n+1},\ldots, x_m$ of algebraically independent variables in $\mathcal{F}$. We define the \textit{coefficient ring} to be $\mathbb{ZP}:=\mathbb{Z}[x_{n+1}\ldots x_m]$.

\begin{defn}
A \textit{\textbf{(labelled) seed}} consists of a pair, $(\mathbf{x},\mathbf{y}, B)$, where

\begin{itemize}[leftmargin=6.8mm]

\item $\mathbf{x} = (x_1,\ldots x_n)$ is a collection of variables in $\mathcal{F}$ which are algebraically independent over $\mathbb{ZP}$,

\item $\mathbf{y} = (y_1,\ldots y_n)$ where $y_k = \displaystyle \prod_{j=n+1}^{m} x_j^{b_{jk}}$ for some $b_{jk} \in \mathbb{Z}$,

\item $B = (b_{jk})_{j,k \in \{1,\ldots, n\}}$ is an $n \times n$ skew-symmetric integer matrix.
\end{itemize}

The variables in any seed are called \textit{\textbf{cluster variables}}. The variables $x_{n+1},\ldots,x_m$ are called \textit{\textbf{frozen variables}}. We refer to $\mathbf{y}$ as the \textbf{\textit{choice of coefficients}}.

\end{defn}

\begin{defn}

Let $i \in \{1,\ldots,n\}$. We define a new seed $\mu_{i}(\mathbf{x},\mathbf{y},B) := (\mathbf{x}',\mathbf{y}',B')$, where:

\begin{itemize}[leftmargin=6.8mm]

\item $\mathbf{x}' = (x'_1,\ldots x'_n)$ is defined by

$$x'_i = \frac{\displaystyle \prod_{b_{ki} >0} x_k^{b_{ki}} + \prod_{b_{ki} <0} x_k^{-b_{ki}}}{x_i}$$

and setting $x_j' = x_j$ when $j \neq i$;

\item $\mathbf{y}'$ and $B' = (b'_{jk})$ are defined by the following rule:

\[
b'_{jk} =
     \begin{cases}
       -b_{jk},& \text{if $j=i$ or $k=i$,}\\
       b_{jk} + \max(0,-b_{ji})b_{ik} + \max(0,b_{ik})b_{ji},& \text{otherwise.}\\
     \end{cases}
\]

\end{itemize}

\end{defn}

\begin{defn}
\label{cluster algebra}
Fix an \textit{initial seed} $ (\mathbf{x},\mathbf{y}, B)$. If we label the \textit{initial cluster variables} of $ \mathbf{x}$ from $1,\ldots, n $ then we may consider the labelled n-regular tree $\mathbb{T}_n $. Each vertex in $ \mathbb{T}_n $ has $ n$ incident edges labelled $1,\ldots,n $. Vertices of $ \mathbb{T}_n $ represent seeds and the edges correspond to mutation. In particular, the label of the edge indicates which direction the seed is being mutated in.

Let $\mathcal{X} $ be the set of all cluster variables appearing in the seeds of $ \mathbb{T}_n$. The \textit{\textbf{cluster algebra}} of the seed $ (\mathbf{x},\mathbf{y}, B) $ is defined as $ \mathcal{A}(\mathbf{x},\mathbf{y}, B ) := \mathbb{ZP}[\mathcal{X}]$. \newline \indent We say $\mathcal{A}(\mathbf{x},\mathbf{y}, B)$ is the \textbf{\textit{cluster algebra with principal coefficients}} if $m = 2n$ and $\mathbf{y} = (y_1, \ldots, y_n)$ satisfies $y_k = x_{n+k}$ for any $k \in \{1,\ldots, n\}$.

\end{defn}

\subsection{Cluster algebras from surfaces}
\label{Cluster algebras from surfaces}

In this subsection we recall the work of Fomin, Shapiro and Thurston \cite{fomin2008cluster}, which establishes a cluster structure for triangulated orientable surfaces. \newline \indent

Let $S$ be a compact orientable $2$-dimensional manifold. Fix a finite set $M$ of marked points of $S$ such that each boundary component contains at least one marked point -- we refer to marked points in the interior of $S$ as \textit{punctures}. The pair $(S,M)$ is called a \textit{\textbf{bordered surface}}. For technical reasons we exclude the cases where $(S,M)$ is an unpunctured or once-punctured monogon; a digon; a triangle; or a once, twice or thrice punctured sphere.

\begin{defn}

An \textit{\textbf{arc}} of $(S,M)$ is a simple curve in $S$ connecting two marked points of $M$, which is not isotopic to a boundary segment or a marked point.
\end{defn}

\begin{defn}

A \textit{\textbf{tagged arc}} $\gamma$ is an arc whose endpoints have been `tagged' in one of two ways; \textit{\textbf{plain}} or \textit{\textbf{notched}}. Moreover, this tagging must satisfy the following conditions: if the endpoints of $\gamma$ share a common marked point, they must receive the same tagging; and an endpoint of $\gamma$ lying on the boundary $\partial S$ must always receive a plain tagging. In this paper we shall always consider tagged arcs up to isotopy.

\end{defn}

\begin{defn}

Let $\alpha$ and $\beta$ be two tagged arcs of $(S,M)$. We say $\alpha$ and $\beta$ are \textit{\textbf{compatible}} \textit{if and only if} the following conditions are satisfied:

\begin{itemize}
\item There exist isotopic representatives of $\alpha $ and $\beta$ that don't intersect in the interior of $S$.

\item Suppose the untagged versions of $ \alpha$ and $\beta $ do not coincide. If $ \alpha$ and $\beta$ share an endpoint $p$ then the ends of $\alpha $ and $\beta $ at $p $ must be tagged in the same way.

\item Suppose the untagged versions of $\alpha $ and $\beta $ do coincide. Then precisely one end of $ \alpha $ must be tagged in the same way as the corresponding end of $\beta$.

\end{itemize}

A \textbf{\textit{tagged triangulation}} of $(S,M) $ is a maximal collection of pairwise compatible tagged arcs of $(S,M) $. Moreover, this collection is forbidden to contain any tagged arc that enclose a once-punctured monogon.

An \textit{\textbf{ideal triangulation}} of $ (S,M)$ is a maximal collection of pairwise compatible plain arcs. Note that ideal triangulations decompose $(S,M)$ into triangles, however, the sides of these triangles may not be distinct; two sides of the same triangle may be glued together, resulting in a \textit{self-folded triangle}.
\end{defn}

\begin{rmk}

To each tagged triangulation $T$ we may uniquely assign an ideal triangulation $T^{\circ}$ as follows:

\begin{itemize}

\item  If $p$ is a puncture with more than one incident notch, then replace all these notches with plain taggings.

\item  If $ p$ is a puncture with precisely one incident notch, and this notch belongs to $ \beta \in T$, then replace $\beta $ with the unique arc $\gamma $ of $(S,M)$ which encloses $\beta $ and $p $ in a monogon.

\end{itemize}

Conversely, to each ideal triangulation $T $ we may uniquely assign a tagged triangulation $ \iota(T)$ by reversing the second procedure described above.
\end{rmk}

\begin{defn}
\label{adjacency matrix}
Let $T$ be a tagged triangulation, and consider its associated ideal triangulation $ T^{\circ}$. We may label the arcs of $T^{\circ} $ from $ 1,\ldots, n$ (note this also induces a natural labelling of the arcs in $ T$). We define a function, $ \pi_{T} : \{1,\ldots,n\} \rightarrow \{1,\ldots,n\} $, on this labelling as follows:
\[
\pi_{T}(i) =
     \begin{cases}
       j & \text{if $ i $ is the glued side of a self-folded triangle in $ T^{\circ}$, and $j$ is the remaining side;}\\
       i & \text{otherwise.}\\
     \end{cases}
\]

For each non-self-folded triangle $ \Delta$ in $T ^{\circ} $, as an intermediary step, define the matrix $ B_T^{\Delta} = (b^{\Delta}_{jk}) $ by setting

\[
b^{\Delta}_{jk} =
     \begin{cases}
       1 & \text{if $\Delta$ has sides $ \pi_{T}(j)$ and $ \pi_{T}(k)$, and $ \pi_{T}(k) $ follows $ \pi_{T}(j) $ in a clockwise order;}\\
       -1 & \text{if $ \Delta$ has sides $ \pi_{T}(j)$ and $\pi_{T}(k) $, and $ \pi_{T}(k) $ follows $\pi_{T}(j)$ in an  anti-clockwise order;}\\
       0 & \text{otherwise}\\
     \end{cases}
\]

The \textit{\textbf{adjacency matrix}} $ B_T = (b_{ij}) $ of $ T $ is then defined to be the following summation, taken over all non-self-folded triangles $ \Delta$ in $ T^{\circ}$:
$$B_T:=  \sum\limits_{\Delta} B_T^{\Delta} $$

\end{defn}

\begin{defn}

Let $T $ be a triangulation of a bordered surface $ (S,M)$. Consider the initial seed $ (\mathbf{x},\mathbf{y},B_T) $, where: $ \mathbf{x} $ contains a cluster variable for each arc in $T $; $B_T $ is the matrix defined in Definition \ref{adjacency matrix}; and $ \mathbf{y}$ is any choice of coefficients. We call $ \mathcal{A}(\mathbf{x}, \mathbf{y}, B_T)$ a \textbf{\textit{surface cluster algebra}}.

\end{defn}

\begin{thm}[Theorem 6.1, \cite{fomin2018cluster}]
\label{surface correspondence}
Let $(S,M) $ be a bordered surface. If $ (S,M)$ is not a once punctured closed surface, then in the cluster algebra $\mathcal{A}(\mathbf{x}, \mathbf{y}, B_T)$, the following correspondence holds:
\begin{align*}
 &\hspace{23mm} \mathbf{\mathcal{A}(\mathbf{x}, \mathbf{y}, B_T)} & &  &\mathbf{(S,M)} \hspace{26mm}&   \\
 &\hspace{18mm} \textit{Cluster variables}  &\longleftrightarrow&  &\textit{Tagged arcs} \hspace{23mm} &  \\
 &\hspace{25mm}\textit{Clusters}   &\longleftrightarrow&  &\textit{Tagged triangulations} \hspace{14mm}&  \\
 &\hspace{24mm} \textit{Mutation}    &\longleftrightarrow&   &\textit{Flips of tagged arcs} \hspace{16mm}&  \\
\end{align*}

When $(S,M)$ is a once-punctured closed surface then cluster variables are in bijection with all plain arcs or all notched arcs depending on whether $T$ consists solely of plain arcs or notched arcs, respectively.
\end{thm}

\section{Snake and loop graphs}

In this section we first recall the notion of an (abstract) \textit{snake} graph, as seen in \cite{canakci2013snake}, \cite{canakci2015snake}. Following this, we define \textit{loop} graphs which share a similar flavour to band graphs.

\subsection{Snake graphs}

\begin{defn}

A \textbf{\textit{tile}} is a graph comprising of four vertices and four edges, where each vertex has degree two. \newline
\indent We shall always embed this graph in the plane, viewing a tile as a square whose edges are parallel to the $ x $ and $ y $ axes. With respect to this embedding we label the edges North (N), East (E), South (S) and West (W), as shown in Figure \ref{tile}.

\begin{figure}[H]
\begin{center}
\includegraphics[width=3cm]{tile.pdf}
\caption{A tile with North, East, South and West edge labelings.}
\label{tile}
\end{center}
\end{figure}

\end{defn}

Two tiles are said to be \textbf{\textit{glued}} if they share a common edge. The graphs considered in this paper will all be obtained via the process of gluing tiles, and the following definition gives the basic recipe of this.

\begin{defn}

A \textbf{\textit{snake graph}}, $ \mathcal{G} = (G_1, \ldots, G_d) $, is a sequence of tiles $ G_1, \ldots, G_d $ such that the following holds for each $ i \in \{1,\ldots, d-1\} $:

\begin{itemize}

\item the North or East edge of $ G_i $ is glued to the South or West edge of $ G_{i+1 } $,

\item $ G_i $ and $ G_{i+1 } $ are glued at precisely one edge.

\end{itemize}

A subsequence of consecutive tiles $ G_i, G_{i+1}, \ldots, G_{j-1}, G_j $ occuring in $ \mathcal{G} $ is called a \textbf{\textit{sub (snake) graph}} of $\mathcal{G} $.

\end{defn}

\begin{defn}

Let $ \mathcal{G} = (G_1,  \ldots , G_d) $ be a snake graph.

\begin{itemize}

\item If the North (resp. East) edge of $ G_i $ is glued to the South (resp. West) edge of $ G_{i+1} $ for every $ i \in \{1,\ldots, n-1\} $, then $ \mathcal{G} $ is said to be \textbf{\textit{straight}}.

\item $ \mathcal{G}$ is said to be \textbf{\textit{zig-zag}} if no three consecutive tiles $ G_i, G_{i+1}, G_{i+2} $ of $ \mathcal{G}$ form a straight sub snake graph.

\end{itemize}

\end{defn}

\begin{figure}[H]
\begin{center}
\includegraphics[width=10cm]{snakegraph.pdf}
\caption{On the left we show a general snake graph $\mathcal{G}$. The two snake graphs on the right are straight and zig-zag sub snake graphs of $\mathcal{G}$, respectively.}
\label{snakegraph}
\end{center}
\end{figure}

\begin{defn}

A \textit{\textbf{perfect matching}} of a graph $ G $ is a collection of edges of $ G $ such that every vertex of $ G $ is contained in exactly one of these edges.

\end{defn}

\begin{prop}[Section 4.3, \cite{musiker2010cluster}]
\label{induceddef}

Any perfect matching $P$ of a snake graph $\mathcal{G} = (G_1,\ldots, G_d)$ induces an orientation on the diagonal of each tile $G_i$.\newline \indent Specifically, this is induced by travelling from the south-west vertex of $G_1$ to the north-east vertex of $G_d$ by alternating travel along edges in $P$ and diagonals of $\mathcal{G}$. Following this procedure, each diagonal of $\mathcal{G}$ (and each edge in $P$) will be traversed precisely once.

\end{prop}

\begin{figure}[H]
\begin{center}
\includegraphics[width=8cm]{induceddiagonal.pdf}
\caption{A perfect matching $P$ of a snake graph. The orientation $P$ induces on the diagonals is shown in blue.}
\label{induceddiagonal}
\end{center}
\end{figure}

\subsection{Loop graphs}

Roughly speaking, a loop graph is obtained from a snake graph by (potentially) creating a loop at each end. Namely, each end of the snake graph may be glued to a previous tile. Just as snake graphs enable us to obtain expansion formulae for cluster variables corresponding to plain arcs \cite{musiker2011positivity}, loop graphs will provide us with the framework to write expansion formulae for the variables corresponding to any tagged arc.

\begin{defn}
\label{loopgraphrules}

Let $\mathcal{G} = (G_1, \ldots, G_d)$ be a snake graph. \newline \indent Let $c$ be an edge of $\{S(G_1),W(G_1)\}$. Furthermore, let $x \in c$ denote the South-West vertex of $G_1$, and let $y$ denote the remaining vertex of $c$. Let $k \in \{2,\ldots, d\}$ and denote by $c'$ the edge in $\{S(G_k),W(G_k)\}$ which is a boundary edge. We let $y' \in c'$ denote the South-West vertex of $G_k$, and let $x'$ denote the remaining vertex of $c'$.

The \textbf{\textit{loop}} with respect to $G_1$ and $k$ is obtained by gluing $c$ to $c'$ such that $x$ (resp. $y$) is glued to $x'$ (resp. $y'$). By abuse of notation we also denote the resulting glued edge by $c$, and call this the \textbf{\textit{cut}}.

We define a loop with respect to the other endtile $G_d$ of $\mathcal{G}$ analogously; one should just replace South and West with North and East, and choose $k \in \{1, \ldots, d-1\}$.

\begin{defn}
\label{loopgraph}
A \textbf{\textit{loop graph}} $\mathcal{G}^{\bowtie}$ is obtained from $\mathcal{G} = (G_1, \ldots, G_d)$ by creating a loop with respect to $G_1$ and $k_1 \in \{2,\ldots, d\}$ and creating a loop with respect to $G_d$ and $k_2 \in \{1,\ldots, d-1\}$.  \newline \indent We extend the definition to all $k_1,k_2 \in \{1,\ldots, d\}$ by demanding there is no loop with respect to $G_1$ (resp. $G_d$) if $k_1 = 1$ (resp. $k_2 = d$). Consequently, loop graphs are snake graphs for which zero, one or two ends have been glued. In this paper we will always have $k_1 \leq k_2$.
\end{defn}

\begin{figure}[H]
\begin{center}
\includegraphics[width=10cm]{loopgluing.pdf}
\caption{An example of a loop graph which has loops at both of its ends.}
\end{center}
\end{figure}

\end{defn}

\begin{defn}
\label{good matching}

As in Definition \ref{loopgraph}, let $\mathcal{G}^{\bowtie}$ be a loop graph obtained from a snake graph $\mathcal{G}$. A \textbf{good matching} of $\mathcal{G}^{\bowtie}$ is a perfect matching which can be extended to a perfect matching of $\mathcal{G}$.
\end{defn}

\begin{rmk} Definition \ref{good matching} may be restated as follows. A perfect matching $P$ of $\mathcal{G}^{\bowtie}$ is a good matching if, for each cut $c$, the edges matching the vertices of $c$ both lie on the `same side' of the cut. That is, when viewed as a matching of $\mathcal{G}$, $P$ must contain edge(s) matching both $x$ and $y$ or both $x'$ and $y'$ (but not both). We introduce the following terminology:

\begin{itemize}

\item  $P$ is a \textbf{\textit{right cut}} with respect to $c$ if $x$ and $y$ are matched in $\mathcal{G}$.

\item $P$ is a \textbf{\textit{left cut}} with respect to $c$ if $x'$ and $y'$ are matched in $\mathcal{G}$.

\item $P$ is a \textbf{\textit{centre cut}} with respect to $c$ if $P$ contains $c$.

\end{itemize}

\end{rmk}

\begin{figure}[H]
\begin{center}
\includegraphics[width=10cm]{badmatching.pdf}
\caption{An example of a perfect matching $P$ (indicated by the red edges) of a loop graph which is \underline{not} a good matching. Indeed, whilst $P$ is a left cut with respect to $c_2$, it is not a right, left nor centre cut with respect to $c_1$.}
\end{center}
\end{figure}

\begin{prop}

As in Proposition \ref{induceddef}, any good matching $P$ of a loop graph $\mathcal{G}^{\bowtie}$ induces an orientation on the diagonal of each tile of $\mathcal{G}^{\bowtie}$.

\end{prop}

\begin{proof}

By definition of a good matching, $P$ can be (uniquely) extended to a perfect matching of the underlying snake graph $\mathcal{G}$. The result then follows from Proposition \ref{induceddef}.

\end{proof}

\section{Snake and loop graphs from surfaces}
\label{snakebandconstruction}

Following the work of Musiker, Schiffler and Williams we first explain how to associate snake graphs to plain arcs of $(S,M)$ with respect to ideal triangulations \cite{musiker2011positivity}. We then generalise this approach and associate loop graphs to all tagged arcs. The basic principle is that tiles in our snake and loop graphs correspond to quadrilaterals on the surface.

\subsection{Snake graphs associated to plain arcs}

\subsubsection{T is an ideal triangulation without self-folded triangles}

For simplicity we first restrict our attention to when $T$ is an ideal triangulation containing no self-folded triangles.

\begin{defn}
\label{relativeorientation}

Let $\gamma$ be a directed plain arc in $(S,M)$, and denote by $p_1, \ldots, p_d$ the intersection points of $\gamma$ with $T = \{\tau_1, \ldots, \tau_n\}$ (listed in order of intersection). In this way we obtain a sequence $i_1, \ldots, i_d$ such that $p_k$ belongs to $\tau_{i_k}$ for each $k \in \{1,\ldots, d\}$. \newline \indent
Let $Q_{i_j}$ be a quadrilateral in $T$ with diagonal labelled by $\tau_{i_j}$. Let $\Delta_j$ and $\Delta_{j+1}$ denote the triangles in $T$ either side of $\tau_{i_j}$, labelled so that, with respect to the orientation of $ \gamma $ through $ p_j $, $ \Delta_j $ precedes $ \Delta_{j+1} $. We view $Q_{i_j}$ as a tile $G_j$ by deleting the diagonal $\tau_{i_j}$ and embedding it in the plane so that:

\begin{itemize}

\item the (deleted) diagonal $\tau_{i_j}$ of $Q_{i_j}$ connected the north-west and south-east vertices of $G_j$.

\item $\Delta_j$ forms the lower half of $G_j$.

\end{itemize}

There are two possible ways to follow the rules above: if the orientation on $ Q_{i_j} $ (induced by $ (S,M) $) agrees with the orientation on $ G_j $ (induced by the clockwise orientation of the plane) then we write $ rel(G_j) =1 $; if it disagrees then $rel(G_j) = -1$. The quantity $rel(G_j)$ is called the \textbf{\textit{relative orientation}} of the tile $G_j$ with respect to $(S,M)$.

\end{defn}

\begin{figure}[H]
\begin{center}
\includegraphics[width=13cm]{tileorientation.pdf}
\caption{An example of relative orientation. The faded line indicates the deleted diagonal.}
\end{center}
\end{figure}

\begin{defn}
\label{arcsnakegraph}

Let $\gamma$ be a plain arc in $(S,M)$. As in Definition \ref{relativeorientation} we associate a tile $G_i$ for each intersection point, $p_i$, such that $rel(G_i) \neq rel(G_{i+1})$. For each $j \in \{1,\ldots, d-1\}$ note that $\tau_{i_j} $ and $\tau_{i_{j+1}} $ form two sides of the triangle $\Delta_j$; we denote the remaining side by $\tau_{[i_j]}$. The snake graph $\mathcal{G}_{\gamma,T} = (G_1,\ldots, G_d)$ associated to $\gamma$ and $T$ is determined by gluing $G_j$ to $G_{j+1}$ along their common edge $\tau_{[i_j]}$.

\end{defn}

\begin{figure}[H]
\begin{center}
\includegraphics[width=15cm]{surfacesnakenew.pdf}
\caption{The construction of a snake graph from a plain arc. The thin lines indicate the associated diagonals of the tiles, however, these are not considered edges of the actual snake graph.}
\end{center}
\end{figure}

\subsubsection{T is an arbitrary ideal triangulation}

We now consider the general setup when T is an arbitrary ideal triangulation. Note that in this situation, ambiguities may arise if we followed the gluing procedures outlined in Definition \ref{arcsnakegraph}. Specifically, ambiguity occurs precisely when passing through a self-folded triangle. Musiker, Schiffler and Williams \cite{musiker2011positivity} addressed these points using the following two definitions.

\begin{defn}
Let $\gamma$ be an oriented plain arc. As usual, let $ p_1, \ldots, p_d $ denote the intersection points of $ \gamma $ with $ T = \{\tau_1, \ldots, \tau_n\} $, and let $\tau_{i_j}$ denote the arc in $T$ containing $p_j$. We associate a tile $G_j$ to each $p_j$ as follows. If $\tau_{i_j}$ is not the folded side of a self-folded triangle in $T$ then $G_j$ is defined as in Definition \ref{relativeorientation}, and is called an \textit{\textbf{ordinary tile}}. Otherwise, the \textit{\textbf{non-ordinary tile}} $G_j$ is defined by glueing two copies of the triangle $(\tau_{i_{j}}, \tau_{i_{j-1}} = \tau_{i_{j+1}}, \tau_{i_j})$ along $\tau_{i_{j}}$, such that the labels on the North and West (equivalently South and East) edges of $G_j$ are equal.  As usual, in both cases, the diagonal $\tau_{i_j}$ is not considered an edge of $G_j$.

\end{defn}

\begin{defn}
\label{snakegraph}

The \textit{\textbf{snake graph}} $\mathcal{G}_{\gamma,T}$ associated to a directed plain arc $\gamma$ is defined as follows:

\begin{itemize}

\item If $G_j$ and $G_{j+1}$ are both ordinary tiles then they are glued as in Definition \ref{arcsnakegraph}.

\item If $G_j$ is a non-ordinary tile then it is glued to $G_{j-1}$ and $G_{j+1}$ according to the arrangement illustrated in Figure \ref{nonordinarytile}.

\end{itemize}

For ordinary tiles we have the notion of \textit{relative orientation} given in Definition \ref{relativeorientation}. This notion is extended to each non-ordinary tile $G_j$ by demanding $rel(G_j) := -rel(G_{j-1})$. Note that the equality $rel(G_i) = -rel(G_{i-1})$ will consequently hold for all tiles appearing in $\mathcal{G}_{\gamma,T}$.

\end{defn}

\begin{figure}[H]
\begin{center}
\includegraphics[width=12cm]{nonordinarytilenew.pdf}
\caption{The gluing instructions of non-ordinary tiles in a snake graph, see Definition \ref{snakegraph}.}
\label{nonordinarytile}
\end{center}
\end{figure}

\subsection{Loop graphs associated to tagged arcs}

To associate loop graphs to tagged arcs it will first be helpful to introduce the notion of a \textit{hook}. This was also used by Labardini-Fragoso in the context of representations of quivers with potentials [Section 6.3, \cite{labardini2010quivers}].

\begin{defn}

Let $\gamma$ be a directed arc and let $T$ be an ideal triangulation. If an endpoint of $\gamma$ is incident to a puncture $p$, we define the \textbf{\textit{hook}} at this endpoint to be the curve which:

\begin{itemize}

\item travels around $p$ (clockwise or anticlockwise) intersecting each incident arc at $p$ in $T$ exactly once (up to multiplicity of degree), and then follows $\gamma$, if $\gamma$ starts at the endpoint;

\item or follows $\gamma$ and then travels around $p$ (clockwise or anticlockwise) intersecting each incident arc at $p$ in $T$ exactly once (up to multiplicity of degree), if $\gamma$ ends at the endpoint.

\end{itemize}

\end{defn}

\begin{defn}

Let $\gamma$ be a tagged arc and let $T$ be an ideal triangulation. The associated \textit{\textbf{hooked arc}} $\overset{{}_{\backsim}}{\gamma}$ is obtained by replacing each notched endpoint of $\gamma$ with a hook.

\end{defn}

\begin{figure}[H]
\begin{center}
\includegraphics[width=10cm]{hook.pdf}
\caption{A hook associated to a notched endpoint. The arcs in $T$ incident to the puncture determine where the hook ends.}
\label{hook}
\end{center}
\end{figure}

\begin{defn}
\label{surfaceloopgraph}

Let $\gamma$ be a tagged arc such that the underlying plain arc $\gamma^{\circ}$ is not in $T$. Moreover, we suppose that $\gamma$ is not notched at any puncture enclosed by a self-folded triangle in $T$. Consider the snake graph $G_{\overset{{}_{\backsim}}{\gamma},T} = (G_1,\ldots, G_d)$ obtained from the associated hooked arc $\overset{{}_{\backsim}}{\gamma}$. Note that $G_{\gamma^{\circ},T} = (G_{k_1},\ldots, G_{k_2})$ is a subgraph of $G_{\overset{{}_{\backsim}}{\gamma},T}$ for some $k_1,k_2 \in \{1,\ldots, d\}$. \newline \indent
We define $G_{\gamma,T}$ to be the loop graph of $G_{\overset{{}_{\backsim}}{\gamma},T}$ with respect to loops at $G_1, k_1$ and $G_d, k_2$. We call $G_{\gamma,T}$ the \textit{\textbf{loop graph of $\gamma$ with respect to $T$}}. Moreover, any loop graph $\mathcal{G}^{\bowtie}$ arising in this way is called a \textit{\textbf{surface loop graph}}.

\end{defn}

\begin{rmk}

Note that the hooked arc $\overset{{}_{\backsim}}{\gamma}$ is not unique, since there is a choice of orientation around the puncture at each notched endpoint. However, up to isomorphism, the resulting loop graph $G_{\gamma,T}$ is independent of this choice.

\end{rmk}

\begin{figure}[H]
\begin{center}
\includegraphics[width=14cm]{single.pdf}
\caption{An example of the loop graph associated to a singly notched arc. The edge connecting $x_1$ and $y_1$ is glued to the edge connecting $x_1'$ and $y_1'$, where $x_1$ (resp. $y_1$) is glued to $x_1'$ (resp. $y_1'$).}
\label{single}
\end{center}
\end{figure}

\vspace{-10mm}

\section{Expansion formulae for tagged arcs via loop graphs}

Let $T = \{\tau_1, \ldots, \tau_n\}$ be an ideal triangulation with corresponding tagged triangulation $\iota(T) = \{\tau_1', \ldots, \tau_n'\}$. Let $x_{\tau_1'}, \ldots, x_{\tau_n'}$ be the cluster variables corresponding to $\iota(T)$; when the context is clear we write $x_1, \ldots, x_n$. In a similar fashion we associate variables to $T$: if $\tau_i \in T$ encloses a punctured monogon then it encloses $\tau_i'$ and $\tau_j'$, for some $j$, and we set $x_{\tau_i} := x_ix_j$, otherwise we set $x_{\tau_i} := x_i$. For the (principal) coefficients we set $y_{\tau_i} := y_{\tau_i'} := y_i$ for each $i$.

\begin{defn}

Let $T = \{\tau_1, \ldots, \tau_n\}$ be an ideal triangulation and let $\gamma$ be a directed tagged arc whose underlying plain arc $\gamma^{\circ}$ is not in $T$. We denote by $\tau_{i_1}, \ldots, \tau_{i_d}$ the sequence of arcs in $T$ which the associated hooked arc $\overset{{}_{\backsim}}{\gamma}$ intersects. The \textit{\textbf{crossing monomial}} of $\gamma$ with respect to $T$ is defined as:  \vspace{-1.5mm} $$cross(\gamma, T) := {\displaystyle \prod_{j=1}^{d} x_{\tau_{i_j}}}.$$

\end{defn}

\begin{defn}

Let $T = \{\tau_1, \ldots, \tau_n\}$ be an ideal triangulation and let $ \gamma $ be a directed arc with associated loop graph $ \mathcal{G}_{\gamma,T} $. For a good matching $ P$ of $\mathcal{G}_{\gamma,T} $ we define the \textit{\textbf{ weight monomial}} $x(P) $ as follows:  \vspace{-0.5mm}

$$ x(P) := {\displaystyle \prod_{\tau_i \in P} x_{\tau_i}}. $$

\end{defn}

\begin{defn}

Let $T$ be an ideal triangulation and $\gamma$ a directed arc with associated loop graph $\mathcal{G}_{\gamma,T}$. Recall that every good matching $P$ of $\mathcal{G}_{\gamma,T}$ induces an orientation on the diagonals of each tile in $\mathcal{G}_{\gamma,T}$. We say the diagonal of a tile $G_j$ is \textit{\textbf{positive}} with respect to some $P$ if:

\begin{itemize}

\item the diagonal of $G_j$ is oriented `down' and $rel(G_j)=1$, or

\item the diagonal of $G_j$ is oriented `up' and $rel(G_j)= -1$,

\end{itemize}

\noindent and we say the diagonal is \textit{\textbf{negative}} otherwise.

\end{defn}

\begin{exmp}

In Figure \ref{induceddiagonal}, if we suppose $rel(G_1) = 1$, then the second, third, fourth and fifth diagonals are positive diagonals, and the remaining diagonals are negative with respect to $P$.

\end{exmp}

\begin{defn}

Let $T = \{\tau_1, \ldots, \tau_n\}$ be an ideal triangulation and $\gamma$ a tagged arc. For any good matching $P$ of a loop graph $\mathcal{G}_{\gamma,T} $ we define the \textit{\textbf{coefficient monomial}}, $y(P) $, as follows:

\begin{equation}
y(P) := \displaystyle \Big(\prod_{\substack{\text{$\tau_{i_j}$ is a } \\ \text{positive}\\ \text{diagonal }}}  y_{\tau_{i_j}} \Big) \Big(\prod_{\substack{\text{$\tau_{i_j}$ is a radius } \\ \text{and a positive}\\ \text{diagonal}}} y_{\tau_{i_j}^{(p)}}^{-1} \Big)
\end{equation}

\noindent where $\tau_{i_j}^{(p)} \in \iota(T)$ is obtained from the plain arc $\tau_{i_j} \in T$ by adding a notch at $p$.

\end{defn}

\begin{rmk}

Note that, for the convenience of this paper, $ y(P)$ is defined using the language of positive diagonals (first found in \cite{schiffler2010cluster} under the name of $\gamma$-oriented diagonals), rather than the symmetric difference of $P $ with the minimal matching $ P_{-}$. However, as discussed in \cite{musiker2010cluster}, one can easily move between the two.

\end{rmk}

\begin{thm}
\label{loopexpansion}
Let $(S,M)$ be a bordered surface. Let $T^{\circ}$ be an ideal triangulation with corresponding tagged triangulation $T= \iota(T^\circ)$. Let $\mathcal{A}$ be the associated cluster algebra with principal coefficients with respect to $\Sigma_T = (\mathbf{x}_T,\mathbf{y}_T,B_T)$. Suppose $\gamma$ is a tagged arc whose underlying plain arc $\gamma^{\circ}$ is not in $T$, and suppose that $\gamma$ is not notched at any puncture enclosed by a self-folded triangle in $T$ (for technical reasons, if $\gamma$ is doubly notched then we also assume $(S,M)$ is not twice-punctured and closed). Then the Laurent expansion of $x_{\gamma} \in \mathcal{A}$ with respect to $\Sigma_T$ is given by:

\begin{equation}
\label{loopexpansionformula}
x_{\gamma} = \frac{1}{cross(\gamma, T^{\circ})}\sum_{P} x(P)y(P).
\end{equation}

\noindent where the sum is taken over all good matchings $P$ of the loop graph $\mathcal{G}_{\gamma,T}$.

\end{thm}

\begin{rmk}

In this paper, the proof of equation (\ref{loopexpansionformula}) relies on the expansion formulae of Musiker, Schiffler, Williams. Therefore, as indicated, we do not cover the case when $\gamma$ is a doubly notched arc on a twice-punctured closed surface $(S,M)$. However, the strategy employed in the upcoming work \cite{Geiss2020bases} can be, with enough patience, extended to cover this case too.

\end{rmk}

\begin{exmp}
Consider the singly notched arc $\gamma$ and (ideal) triangulation $T$ found in Figure \ref{single}. To obtain the cluster variable $x_{\gamma}$ with respect to principal coefficients at $T$, Theorem \ref{loopexpansion} tells us we must compute the crossing monomial $cross(\gamma, T)$ and enumerate all good matchings of the associated loop graph (also found in Figure \ref{single}). We see $$cross(\gamma, T) = x_1x_2x_3x_4x_5x_6$$ and the complete collection of good matchings is provided in Figure \ref{singlelattice}. We thus obtain:

 \begin{gather}
    \nonumber x_{\gamma} = \frac{1}{x_1x_2x_3x_4x_5x_6}\Big( x_1x_2x_4^2x_6x_8 + x_1^2x_4x_6x_8x_{15} \textcolor{red}{y_3} + x_1x_2x_4x_8x_{11}x_{14}\textcolor{red}{y_5} + x_1x_3x_4x_6x_8x_{10}\textcolor{red}{y_2y_3} \\
   \nonumber \hspace{-32mm} + \hspace{2mm}  x_1^2x_8x_{11}x_{14}x_{15}\textcolor{red}{y_3y_5} + x_1x_2x_4x_5x_7x_{14}\textcolor{red}{y_5y_6} + x_1x_3x_5x_7x_8x_{15}\textcolor{red}{y_3y_4y_5} \\
    \nonumber \hspace{-15mm} + \hspace{2mm} x_1x_3x_8x_{10}x_{11}x_{14}\textcolor{red}{y_3y_5y_6} + x_1^2x_5x_7x_{14}x_{15}\textcolor{red}{y_2y_3y_4y_5} + x_3x_5x_7x_8x_{10}x_{11}\textcolor{red}{y_3y_4y_5y_6} \\
   \nonumber \hspace{-8.7mm} + \hspace{2mm} x_1x_3x_5^2x_7x_{15}\textcolor{red}{y_2y_3y_5y_6} + x_1x_3x_5x_7x_{10}x_{14}\textcolor{red}{y_1y_2y_3y_4y_5} + x_2x_3x_4x_5x_8x_{11}\textcolor{red}{y_2y_3y_4y_5y_6} \\
   \hspace{-74mm} + \hspace{2mm} x_3^2x_5^2x_7x_{10} + x_2x_3x_4x_5^2x_7\textcolor{red}{y_1y_2y_3y_4y_5y_6} \Big).
  \end{gather}

\end{exmp}

\begin{exmp}
The reader may find it helpful to compare the loop graph expansion formulae with Musiker, Schiffler, Williams' method. To this end, we now follow the doubly-notched example found in [Section 5.3, \cite{musiker2011positivity}], which we have also illustrated in Figure \ref{double}. For this choice of $\gamma$ and $T$, the collection of good matchings of $\mathcal{G}_{\gamma,T}$ is shown in Figure \ref{doublelattice}. Moreover, since $$cross(\gamma, T) = x_3x_4x_5x_6x_7x_8$$ Theorem \ref{loopexpansion} gives us the following expansion of $x_{\gamma}$ with respect to principal coefficients at $T$:

\begin{gather}
    \nonumber x_{\gamma} = \frac{1}{x_3x_4x_5x_6x_7x_8}\Big( x_3x_4x_6^2x_8 + x_4^2x_6x_8x_{10} \textcolor{red}{y_5} + x_3x_4x_6x_8x_9\textcolor{red}{y_7} + x_2x_4x_5x_6x_8\textcolor{red}{y_3y_5} \\
   \nonumber \hspace{-24.7mm} + \hspace{2mm}  x_4^2x_8x_{9}x_{10}\textcolor{red}{y_5y_7} + x_2x_4x_5x_8x_9\textcolor{red}{y_3y_5y_7} + x_4x_5x_7x_9x_{10}\textcolor{red}{y_5y_6y_7} \\
    \nonumber \hspace{-8.6mm} + \hspace{2mm} x_2x_5^2x_7x_9\textcolor{red}{y_3y_5y_6y_7} + x_4x_5x_6x_7x_{10}\textcolor{red}{y_5y_6y_7y_8} + x_3x_5x_6x_7x_9\textcolor{red}{y_3y_4y_5y_6y_7} \\
   \nonumber \hspace{-41.5mm} + \hspace{2mm}  x_2x_5^2x_6x_7\textcolor{red}{y_3y_5y_6y_7y_8} + x_3x_5x_6^2x_7\textcolor{red}{y_3y_4y_5y_6y_7y_8} \Big).
  \end{gather}

\end{exmp}

\begin{figure}[H]
\begin{center}
\includegraphics[width=14cm]{double.pdf}
\caption{An example of the loop graph associated to a doubly notched arc. The edge connecting $x_i$ and $y_i$ is glued to the edge connecting $x_i'$ and $y_i'$, for $i \in \{1,2\}$. In this gluing $x_i$ (resp. $y_i$) is glued to $x_i'$ (resp. $y_i'$).}
\label{double}
\end{center}
\end{figure}

\begin{figure}[H]
\begin{center}
\includegraphics[width=14cm]{singlelattice.pdf}
\caption{The lattice of good matchings of the loop graph found in Figure \ref{single}. Tiles with positive diagonals are shaded in green.}
\label{singlelattice}
\end{center}
\end{figure}

\begin{figure}[H]
\begin{center}
\includegraphics[width=10cm]{doublelattice.pdf}
\caption{The lattice of good matchings of the loop graph found in Figure \ref{double}. Tiles with positive diagonals are shaded in green.}
\label{doublelattice}
\end{center}
\end{figure}

\section{Proof of Theorem \ref{loopexpansion}}

We prove Theorem \ref{loopexpansion} by reinterpreting Musiker, Schiffler, Williams' language of `$\gamma$-symmetric perfect matchings' and `$\gamma$-compatible pairs of $\gamma$-symmetric perfect matchings' as statements about good matchings of loop graphs.

\subsection{$\gamma$-symmetric perfect matchings}

\begin{defn}
\label{singlynotched}
Let $ \gamma^{(p)} $ be a tagged arc which has one end notched at a puncture $p$, and its other end tagged plain at another marked point. We call $\gamma^{(p)} $ a \textbf{\textit{singly notched arc}} at $ p$ and denote its underlying plain arc by $\gamma$. Furthermore, we denote by $ \ell_p $ the unique plain arc enclosing $\gamma$ in a monogon with puncture $p$.
\end{defn}

Note that if $ \gamma$ has $k $ intersection points with $T ^{\circ}$, then $\ell_p $ has $ 2k + l$ intersection points for $l \geq 2 $. Specifically, $ l$ is the degree of the puncture $p $ in $T ^{\circ}$.

\begin{defn}

Consider the snake graph $ \mathcal{G}_{\ell_p,T^{\circ}} = (G_1, \ldots, G_{2k +l}) $ and let $$ \mathcal{H}_{\gamma, 1} := (G_1,\ldots,G_d)\setminus \{NE(G_k)\} $$ be the subgraph of $ G_{\gamma, 1} := (G_1, \ldots, G_k) $ where the North-East vertex of $ G_k $ and its incident edges $N(G_k), E(G_k)$ have been removed.

Similarly, let $$ \mathcal{H}_{\gamma, 2} := (G_{k+l+1}, \ldots ,G_{2k+l}) \setminus \{SW(G_{k+l+1})\} $$ be the subgraph of $ G_{\gamma, 2} := (G_{k+l+1},\ldots ,G_{2k+l}) $ where the South-West vertex of $ G_{k+l+1} $ and its incident edges $ S(G_{k+l+1}), W(G_{k+l+1})$ have been removed. \newline \indent

Note that $$ \mathcal{H}_{\gamma, 1} \cong \mathcal{H}_{\gamma, 2} \hspace{11mm} \text{and}  \hspace{11mm}  \mathcal{G}_{\gamma, 1}  \cong \mathcal{G}_{\gamma, 2} \cong  \mathcal{G}_{\gamma, T^{\circ}}.$$

\end{defn}

\begin{defn}

A perfect matching $ P $ of $ \mathcal{G}_{\ell_p,T^{\circ}} $ is said to be \textbf{\textit{$ \gamma $-symmetric}} if: $$ P_{\vert_{\mathcal{H}_{\gamma, 1}}}  \cong P_{\vert_{\mathcal{H}_{\gamma, 2}}} $$ with respect to the isomorphism $ \mathcal{H}_{\gamma, 1}  \cong  \mathcal{H}_{\gamma, 2} $.

\end{defn}

\begin{defn}

Let $ P $ be a $ \gamma $-symmetric perfect matching of $ \mathcal{G}_{\ell_p,T^{\circ}} $. The associated \textit{\textbf{weight monomial}} and \textit{\textbf{coefficient monomial}} are defined respectively, as follows: $$ \overline{x}(P) := \frac{x(P)}{x(P_{\vert_{\mathcal{G}_{\gamma, i}}})}  \hspace{10mm} \text{and}  \hspace{10mm} \overline{y}(P) := \frac{y(P)}{y(P_{\vert_{\mathcal{G}_{\gamma, i}}})}. $$

The index $ i \in \{1,2\} $ above is chosen such that $ P_{\vert_{\mathcal{G}_{\gamma, i}}} $ is a perfect matching of $ \mathcal{G}_{\gamma, i} $ -- this is well defined by [Lemma 12.4, \cite{musiker2011positivity}].

\end{defn}

\begin{thm}[Theorem 4.17. \cite{musiker2011positivity}]
\label{singlynotched}
Let $(S,M)$ be a bordered surface with puncture $ p $. Let $ T^{\circ} $ be an ideal triangulation with corresponding tagged triangulation $ T = \iota(T^{\circ}) $. Let $\mathcal{A} $ be the associated cluster algebra with principal coefficients with respect to $\Sigma_T = (\mathbf{x}_T,\mathbf{y}_T,B_T)$. Suppose $\gamma^{(p)}$ is a singly notched arc at $p$ whose underlying plain arc $\gamma$ is not in $T$, and that $p$ is not the puncture of a self-folded triangle in $T$. Then the Laurent expansion of $x_{\gamma^{(p)}} \in \mathcal{A}$ with respect to $\Sigma_T$ is given by:

\begin{equation}
x_{\gamma^{(p)}} = \frac{cross(\gamma,T^{\circ})}{cross(\ell_p,T^{\circ})} {\displaystyle \sum_{P} \overline{x}(P)\overline{y}(P)}
\end{equation}

\noindent where the sum is over all $ \gamma $-symmetric perfect matchings $ P $ of the snake graph $ \mathcal{G}_{\ell_p, T^{\circ}} $.

\end{thm}

\begin{prop}
\label{singlebijection}
Let $T$ be an ideal triangulation and let $ \gamma^{(p)} $ be a singly notched arc at $p$ whose underlying plain arc $ \gamma $ is not in $ T $, and suppose that $ p $ is not the puncture of a self-folded triangle in $ T $. Then there exists a bijection

\begin{align*}
 \Phi \hspace{1mm}: \hspace{2mm} &\Big\{ \stackanchor{\text{\hspace{0.5mm} $ \gamma $-symmetric perfect matchings \hspace{0.5mm}}}{\text{$P$ of $\mathcal{G}_{\ell_p, T}$}}\Big\} \hspace{5mm} \longrightarrow \hspace{5mm} \Big\{ \text{Good matchings of $\mathcal{G}_{\gamma^{(p)}, T}$}\Big\}
\end{align*}

such that $$\overline{x}(P) = x(\Phi(P)) \hspace{5mm} and \hspace{5mm} \overline{y}(P) = y(\Phi(P))$$ for all $\gamma$-symmetric perfect matchings $P$ of $\mathcal{G}_{\ell_p, T}$.

\end{prop}

\begin{proof}
Following the conventions of this section, let us write $\mathcal{G}_{\ell_p,T} = (G_1, \ldots, G_{2k +l})$. Note that $\mathcal{G}_{\gamma^{(p)}, T}$ can be obtained from $(G_1, \ldots, G_{k + l})$ by creating a loop with respect to $G_{k+l}$ and $k$, and can also be obtained from $(G_{k+1}, \ldots, G_{2k +l})$ by creating a loop with respect to $G_{2k+l}$ and $k+1$. Furthermore, note that one of the subgraphs $(G_{k-1},G_k,G_{k+1})$ and $(G_{k+l},G_{k+l+1},G_{k+l+2})$ is a zig-zag. Without loss of generality, we will suppose $(G_{k-1},G_k,G_{k+1})$ is zig-zag and that $E(G_k)$ and $S(G_k)$ are boundary edges. Finally, note that it is possible that $\ell_p$ has only $l+2$ intersections with arcs in $T$, in which case $G_{k-1} = \emptyset = G_{k+l+2}$. The proof described below works in the same way for this case too.  \newline \indent

Let $P$ be a $\gamma$-symmetric perfect matching of $\mathcal{G}_{\ell_p, T}$. From our assumptions we see that $P$ will contain one of the (boundary) edges $E(G_k)$ or $S(G_k)$. \newline

\noindent \textbf{Case 1}: $P$ involves $E(G_k)$. \newline \indent  Note that $P$ involves the edge $E(G_k)$ \textit{if and only if} $$P = E(G_k) \cup P_1 \cup P_1' \cup P_2$$ where \begin{itemize}

\item $P_1$ and $P_1'$ are perfect matchings of $(G_1,\ldots, G_{k-1})$ and $(G_{k+l+2},\ldots, G_{2k+l})$, respectively, such that $P_1 \cong P_1'$,

\item $P_2$ is a perfect matching of $(G_{k+2},\ldots, G_{k+l})$.

\end{itemize}

Similarly, a good matching $P$ of $\mathcal{G}_{\gamma^{(p)}, T} = (G_1, \ldots, G_{k + l})^{\bowtie}$ is a right or centre cut at $E(G_k)$ \textit{if and only if} $$P = P_1 \cup P_2$$ where $P_1$ is a perfect matching of $(G_1,\ldots, G_{k-1})$ and $P_2$ is a perfect matching of $(G_{k+2},\ldots, G_{k+l})$. \newline

For the second part of the proposition, recall that $\overline{x}(P) := \frac{x(P)}{x(P_{\vert_{\mathcal{G}_{\gamma,1}}})}$. Since $P_{\vert_{\mathcal{G}_{\gamma,1}}} = E(G_k) \cup P_1$ and $P_1 \cong P_1'$ then $$\overline{x}(P) = \frac{x(E(G_k))x(P_1)x(P_1')x(P_2)}{x(E(G_k))x(P_1)} = x(P_1')x(P_2) = x(P_1 \cup P_2).$$

Moreover, with respect to the $\gamma$-symmetric perfect matching $P$, a diagonal of a tile in $\mathcal{G}_{\gamma,1} := (G_1,\ldots, G_k)$ is positive \textit{if and only if} the diagonal of the corresponding tile in $\mathcal{G}_{\gamma,2} := (G_{k+l+1},\ldots, G_{2k+l})$ is positive. Hence $$\overline{y}(P) := \frac{y(P)}{y(P_{\vert_{\mathcal{G}_{\gamma,1}}})} = y(P_1\cup P_2).$$

\noindent \textbf{Case 2}: $P$ involves $S(G_k)$. \newline \indent  Analogous to above, $P$ involves the edge $S(G_k)$ \textit{if and only if} $$P = S(G_k) \cup P_1 \cup P_1' \cup P_2 \cup e_1 \cup e_2$$ where \begin{itemize}

\item $P_1$ and $P_1'$ are perfect matchings of $(G_1,\ldots, G_{k-1})\setminus E(G_{k-1})$ and $(G_{k+l+2},\ldots, G_{2k+l})\setminus b$, respectively, such that $P_1 \cong P_1'$ (here $b= W(G_{k+l+2})$ if $l$ is odd, and $b= S(G_{k+l+2})$ if $l$ is even),

\item $P_2$ is a perfect matching of $(G_{k+1},\ldots, G_{k+l-1})$.

\item $e_1 = N(G_{k+l+1})$ and $e_2 = S(G_{k+l+1})$ if $l$ is odd, and $e_1 = E(G_{k+l+1})$ and $e_2 = W(G_{k+l+1})$ if $l$ is even.

\end{itemize}

Similarly, a good matching $P$ of $\mathcal{G}_{\gamma^{(p)}, T} = (G_1, \ldots, G_{k + l})^{\bowtie}$ is a left cut at $E(G_k)$ \textit{if and only if} $$P = S(G_k) \cup P_1 \cup P_2$$ where $P_1$ is a perfect matching of $(G_1,\ldots, G_{k-1})\setminus E(G_{k-1})$ and $P_2$ is a perfect matching of $(G_{k+1},\ldots, G_{k+l-1})$. \newline

For the second part of the proposition, recall that $\overline{x}(P) := \frac{x(P)}{x(P_{\vert_{\mathcal{G}_{\gamma,2}}})}$. Since $P_{\vert_{\mathcal{G}_{\gamma,2}}} = P_1' \cup e_1 \cup e_2$ then $$\overline{x}(P) = \frac{x(S(G_k))x(P_1)x(P_1')x(P_2)x(e_1)x(e_2)}{x(P_1')x(e_1)x(e_2)} = x(S(G_k) \cup P_1 \cup P_2).$$

Moreover, as in Case 1, a diagonal of a tile in $\mathcal{G}_{\gamma,1} := (G_1,\ldots, G_k)$ is positive \textit{if and only if} the diagonal of the corresponding tile in $\mathcal{G}_{\gamma,2} := (G_{k+l+1},\ldots,G_{2k+1})$ is positive. Hence $$\overline{y}(P) := \frac{y(P)}{y(P_{\vert_{\mathcal{G}_{\gamma,2}}})} = y(S(G_k) \cup P_1\cup P_2).$$

This completes the proof as any good matching of $\mathcal{G}_{\gamma^{(p)}, T} = (G_1, \ldots, G_{k + l})^{\bowtie}$ has a right, left or centre cut at $E(G_k)$.

\end{proof}

The following observation will be helpful in the next section, where we compare good matchings and compatible pairs of $\gamma$-symmetric perfect matchings. It follows directly from the above proof.

\begin{cor}
\label{proof cor} Let $P$ be a $\gamma$-symmetric perfect matching of $\mathcal{G}_{\ell_p, T}$. With respect to the set-up described in the opening paragraph of the proof of Proposition \ref{singlebijection}, the following holds. \newline \indent

If $E(G_k) \in P$ then $P$ restricts to a perfect matching on $(G_1,\ldots, G_{k+l})$. Moreover, we get a bijection between $\gamma$-symmetric perfect matchings of $\mathcal{G}_{\ell_p,T}$ involving $E(G_k)$ and good matchings of $$\mathcal{G}_{\gamma^{(p)},T} = (G_1,\ldots, G_{k+l})^{\bowtie}$$ with right or centre cut at $E(G_k)$ via $$P \mapsto P_{\vert_{(G_1,\ldots,G_{k+l})}}\setminus E(G_k).$$

Similarly, if $S(G_k) \in P$ then $P$ restricts to a perfect matching on $(G_{k+1},\ldots, G_{2k+l})$. Moreover, we get a bijection between $\gamma$-symmetric perfect matchings of $\mathcal{G}_{\ell_p,T}$ involving $S(G_k)$ and good matchings of $$\mathcal{G}_{\gamma^{(p)},T} = (G_1,\ldots, G_{k+l})^{\bowtie} \cong (G_{k+1},\ldots, G_{2k+l})^{\bowtie}$$ with left cut at $E(G_k)$ via $$P \mapsto P_{\vert_{(G_{k+1},\ldots,G_{2k+l})}}\setminus b$$

\noindent where $b = S(G_{k+l+1})$ if $l$ is odd and $b = W(G_{k+l+1})$ if $l$ is even.

\end{cor}

\subsection{Compatible pairs of $\gamma$-symmetric perfect matchings}

\begin{defn}

Let $\gamma^{(pq)}$ be a tagged arc which is notched at puncture $p$ and $q$ (we allow $p = q$). We say $\gamma^{(pq)} $ is a \textbf{\textit{doubly notched arc}} at $p $ and $q $. We define $\ell_p$ and $\ell_q$ as in Definition \ref{singlynotched}, however, note that when $ p= q $ then $ \ell_p$ and $ \ell_q$ are not strictly arcs as they are self-intersecting. \end{defn}

\begin{defn}
\label{compatiblepair}
Let $\gamma^{(pq)} $ be a doubly notched arc and let $ P_p$ and $ P_q$ be $ \gamma $-symmetric perfect matchings of $ \mathcal{G}_{\ell_p, T^{\circ}} $ and $ \mathcal{G}_{\ell_q,  T^{\circ}} $, respectively. \newline \indent The pair $ (P_p, P_q) $ is called \textit{\textbf{$\gamma$-compatible}} if the following holds for some $ i,j \in \{1,2\}$:

\begin{itemize}

\item ${P_p}_{\vert_{\mathcal{G}_{\gamma, i}}}$ and ${P_q}_{\vert_{\mathcal{G}_{\gamma, j}}}$ are perfect matchings of $\mathcal{G}_{\gamma, i} \subset \mathcal{G}_{\ell_p, T^{\circ}}$ and $\mathcal{G}_{\gamma, j} \subset \mathcal{G}_{\ell_q, T^{\circ}}$, respectively,

\item and ${P_p}_{\vert_{\mathcal{G}_{\gamma, i}}} \cong {P_q}_{\vert_{\mathcal{G}_{\gamma, j}}}$ with respect to the canonical isomorphism $\mathcal{G}_{\gamma, i} \cong \mathcal{G}_{\gamma, j}$.

\end{itemize}

\end{defn}

\begin{defn}

Let $(P_p,P_q)$ be a $\gamma$-compatible pair of $\gamma$-symmetric perfect matchings of $(\mathcal{G}_{\ell_p,T^{\circ}},\mathcal{G}_{\ell_q,T^{\circ}})$. The associated \textit{\textbf{cluster monomial}} and \textit{\textbf{coefficient monomial}}, are defined, respectively, as follows: $$\overline{\overline{x}}(P_p ,P_q ) := \frac{x(P_p )x(P_q )}{x({P_p }_{\vert_{\mathcal{G}_{\gamma, i }}})^3} \hspace{10mm} \text{and} \hspace{10mm} \overline{\overline{y}}(P_p ,P_q ) := \frac{y(P_p )y(P_q )}{y({P_p }_{\vert_{\mathcal{G}_{\gamma, i }}})^3}.$$

Where the index $ i \in \{1,2\} $ is chosen such that $ {P_p}_{\vert_{\mathcal{G}_{\gamma, i}}} \cong { P_q}_{\vert_{\mathcal{G}_{\gamma, j }}} $ for some $ j \in \{1,2\} $, as in Definition \ref{compatiblepair}. This is well defined by [Lemma 12.4, \cite{musiker2011positivity}].

\end{defn}

\begin{thm}[Theorem 4.20, \cite{musiker2011positivity}]
\label{doublynotched}
Let $(S,M)$ be a bordered surface with punctures $p$ and $q$, that is not twice punctured and closed. Let $T^{\circ}$ be an ideal triangulation with corresponding tagged triangulation $T$. Let $\mathcal{A}$ be the associated cluster algebra with principal coefficients with respect to $\Sigma_T = (\mathbf{x}_T,\mathbf{y}_T,B_T)$. Suppose $\gamma^{(pq)}$ is a doubly notched arc at $p$ and $q$ whose underlying plain arc $\gamma$ is not in $T^{\circ}$, and that neither $p$ nor $q$ are the puncture of a self-folded triangle in $T$. Then the Laurent expansion of $x_{\gamma^{(pq)}} \in \mathcal{A}$ with respect to $\Sigma_T$ is given by:

\begin{equation}
 x_{(\gamma^{(pq)})} = \frac{cross(\gamma,T^{\circ})^3}{cross(\ell_p,T^{\circ})cross(\ell_q,T^{\circ})} {\displaystyle \sum_{(P_p,P_q)} \overline{\overline{x}}(P_p,P_q)\overline{\overline{y}}(P_p,P_q)}
\end{equation}

Where the sum is over all $\gamma$-compatible pairs of $\gamma$-symmetric perfect matchings $(P_p,P_q)$ of the pair of snake graphs $(\mathcal{G}_{\ell_p, T^{\circ}},\mathcal{G}_{\ell_q, T^{\circ}})$.

\end{thm}

\begin{prop}
\label{doublebijection}
Let $T$ be an ideal triangulation and let $\gamma^{(pq)}$ be a doubly notched arc at $p$ and $q$ whose underlying plain arc $\gamma$ is not in $T$. Furthermore, suppose that neither $p$ nor $q$ are the puncture of a self-folded triangle in $T$. Then there exists a bijection

\begin{align*}
 \Phi \hspace{1mm}: \hspace{2mm} &\Bigg\{ \substack{\text{ \normalsize $\gamma$-compatible pairs of $\gamma$-symmetric} \\ \text{ \normalsize perfect matchings $(P_p,P_q)$}\\ \text{ \normalsize of $(\mathcal{G}_{\ell_p, T},\mathcal{G}_{\ell_p, T})$}}\Bigg\} \hspace{5mm} \longrightarrow \hspace{5mm} \Big\{ \text{Good matchings of $\mathcal{G}_{\gamma^{(pq)}, T}$}\Big\}
\end{align*}

such that $$\overline{\overline{x}}(P_p,P_q) = x(\Phi(P_p,P_q)) \hspace{5mm} and \hspace{5mm} \overline{\overline{y}}(P_p,P_q) = y(\Phi(P_p,P_q))$$ for all $\gamma$-compatible pairs of $\gamma$-symmetric perfect matchings $(P_p,P_q)$ of $(\mathcal{G}_{\ell_p, T},\mathcal{G}_{\ell_p, T})$.

\end{prop}

\begin{proof}

Let us write $\mathcal{G}_{\ell_p,T} = (G_1, \ldots, G_{2k +l_p})$ and $\mathcal{G}_{\ell_q,T} = (H_1, \ldots, H_{2k + l_q})$. Furthermore, following the same reasoning used in the proof of Proposition \ref{singlebijection}, without loss of generality we will suppose both $(G_{k-1},G_k,G_{k+1})$ and $(H_{k-1},H_k,H_{k+1})$ are zig-zag and that $E(G_k)$,$S(G_k)$,$E(H_k)$,$S(H_k)$ are boundary edges.

The collection of all $\gamma$-compatible pairs of $\gamma$-symmetric perfect matchings $(P_p,P_q)$ can be decomposed into the disjoint union of the following four classes: \begin{enumerate}

\item $E(G_k) \in P_p$ and $E(H_k) \in P_q$.

\item $S(G_k) \in P_p$ and $E(H_k) \in P_q$.

\item $E(G_k) \in P_p$ and $S(H_k) \in P_q$.

\item $S(G_k) \in P_p$ and $S(H_k) \in P_q$.

\end{enumerate}

For each class there exist $i,j \in \{1,2\}$ such that $P_p$ and $P_q$ restrict to perfect matchings on $\mathcal{G}_{\gamma,i} \subset \mathcal{G}_{\ell_p,T}$ and $\mathcal{G}_{\gamma,j} \subset \mathcal{G}_{\ell_q,T}$, respectively, for all $(P_p,P_q)$ in the chosen class. Moreover, by definition of $\gamma$-compatibility, these restrictions are isomorphic with respect to the isomorphism $\mathcal{G}_{\gamma,i} \cong \mathcal{G}_{\gamma,j}$.

This means that $P_p$ and $P_q$ can be glued along $\mathcal{G}_{\gamma,i}$ and $\mathcal{G}_{\gamma,j}$. Applying Corollary \ref{proof cor}, for each of the four classes above, we get a bijection between the following classes of good matchings $P$ of $\mathcal{G}_{\gamma,T}$:

\begin{enumerate}

\item $P$ has a right or centre cut with respect to $E(G_k)$ and a right or centre cut with respect to $E(H_k)$.

\item $P$ has a left cut with respect to $E(G_k)$ and a right or centre cut with respect to $E(H_k)$.

\item $P$ has a right or centre cut with respect to $E(G_k)$ and a left cut with respect to $E(H_k)$.

\item $P$ has a left cut with respect to $E(G_k)$ and a left cut with respect to $E(H_k)$.

Finally, coupling this with Proposition \ref{singlebijection}, the bijection $(P_p,P_q) \mapsto P$ described above satisfies $$\overline{\overline{x}}(P_p,P_q) = x(P) \hspace{10mm} \text{and} \hspace{10mm} \overline{\overline{y}}(P_p,P_q) = y(P).$$

\end{enumerate}

\end{proof}

We now conclude the section with a proof of the Main Theorem \ref{loopexpansion}.

\begin{proof}[Proof of Theorem \ref{loopexpansion}]

When $\gamma$ is a plain arc then $\mathcal{G}_{\gamma,T}$ is just a snake graph and equation (\ref{loopexpansionformula}) reduces to [Theorem 4.10. \cite{musiker2011positivity}].

When $\gamma = \gamma^{(p)}$ is a singly notched arc then equation (\ref{loopexpansionformula}) follows from Theorem \ref{singlynotched}, Proposition \ref{singlebijection} and the equality $$cross(\gamma^{(p)},T^{\circ}) = \frac{cross(\ell_p,T^{\circ})}{cross(\gamma^{\circ},T^{\circ})}.$$

Finally, when $\gamma = \gamma^{(pq)}$ is a doubly notched arc then equation (\ref{loopexpansionformula}) follows from Theorem \ref{doublynotched}, Proposition \ref{doublebijection} and the equality $$cross(\gamma^{(pq)},T) = \frac{cross(\ell_p,T^{\circ})cross(\ell_q,T^{\circ})}{cross(\gamma^{\circ},T^{\circ})^3}.$$

\end{proof}

\section{The lattice structure of good matchings of loop graphs}

In this section we discuss some properties of surface loop graphs. It builds on the work of Musiker, Schiffler, Williams established for snake graphs in [Section 5, \cite{musiker2013bases}]. We shall assume throughout that the first tile of any loop graph has relative orientation $1$.

\begin{defn}

Let $P$ be a good matching of a loop graph $\mathcal{G}^{\bowtie} = (G_1 \ldots, G_d)^{\bowtie}$. We say a good matching $P'$ of $\mathcal{G}^{\bowtie}$ is obtained from $P$ by a \textit{\textbf{positive twist}} at tile $G_j$ if one of the following holds:

\begin{itemize}

\item $P \setminus \{N(G_j),S(G_j)\} = P' \setminus \{W(G_j),E(G_j)\}$ and $j$ is odd, or

\item $P \setminus \{W(G_j),E(G_j)\} = P' \setminus \{N(G_j),S(G_j)\}$ and $j$ is even.

\end{itemize}

\end{defn}

\begin{defn}

Let $\mathcal{G}^{\bowtie}$ be a loop graph. We define the \textbf{\textit{lattice of good matchings}} of $\mathcal{G}^{\bowtie}$ to be the quiver $L(\mathcal{G}^{\bowtie})$ whose vertices are good matchings of $\mathcal{G}^{\bowtie}$. Moreover, there is an arrow $P \rightarrow P'$ in $L(\mathcal{G}^{\bowtie})$ \textit{if and only if} $P'$ is obtained from $P$ by a positive twist.

\end{defn}

\begin{defn}
\label{snake quiver}
Let $\mathcal{G} = (G_1, \ldots, G_d)$ be a snake graph. We define $Q_{\mathcal{G}}$ to be the quiver with vertices $\{1, \ldots, d\}$ and whose arrows are determined by the following rules:

\begin{itemize}

\item there is an arrow $i \rightarrow i+1$ in $Q_{\mathcal{G}}$ \textit{if and only if} $i$ is odd and $G_{i+1}$ is on the right of $G_i$, or $i$ is even and $G_{i+1}$ is on top $G_i$,

\item there is an arrow $i \rightarrow i-1$ in $Q_{\mathcal{G}}$ \textit{if and only if} $i$ is odd and $G_{i}$ is on the right of $G_{i-1}$, or $i$ is even and $G_{i}$ is on top of $G_{i-1}$.

\end{itemize}

$Q_{\mathcal{G}}$ induces a poset structure on $\{1,\ldots, d\}$ by setting $i \leq j$ \textit{if and only if} $i = j$ or there is a sequence of arrows in $Q_{\mathcal{G}}$ oriented from $i$ to $j$. Namely, $Q_{\mathcal{G}}$ is the Hasse diagram of this poset.

\end{defn}

\begin{defn}

We say $I \subseteq Q$ is an \textit{\textbf{order ideal}} of a poset $(Q, \leq)$ if whenever $x \in I$ and $y \in Q$ satisfy $y \leq x$, then $y \in I$.

\end{defn}

\begin{defn}

Let $P$ be a good matching of a loop graph $\mathcal{G}^{\bowtie} = (G_1, \ldots, G_d)^{\bowtie}$. We define the \textit{\textbf{height}} to be the set $h(P) \subseteq \{1,\ldots, d\}$ where $ i \in h(P)$ \textit{if and only if} the diagonal of $G_i$ is positive with respect to $P$.

\end{defn}

\begin{thm}[Theorem 5.4, \cite{musiker2013bases}]
\label{order lattice}
Let $\mathcal{G}$ be a snake graph. Then $L(\mathcal{G})$ is isomorphic to the lattice of order ideals $\mathcal{J}(Q_{\mathcal{G}})$ of the poset $Q_{\mathcal{G}}$. Specifically, this isomorphism is given by sending a perfect matching $P$ to its height $h(P)$.

\end{thm}

\begin{defn}

Let $\mathcal{G}^{\bowtie} = (G_1, \ldots, G_d)^{\bowtie}$ be a loop graph with underlying snake graph $\mathcal{G} = (G_1, \ldots, G_d)$. We define the quiver $Q_{\mathcal{G}^{\bowtie}}$ of $\mathcal{G}^{\bowtie}$ to be the quiver $Q_{\mathcal{G}}$ with an additional arrow for each loop of $\mathcal{G}^{\bowtie}$. Specifically, this arrow is determined by the following rule:

\begin{itemize}

\item if there is a loop with respect to $G_1$ and $k \in \{2, \ldots, d\}$ then the arrow $1 \rightarrow k$ (resp. $k \rightarrow 1$) is in $Q_{\mathcal{G}^{\bowtie}}$ \textit{if and only if} $k$ is odd (resp. even) and $S(G_k)$ is the cut edge, or $k$ is even (resp. odd) and $W(G_k)$ is the cut edge.

\item if there is a loop with respect to $G_d$ and $k \in \{1, \ldots, d-1\}$ then the arrow $d \rightarrow k$ (resp. $k \rightarrow d$) is in $Q_{\mathcal{G}^{\bowtie}}$ \textit{if and only if} $k$ is odd (resp. even) and $N(G_k)$ is the cut edge, or $k$ is even (resp. odd) and $E(G_k)$ is the cut edge.

\end{itemize}

\end{defn}

\begin{lem}

Let $\mathcal{G}^{\bowtie} = (G_1, \ldots, G_d)^{\bowtie}$ be a surface loop graph. Then $Q_{\mathcal{G}^{\bowtie}}$ defines a well-defined poset structure on $\{1,\ldots, d\}$ by setting $i \leq j$ \textit{if and only if} $i = j$ or there is a sequence of arrows in $Q_{\mathcal{G}}$ oriented from $i$ to $j$.

\end{lem}

\begin{proof}

Suppose there is a loop with respect to $G_1$ and $k \in \{3,\ldots, d\}$. Since $\mathcal{G}^{\bowtie}$ is a surface loop graph then $(G_{k-2},G_{k-1},G_k)$ and $(G_{d-1},G_{d},G_k)$ are straight subgraphs of $\mathcal{G}^{\bowtie}$. An analogous statement holds if there a loop with respect to $G_d$ and $k \in \{1,\ldots, d-2\}$. Consequently, the poset structure is well defined.

\end{proof}

\begin{figure}[H]
\begin{center}
\includegraphics[width=15cm]{singlehasse.pdf}
\caption{The associated quivers, shown in red, of the loop graphs found in Figures \ref{single} and \ref{double}.}
\label{hasse}
\end{center}
\end{figure}

We are now ready to state the main theorem of this section.

\begin{thm}
\label{loop order lattice}

Let $\mathcal{G}^{\bowtie}$ be a surface loop graph. Then $L(\mathcal{G}^{\bowtie})$ is isomorphic to the lattice of order ideals $\mathcal{J}(Q_{\mathcal{G}^{\bowtie}})$ of the poset $Q_{\mathcal{G}^{\bowtie}}$. Specifically, this isomorphism is given by sending a good matching $P$ to its height $h(P)$.

\end{thm}

\begin{proof}

Let us consider the case when $\mathcal{G}^{\bowtie}$ arises from a singly notched arc. Moreover, let $\mathcal{G} = (G_1,\ldots, G_k, \ldots, G_d)$ be a snake graph which gives rise to $\mathcal{G}^{\bowtie}$ by creating a loop with respect to $G_1$ and $k$. Without loss of generality, we may assume that $G_2$ is on the right of the tile $G_1$, and that $(G_{k-1},G_k,G_{k+1})$ is a zig-zag (we allow the possibility that $G_{k+1} = \emptyset$) -- see Figure \ref{latticesetup}. \newline \indent

If $\overline{P}$ is a perfect matching of $\mathcal{G}$ that induces a negative diagonal on tile $G_k$ then the edge matching $x'$ and $y'$ is in $\overline{P}$. So $\overline{P}$ descends to a good matching on $\mathcal{G}^{\bowtie}$. \newline \indent Conversely, If $\overline{P}$ is a perfect matching of $\mathcal{G}$ that induces a positive diagonal on tile $G_k$ then: $N(G_k) \in \overline{P}$ or $E(G_k) \in \overline{P}$, respective of whether $k$ is even or odd. So $\overline{P}$ descends to a good matching of $\mathcal{G}^{\bowtie}$ \textit{if and only if} the edge matching $x$ and $y$ is in $\overline{P}$. Consequently, the diagonal of $G_1$ must also be positive. \newline \indent

Therefore, by Theorem \ref{order lattice}, the collection of good matchings of $\mathcal{G}_{\gamma,T}$ may be identified with the order ideals of $Q_{\mathcal{G}}$ which include the vertex $1$ whenever they contain the vertex $k$. This subcollection of order ideals is precisely the order ideals of $Q_{\mathcal{G}^{\bowtie}}$, which completes the proof when $\mathcal{G}^{\bowtie}$ arises from a singly-notched arc. The doubly-notched case follows in exactly the same way.

\end{proof}

\begin{figure}[H]
\begin{center}
\includegraphics[width=14cm]{latticesetup.pdf}
\caption{The setup of the loop graph $\mathcal{G}^{\bowtie}$ discussed in the proof of Theorem \ref{loop order lattice}. The red quiver indicates (part of) the associated quiver $Q_{\mathcal{G}^{\bowtie}}$.}
\label{latticesetup}
\end{center}
\end{figure}

\begin{cor}

Let $\mathcal{G}^{\bowtie}$ be a surface loop graph. Then there exist (unique) good matchings $P_-$ and $P_+$ of $\mathcal{G}^{\bowtie}$ for which the diagonals of $\mathcal{G}^{\bowtie}$ are all negative and all positive, respectively. We call these the \textbf{\textit{minimal}} and \textbf{\textit{maximal}} good matchings of $\mathcal{G}^{\bowtie}$.

\end{cor}

\begin{proof}

Note that $\emptyset$ and $\{1,\ldots, d\}$ are order ideals of $Q_{\mathcal{G}^{\bowtie}} = (G_1, \ldots, G_d)^{\bowtie}$. By Theorem \ref{loop order lattice} there exist good matchings $P_-$ and $P_+$ of $\mathcal{G}^{\bowtie}$ such that $h(P_-) = \emptyset$ and $h(P_+) = \{1,\ldots, d\}$.

\end{proof}

\begin{rmk}

Let $\mathcal{G}^{\bowtie}$ be a loop graph. One can associate a quiver representation $M(I)$ of $Q_{\mathcal{G}^{\bowtie}}$ to each order ideal $I$ of $Q_{\mathcal{G}^{\bowtie}}$. Specifically, $$M(i) = \mathbb{C} \hspace{4mm} \textit{if and only if} \hspace{4mm} i \notin I$$ and for each arrow $\alpha: i \rightarrow j$ in $Q_{\mathcal{G}^{\bowtie}}$ we have $$M(\alpha) = Id, \hspace{2mm} \text{if} \hspace{2mm} i,j \notin I \hspace{6mm} \text{and} \hspace{6mm} M(\alpha) = 0, \hspace{3mm} \text{otherwise}.$$ Adopting the terminology used in \cite{canakci2018lattice}, we see from Theorem \ref{loop order lattice} that $L(\mathcal{G}^{\bowtie})$ is isomorphic to the \textit{canonical} submodule lattice of $M(\emptyset)$, with respect to $Q_{\mathcal{G}^{\bowtie}}$, for any surface loop graph $\mathcal{G}^{\bowtie}$. Note that our situation is dual to that presented in \cite{canakci2018lattice}, so the ordering on the canonical submodule lattice is defined by $M(I) \leq M(J)$ \textit{if and only if} $M(J)$ is a submodule of $M(I)$.
\end{rmk}

\bibliography{bases}
\bibliographystyle{plain}

\Addresses

\end{document}


TITLE: Show that there is only one positive integer k such that no graph contains exactly k spanning trees.
QUESTION [3 upvotes]: Show that there is only one positive integer k such that no graph contains exactly k spanning trees.
I feel that k is 2. And we can show by induction that it is true for $k >= 3 $.
But I am unable to do it.

REPLY [2 votes]: By graph we mean a connected undirected graph.

Look at the $k$-th regular polygon, $k \ge 3$. It has $k$ nodes and $k$ edges, its spanning tree is all the edges minus one. It has exactly $k$ spanning trees.
Adding some edges and nodes to a graph won't reduce its number of spanning trees.
A graph has exactly one spanning tree iff it is a tree (un-cyclic), otherwise it has a cycle of length $k \ge 3$, and by the preceding, it has at least $k$ spanning trees.

REPLY [1 votes]: Hint. As regards the existence of a graph with exactly $k\geq 3$ spanning trees, consider the Pan Graphs or the Sunlet  Graphs (Cycle Graphs are already mentioned in user1952009's answer).
For the case $k=2$ see here: Prove graph cannot have exactly two distinct spanning trees


TITLE: Books on functional equations
QUESTION [6 upvotes]: Could you help me please with some functional equations? I need some online books with exercises and some explanations. I'm interested in the Cauchy functional equation and Jensen functional equation.

REPLY [1 votes]: I think mathlink is the best one. Usually, books about functional equations include old problems only(some of them doesn't even include problems made in 21th century...) But if you search 'functional equation' on Forum(which is in the 'Community' section), there are a lot of challenging problems, and you might see tons of amazing techniques in FE!!!
Here's the link : https://artofproblemsolving.com/


TITLE: An Elementary Approach to How Many Singular Points a Curve Can Have
QUESTION [2 upvotes]: Consider an irreducible plane curve, $C \subseteq A^{2}_{\mathbb{C}}$. Prove that C has only finitely many singular points.
My idea is to consider the subset $S$ that contains the singular points of C. Then we would want to show that it is a closed subset--but I do not see where to go from here. Could someone help, with elementary methods?

REPLY [6 votes]: Hint: The singular points should satisfy some equation, and so should be Zariski closed. That means they are either everything or finite (why?). But, they can't be everything (why?).


TITLE: Identifying a Hopf algebra cohomology theory
QUESTION [13 upvotes]: Here is a cohomology theory for a Hopf algebra, which I am sure has appeared elsewhere. I met it in the van Est spectral sequence for Hopf algebras. Apologies for my being stupid here, but it would be really helpful if someone would tell me where it comes from, and where to look for results on it!
Let $H$ be a Hopf algebra and $\lambda: F\to H\otimes
F$ be a left $H$-comodule, which we write in Sweedler notation $\lambda(f)=f_{[-1]}\otimes f_{[0]}$.
Define $D^{n}=H^{\otimes n+1}\otimes F$ for $n\ge 0$, with
the tensor product left $H$-coaction.  The differential $ d:D^{n}\to D^{n+1}$ with $ d^2=0$ is defined by
      $$
       d(h_{0}\otimes\ldots\otimes h_{n}\otimes f)\,=\, \sum_{n+1\ge i\ge
      0}(-1)^{i}\, h_{0}\otimes\ldots\otimes h_{i-1}\otimes 1_H \otimes
      h_{i}\otimes\ldots \otimes h_{n}\otimes f\ .
      $$
As $ d$ is a left $H$-comodule map, we can restrict the complex to the invariants to give $({}^{coH}D^{n}, d)$, and the cohomology of the invariants is what I am looking for. The invariants are taken over the tensor product coaction on all factors. There is an explicit reformulation of the cohomology without taking invariants, and seemingly without requiring an algebra structure, though showing an isomorphism is awkward, and does require Hopf algebra structure:
Define a cochain complex
$(G^{*},\bar d )$ by $G^{n}=H^{\otimes n}\otimes F$ for $n\ge 0$ with
 $\bar d  f=1_{H}\otimes f-\lambda(f)$ for $f\in F$ and
\begin{eqnarray*}
      \bar d (h_{1}\otimes\dots\otimes h_{n}\otimes f) &=& 1_{H}\otimes
h_{1}\otimes\dots\otimes h_{n}\otimes f\,-\, \Delta(h_{1})\otimes\dots\otimes
h_{n}\otimes f\,+\,\dots \cr &&+\,(-1)^{n}\,h_{1}\otimes\dots\otimes
\Delta(h_{n})\otimes f\,-\, (-1)^{n}\,h_{1}\otimes\dots\otimes h_{n}\otimes
\lambda(f)\ .
\end{eqnarray*}
I guess that the comment below on the dependence on a coalgebra structure is then correct...

REPLY [8 votes]: Looks to me as if you have not used the product of your Hopf algebra, and it looks to me that you have written an example of a cotorsion product, as defined by Eilenberg and Moore in their paper Homology and fibrations I. Coalgebras, cotensor product and its derived functors. Comm. Math. Hel. 40(1965), 199--236, available here:
http://retro.seals.ch/digbib/view?rid=comahe-002:1965-1966:40::223


TITLE: Proof of $f^{-1}(A) \cap f^{-1}(B)= f^{-1}(A \cap B)$
QUESTION [1 upvotes]: First let me say I am aware of the other threads on this result. The reason for me making this thread is to find out whether or not my proof/proof attempt is correct.
The problem stated in full detail is given below.

Let $X,Y$ be sets and $f:X \rightarrow Y$, let $C,D \subseteq X$ and let $A,B \subseteq Y$. Prove that $f^{-1}(A) \cap f^{-1}(B)= f^{-1}(A \cap B)$.

Here is my attempt:
$f^{-1}(A) \cap f^{-1}(B)= { \{x\in X \mid f(x) \in A\}}\cap { \{x\in X \mid f(x) \in B\}}= \{x\in X \mid f(x) \in A\wedge f(x) \in B\}= \{x\in X \mid f(x) \in A\cap B \}=f^{-1}(A \cap B)$
If anyone would be kind enough to explain to me where I've gone wrong or made an unjustified assumption I would be very grateful!
P.S. Sorry about the bad formating

REPLY [3 votes]: Your proof seems perfectly OK to me.
If you aren't sure because the set notation is confusing you, maybe rewriting it without so many sets would also work:
$$\begin{align}x\in f^{-1}(A)\cap f^{-1}(B)\iff &(x\in f^{-1}(A)\land x\in f^{-1}(B)\\\iff& f(x)\in A\land f(x)\in B\\\iff& f(x)\in A\cap B\\\iff& x\in f^{-1}(A\cap B)\end{align}$$

REPLY [1 votes]: Your proof is fine ! Everything is correct.


TITLE: What is the best book for coordinate geometry?
QUESTION [0 upvotes]: Requirements:

A) not too thick, as I am reading this only to solve calculus problem.
B) free on web is the best (optional)
C) I don't mind if the book involves both coordinate geometry and analytical geometry.

Any suggestion? Thanks

REPLY [0 votes]: I will recommend Precalculus Mathematics in a Nutshell: Geometry, Algebra, Trigonometry
by George F. Simmons. It has coordinate geometry as well.


TITLE: Removing a hypothesis when generalizing the Lebesgue measure
QUESTION [1 upvotes]: Let $f:\mathbb R\to\mathbb R$ be a continuous increasing function. Define the (generalized) length of (finite) semiopen intervals,
$$
\begin{align}
\lambda_f:&\{[a,b):a,b\in\mathbb R\,;\;a\leq b\}\to[0,\infty),\\
&[a,b) \mapsto f(b)-f(a).
\end{align}
$$
Define also
$$
\begin{align}\theta^*_f:&\mathcal P(\mathbb R)\to[0,\infty],\\
&A\mapsto\inf\,\left\{\sum_{k\in\mathbb N}\,\lambda_f([a_k,b_k)):A\subset\bigcup_{k\in\mathbb N}[a_k,b_k)\right\},
\end{align}
$$
which can be shown to be an outer measure. (Therefore, with $\theta^*_f$, Carathéodory's method generates the measure $\mu_f$, the Lebesgue-Stieltjes measure.)
What changes in this rationale if we no longer assume $f$ has to be continuous?

REPLY [3 votes]: Note that, since $f$ is increasing, this already implies that it has finite one-sided limits in any real point. Of course, this does not imply continuity, but in order to eventually get a measure which is defined and finite on all intervals $[a,b)$, $f$ must at least be right-continuous. Indeed, if $\mu$ is a measure on the real line assigning finite value to every interval of this form, then $\mu ([a,b)) = \lim_{n \to \infty} \mu ([a,b+h_n))$ for any sequence $h_n > 0$ decreasing to $0$ (because $[a,b] = \bigcap_{n \in \mathbb{N}} [a,b+h_n)$ and $\mu(\{b\})=0\!$ ).
To apply Carathéodory's method, you need that the measure be a priori $\sigma$-additive on intervals of such form (in the case that their union is also of this form). The above illustrates that this won't be true if $f$ isn't right continuous. However, it turns out that right continuity (along with the monotonicity requirement) is enough in order to get a Borel measure using Carathéodory's method. This is simply because in this case we avoid the former obstruction and this is indeed the only one — Carathéodory's method then generally extends the measure to the smallest $\sigma$-algebra generated by such intervals, which is the Borel algebra.


TITLE: Convolution of $L^1 \cap L^q$ and $L^2 \cap L^{\infty}$
QUESTION [0 upvotes]: This is not from assignment, something on my notes.
With $f \in L^1 \cap L^q$ for a $q > \frac{3}{2}$ and we take its convolution $u = \frac{1}{4 \pi|x|} * f$, we can show that $u$ is in $L^p \cap L^\infty$ for all $p > 3$.
My attempt was: We know that $\frac{1}{4\pi|x|} = (\frac{1}{4\pi^2 |\xi|^2})^\vee$  ($\vee$ means inverse fourier transformation). Since $\frac{1}{4\pi^2 |\xi|^2}$ is in $L^1 \cap L^2$,  $\frac{1}{4\pi|x|} \in L^2 + L^\infty$. Write $\frac{1}{4\pi|x|} = G_1 + G_2$, where $G_1 \in L^2$ and $G_2 \in L^\infty$. Then we consider $G_1*f$ and $G_2*F$ separately, and use generalized Young's inequality. However I am only able to prove that $u \in L^p + L^\infty$ this way, which is not what is wanted.

REPLY [1 votes]: The shorter proof would be using Lorentz spaces and since $\frac{1}{|x|}\in L^{3,\infty}$ and since $f\in L^1\cap L^{q} \subset L^{3/2,1}$ by interpolation, you deduce that $\frac{1}{|x|}*f\in L^\infty$ since the dual of $L^{3,\infty}$ is $L^{3/2,1}$. On the other hand, since $f\in L^r$ for any $r\in(1,3/2)$, by the Hardy$\unicode{x2013}$Littlewood$\unicode{x2013}$Sobolev's inequality
$$
\|\frac{1}{|x|}*f\|_{L^p} \leq C \|f\|_{L^r}
$$
with $\frac{1}{p} = \frac{1}{r} - \frac{2}{3}$, and $r>1$ is equivalent to $p>3$.

Then as you say, a longer but more elementary proof can be obtained by cutting the functions. You can write $\frac{1}{|x|}$ as a sum in $L^2+L^\infty$, and more explicitly
$$
\frac{1}{|x|} = \frac{1}{|x|} \,\mathbf{1}_{|x|<1} + \frac{1}{|x|} \,\mathbf{1}_{|x|\geq 1} = G_1+G_2 \in (L^1\cap L^{3-\epsilon}) + (L^\infty\cap L^{3+\epsilon})
$$
Then again you have to prove separately that $f\in L^\infty$, and then that $f\in L^p$.

$G_1*f\in L^\infty$ by Young's inequality (actually Hölder's inequality in this case) because the Hölder conjugate of $q$ verifies $q'<3/2$, so $G_1\in L^{q'}$ and $f\in L^{q}$.
$G_2*f\in L^\infty$ because $G_2\in L^\infty$ and $f\in L^1$.

So $\frac{1}{|x|}*f \in L^\infty$.

$G_1*f\in L^p$ because $G_1\in L^1$ and $f\in L^p$.
$G_2*f\in L^p$ because $G_2\in L^{3+\epsilon}$ and $f\in L^1$.

So $\frac{1}{|x|}*f \in L^p$ with $p>3$.


text:
\section{Proof of Theorem~\ref{th:consistency}}
\label{appendix:Proof_Th2}

The consistency of our proposed estimators is tied to the approximation power of the neural network, which is addressed in the following lemma.

\begin{lemma}
	\label{Lemma:functiona_apprx}
	For a given $\epsilon>0$, $\exists\, \tilde\theta\in\Theta$ such that $\Theta\subset \mathbb{R}^h$ is compact and
	$$\abs{L(\omega_{\tilde\theta})-L^*}\leq \frac{\epsilon}{2}.$$
	\begin{proof}
		The proof can be shown similar to \cite[Lemma~4]{mukherjee2019ccmi_conf}.
	\end{proof}
\end{lemma}

\begin{remark}
	The universal functional approximation introduced in \cite{hornik1989multilayer} allows choosing parameters in a compact set of $\mathbb{R}^h$, while $\epsilon$ determines the number of neurons, and accordingly $h$, such that the desired approximation is achieved.
	Consider the network is approximating the function $\omega^*$; then, given $\epsilon>0$, there exist a set $\Theta$ and a parameter $\tilde{\theta}\in\Theta$ such that $\omega_{\tilde{\theta}}$ is at an $\epsilon$ distance of $\omega^*$.
\end{remark}

Adopting an optimizer such as \textit{Adam}, we can minimize $L_{\emp}(\omega_\theta)$ to find $\hat\theta$, and it is desired that $L(\omega_{\hat{\theta}})$ is close to $L^*$, which suggests we can use the neural network to approximate $\omega^*$.
As shown in Proposition~\ref{Prop:convergence_L}, given a particular $\theta\in\Theta$, one can choose $n$ such that $L_{\emp}(\omega_\theta)$ falls in a the neighborhood of $L(\omega_\theta)$.
Nevertheless, we need a more restrictive condition if we want to guarantee such convergence for all $\theta$ simultaneously.
This is addressed in the lemma below.

\begin{lemma}\label{Lemma:convergence_Sup_L}
	Let Assumptions~\ref{Assum:knn} and \ref{Assum:NN_Lip} hold, then for any $\mu>0$, there exists $n_1$ such that, for $n>n_1$, we have that
	\begin{equation}
	\pr{\sup_{\theta\in \Theta} \abs{L_{\emp}(\omega_\theta)-L(\omega_\theta)}>2\mu} \leq \mdel{4}(\mu),
	\label{eq:lemma_covering}
	\end{equation}
	where $\mdel{4}$ is defined in Table~\ref{tab:param}.

	\begin{proof}
		The proof follows similar steps as the one for~\cite[Lemma~5]{mukherjee2019ccmi_conf} and we provide here only some details.

		Since $\Theta\subset \mathbb{R}^h$ and $\vnorm{\theta}_2\leq K$, $\forall\theta\in\Theta$, $\Theta$ can be covered with $N(\Theta,r)$ number of balls of radius $r$---the covering number with respect to $\ell_2$.
		The covering number is finite and bounded \cite{shalev2014understanding}:
			\begin{align}\label{eq:covering_bound}
			N(\Theta,r)\leq \bigg( \frac{2K\sqrt{h}}{r} \bigg)^h.
			\end{align}

		Let $\{ \theta_1, \dots, \theta_{N(\Theta,r)} \}$ denote the centers of the covering balls and $\{ \Theta_1, \dots, \Theta_{N(\Theta,r)} \}$, the corresponding balls.

		We may then use the union bound on the LHS of~\eqref{eq:lemma_covering} and take the supremum inside each ball $\Theta_j$.
		By the triangle inequality, for any $\theta\in\Theta$, $\forall j$, and with probability at least $1-\mdel{4}(\mu)$:
		\begin{align}
		\MoveEqLeft[2]
		\abs{L_{\emp}(\omega_\theta)-L(\omega_\theta)} \nonumber\\
		&\leq \abs{L_{\emp}(\omega_\theta)-L_{\emp}(\omega_{\theta_j})} + \abs{L_{\emp}(\omega_{\theta_j}) - L(\omega_{\theta_j})} \nonumber\\
		&\quad + \abs{L(\omega_{\theta_j}) - L(\omega_\theta)} \nonumber\\
		&\leq \frac{Br}{\tau} +\mu +\frac{Br}{\tau},
		\end{align}

		where the last step follows from Lipschitz continuity of $\log(\cdot)$ and $\omega_{\theta}$ according to Assumption~\ref{Assum:NN_Lip}, and using Proposition~\ref{Prop:convergence_L}.
		Finally, choosing $r=\frac{\tau\mu}{2B}$ concludes the proof.
	\end{proof}
\end{lemma}

The following proposition shows the convergence of $L(\omega_{\hat\theta})$.

\begin{proposition}\label{Prop:L_Ls}
	Let Assumptions~\ref{Assum:knn} and \ref{Assum:NN_Lip} hold. Given $\epsilon>0$, there exists an integer $n_1$ such that, for $n>n_1$,
	\begin{align}
	\pr{L(\omega_{\hat\theta})- L^*\geq \epsilon}\leq \mdel{4}\!\left(\frac{\epsilon}{8}\right).
	\end{align}

	\begin{proof}
		From Lemma~\ref{Lemma:convergence_Sup_L}, with probability at least $1-\mdel{4}(\mu)$, we have that
		\begin{align}
		\abs{L_{\emp}(\omega_{\tilde\theta})-L(\omega_{\tilde\theta})}\leq 2\mu\
		\textnormal{ and }\
		\abs{L_{\emp}(\omega_{\hat\theta})-L(\omega_{\hat\theta})}\leq 2\mu.\label{eq:L2b_conv}
		\end{align}

		Since $\hat\theta$ minimizes $L_{\emp}(\omega_\theta)$, by choosing $\mu=\frac{\epsilon}{8}$, we obtain:
		\begin{align}
		L(\omega_{\hat\theta})&\leq L_{\emp}(\omega_{\hat\theta})+\frac{\epsilon}{4}\leq L_{\emp}(\omega_{\tilde\theta})+\frac{\epsilon}{4}\nonumber\\
		&\stackrel{(a)}{\leq} L(\omega_{\tilde\theta}) + \frac{\epsilon}{2} \stackrel{(b)}{\leq} L^* + \epsilon,\label{eq:L_vicin}
		\end{align}
		where the steps $(a)$ and $(b)$ are due to \eqref{eq:L2b_conv} and Lemma~\ref{Lemma:functiona_apprx}, respectively.
	\end{proof}
\end{proposition}

Proposition~\ref{Prop:L_Ls} implies that $L(\omega_{\hat\theta})$ is close to $L^*$ and, due to the strong convexity of the cross-entropy loss, it can be shown that $\omega_{\hat{\theta}}$ is close to $\omega^*$ (in $\ell_1$ norm).
We continue the proof of the Theorem by defining the following terms:
\begin{align}
I_{\DV}^{\hat\theta} &\coloneqq \ex_{p(x,y,z)} \big[ \log \hat\Gamma(X,Y,Z) \big]\nonumber\\
&\hspace{1.7cm}- \log \ex_{p(x|z)p(y,z)} \big[ \hat\Gamma(X,Y,Z) \big], \nonumber\\

I_{\NWJ}^{\hat\theta} &\coloneqq 1 + \ex_{p(x,y,z)} \big[ \log \hat\Gamma(X,Y,Z) \big] \nonumber\\
&\hspace{1.7cm}- \ex_{p(x|z)p(y,z)} \big[ \hat\Gamma(X,Y,Z) \big], \nonumber\\

I_{\LDR}^{\hat\theta}&\coloneqq \ex_{p(x,y,z)} \big[ \log \hat\Gamma(X,Y,Z) \big],
\label{eq:expected_I_theta_hat}
\end{align}
where $\hat\Gamma(\cdot)$ is defined in \eqref{eq:Gamma_hat}.
Then from the triangle inequality, we have that
\begin{align}\label{eq:convergence_split}
\Big| \hat I_{\mathtt{est}}^{n,\hat\theta} - I(X;Y|Z) \Big| &\leq \Big| \hat I_{\mathtt{est}}^{n,\hat\theta} - I_{\mathtt{est}}^{\hat\theta} \Big| + \Big| I_{\mathtt{est}}^{\hat\theta}- I(X;Y|Z) \Big|,
\end{align}
where `$\mathtt{est}$' can be replaced with `$\DV$', `$\NWJ$', or `$\LDR$'.
In the following, we show high-confidence convergence of the first and second terms on the RHS of the inequalities~\eqref{eq:convergence_split} due to Lemma~\ref{Lemma:conv_I} and Lemma~\ref{Lemma:conv_I_2}, respectively.

\begin{lemma}\label{Lemma:conv_I}
	Let Assumption~\ref{Assum:knn} hold. For any $\epsilon^*>0$, there exists $n_2$ such that for $n>n_2$ the following bounds hold:
	\begin{align}
	\pr{ \Big| \hat I_{\DV}^{n,\hat\theta} - I_{\DV}^{\hat\theta} \Big| \geq \frac{\epsilon^*}{2}}&\leq \mdel{5}(\epsilon^*), \label{eq:conv_I_DV}\\
	\pr{ \Big| \hat I_{\NWJ}^{n,\hat\theta} - I_{\NWJ}^{\hat\theta} \Big| \geq \frac{\epsilon^*}{2}}&\leq \mdel{6}(\epsilon^*), \label{eq:conv_I_NWJ}\\
	\pr{ \Big| \hat I_{\LDR}^{n,\hat\theta} - I_{\LDR}^{\hat\theta} \Big| \geq \frac{\epsilon^*}{2}}&\leq \mdel{7}(\epsilon^*), \label{eq:conv_I_LDR}
	\end{align}
	where $\mdel{5}$, $\mdel{6}$, and $\mdel{7}$ are defined in Table~\ref{tab:param}.
	\begin{proof}
		See Appendix~\ref{App:proof_Lemma_conv_I}.
	\end{proof}
\end{lemma}

\begin{lemma}\label{Lemma:conv_I_2}
	Let Assumptions~\ref{Assum:knn} and \ref{Assum:NN_Lip} hold and let $\tau<p_1$. Given $\epsilon^*>0$, there exists an integer $n_1$ such that for $n>n_1$
	\begin{align}
	\pr{ \Big| I_{\mathtt{est}}^{\hat\theta} - I(X;Y|Z) \Big| \geq \frac{\epsilon^*}{2}} &\leq\mdel{4}\left(\frac{\epsilon}{8}\right),\label{eq:conv_I_3}
	\end{align}

	where `$\mathtt{est}$' can be replaced with `$\DV$', `$\NWJ$', or `$\LDR$', and $\epsilon$ and $\mdel{4}$ are defined in Table~\ref{tab:param}.
	\begin{proof}
		See Appendix~\ref{App:proof_Lemma_conv_I_2}.
	\end{proof}
\end{lemma}

Therefore, if Assumption~\ref{Assum:b} also holds, we may combine Lemma~\ref{Lemma:conv_I} and Lemma~\ref{Lemma:conv_I_2} to yield a high-confidence bound for~\eqref{eq:convergence_split}, which concludes the proof of the Theorem.
\hfill$\square$

config: arxiv