%% 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[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{81}
\addbibresource{81.bib}

%% note that the class file already loads {amsmath, amsthm, amssymb}

% use these commands for typesetting doi and arXiv references in the bibliography
%\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
%\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}


%% define your title in the usual way
\title[Cluster algebras and binary words]{Cluster algebras and binary words}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Rachel Bailey\thanks{\href{mailto:rachel.bailey@uconn.edu}{rachel.bailey@uconn.edu}. 
%Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.
}%\addressmark{1} 
\and Emily Gunawan\thanks{\href{mailto:emily.gunawan@uconn.edu}{emily.gunawan@uconn.edu}. 
E.G. was supported by the NSF grant DMS-1254567 and by the University of Connecticut.}
%\addressmark{2}
}

% Dark red emphasis
\definecolor{darkred}{rgb}{0.7,0,0} % darkred color
\newcommand{\defn}[1]{{\color{darkred}\emph{#1}}} % emphasis of a definition


%% then use \addressmark to match authors to institutions here
\address{%\addressmark{1}
Department of Mathematics, University of Connecticut, 
Storrs, CT 06269-1009, USA
% \\ \addressmark{2}School of Something, University of Something Else, Somewhere
}

% 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{We establish a connection between binary subwords and perfect matchings of a snake graph, an important tool in the theory of cluster algebras.  
Every binary expansion~$w$ can be associated to a piecewise-linear poset~$P$ and a snake graph~$G$.
We describe bijections from the subwords of $w$ to the antichains of $P$ and to the perfect matchings of~$G$. 
We also construct a tree structure called the antichain trie which is isomorphic to the trie of subwords introduced by Leroy, Rigo, and Stipulanti. 
}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{
snake graph perfect matching, 
cluster algebra, 
binary subword, 
binomial coefficient of words, 
%combinatorics on words, 
antichain, 
order filter}


%% 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{fpsac19_bg.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Begin preamble not included in FPSAC sample %%%
%\usepackage{amsmath}
\usepackage{cases}
\usepackage{tikz}
\usetikzlibrary{shapes,calc}

\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=0.7pt] (char) {#1};}}
\newcommand*\doublecircled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,double,inner sep=0.9pt] (char) {#1};}}

%\theoremstyle{definition} % longer text
\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{solution}
  {\renewcommand\qedsymbol{$\blacksquare$}\begin{proof}[Solution]}
  {\end{proof}}
\usepackage[utf8]{inputenc}

%%% End preamble not included in FPSAC sample %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\maketitle

\section{Introduction}
\label{sec:poset}

A planar graph called the \defn{snake graph} appears naturally in the study of cluster algebras~\cite{FZ02}. 
An early version of the snake graph is a bipartite graph which is dual to a polygon triangulation and was studied by Propp et al. along with other equivalent combinatorial models~\cite{Pro05}. 
Musiker, Schiffler, and Williams then used the snake graphs to study positivity and bases of cluster algebras from surfaces~\cite{MSW11, MSW13}. 
The theory of abstract snake graph was developed further by {\c{C}anak\c{c}\i} and Schiffler~\cite{CS13}. 
The snake graphs are connected to various mathematical objects,  
including 
matchings of triangles~\cite{BCI74, Pro05, GMV16}, 
submodules of a string module~\cite{CC06, MSW13, CaSi18}, 
T-paths~\cite{ST09, GM15},  
0-1 sequences called globally compatible sequences (GCSs)~\cite{LLN17}, 
matchings of angles and minimal cuts~\cite{Yur18}, 
intervals in the weak order determined by a Coxeter element~\cite{CaSi18}, 
continued fractions~\cite{CS18}, 
and Jones polynomials~\cite{LS17}. 
We add another item to this list by providing a connection between snake graphs and base-2 expansions of positive integers.


In this paper, let a \defn{binary word} be a finite (possibly empty) sequence of letters on the alphabet $\{0,1 \}$  starting with $1$. 
Let a \defn{subword} of a binary word be a ``scattered" subsequence which is itself a binary word. 


To every nonempty binary word $w=w_1 w_2 \dots w_d$ of length $d$ 
we associate (the Hasse diagram of) a piecewise-linear partially ordered set (poset) $P$ as follows.
The elements of $P$ are labeled $P_1=1$, $\dots$, $P_d=d$, arranged from left to right in the Hasse diagram of~$P$, 
and there is an edge between $P_{i-1}$ and $P_{i}$.
For $i \geq 2$, if $w_i=1$ (respectively, if $w_i=0$) then the edge between $P_{i-1}$ and $P_i$ is of slope $1$ (respectively, $-1$), so that we have the 
covering relation $P_{i-1} \lessdot P_i$ (respectively, $P_{i-1} \gtrdot P_i$). See \cref{fig:hasse101110}. 

An \defn{antichain} is a subset $A= \{A_1, A_2, \dots ,A_r\}$ of a poset 
 such that no two distinct elements in $A$ are comparable. 
 For example, the subsets $\{1,3,6\}$, $\{1,4\}$, and $\{2,6\}$ of the poset whose Hasse diagram is given in \cref{fig:hasse101110} are antichains, while $\{2,4\}$ is not. 


\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[xscale=1, yscale=0.65]
\def\posetedgecolor{blue}
\node(1) at (0,0) {{$1$}}; 
\node(2) at (1,-1) {{$2$}};
\node(3) at (2,0) {{$3$}};
\node(4) at (3,1) {{$4$}};
\node(5) at (4,2) {{$5$}};
\node(6) at (5,1) {{$6$}};

\node[\posetedgecolor] at (-0.9,0) {$\underline{1}$};
\draw[-, line width=1pt] (2) -- (1) node[\posetedgecolor,pos=0.7,below] {\small $0$}; 
\draw[-, line width=1pt]  (2) -- (3) node[\posetedgecolor,pos=0.2,above] {\small $1$};  
\draw[-, line width=1pt] (3) -- (4) node[\posetedgecolor,pos=0.2,above] {\small $1$};  
\draw[-, line width=1pt] (4) -- (5) node[\posetedgecolor,pos=0.2,above] {\small $1$}; 
\draw[-,line width=1pt] (6) -- (5) node[\posetedgecolor,pos=0.7,below] {\small $0$}; 
\end{tikzpicture}

\caption{The Hasse diagram associated to the word \textcolor{blue}{$101110$}.}
\label{fig:hasse101110}
\end{center}
\end{figure}

In~{\cite[Sec.~2]{LRS17}}, Leroy, Rigo, and Stipulanti introduce a specific construction of a  prefix tree (called \defn{trie of subwords}) which is a binary tree that is convenient for counting distinct subwords occurring in a given word $w$. We use this same construction to define a tree we call \defn{antichain trie} to study the antichains of the poset $P$ corresponding to $w$.
We associate each node $v$ of the antichain trie to an antichain $A(v)$ of $P$ in such a way that moving from a node $v$ to its left child replaces $P_i$ in $A(v)$ with $P_{i+1}$ (where $i$ is the largest integer in $A(v)$) and moving from a node $v$ to its right child adds a new element $P_i$ to $A(v)$ (where $i$ is larger than every integer in $A(v)$). 

\begin{proposition}[\cref{prop:antichain_trie}] 
The nodes of the antichain trie are distinct antichains.
\end{proposition}

Next, we show that this antichain trie contains all antichains by giving a bijection between the subwords and the antichains. 

\begin{theorem}[\cref{thm:antichain_to_subword}]
Given a nonempty binary word $w$ and its corresponding piecewise-linear poset $P$, there is a bijection between the subwords of $w$ and the antichains of~$P$. 
\end{theorem}

It is known that one can associate a binary sequence of length $d-1$ to a snake graph with $d$ tiles (see \cref{def:sign_function}). So, given a binary word $w=w_1$ $w_2$ $\dots$ $w_d$, we associate $(w_2, \dots, w_d)$ to a snake graph $G(w)$ and  
present a bijection from the subwords of $w$ to the perfect matchings of $G(w)$.

\begin{theorem}[\cref{thm:subwords_to_snake_graph_matchings}]
The subwords of a binary word $w$ are in bijection with the perfect matchings of its corresponding snake graph $G(w)$. 
\end{theorem}

The paper is organized as follows. 
In \cref{sec:trie_of_subwords}, we recall the construction of the trie of subwords given by Leroy, Rigo, and Stipulanti.
In \cref{sec:antichain_trie}, we introduce the antichain trie.  
We define a map from the antichains to the subwords and prove that it is a bijection in \cref{sec:bijection_between_antichains_and_subwords}.
In \cref{sec:subwords_to_snake_graph_matchings}, 
 we give the necessary snake graph theory background and present a bijection between subwords and perfect matchings. 

\section{Trie of subwords}
\label{sec:trie_of_subwords}


Let $w = w_1\dots w_d$ be a nonempty binary word and  
consider the \defn{trie of (distinct) subwords} of $w$, denoted by $\mathcal{T}$. 
It is a tree with the root denoted by $\epsilon$. 
If $u$ and $ua$ are two subwords of $w$ with $a$ being a one-letter subword, then $ua$ is a child of $u$. This trie is also called a \defn{prefix tree} because all successors of a node have a common prefix. 
Note that, since $w$ is a binary word, the trie is a binary tree. 
For the rest of the section, we describe the specific construction of $\mathcal{T}$ which is given in~{\cite[Sec.~2]{LRS17}}.

Factor $w$ into consecutive maximal blocks of 1's and blocks of 0's such that 
\[
w=\underbrace{1^{n_1}}_{u_1} \underbrace{0^{n_2}}_{u_2} \underbrace{1^{n_3}}_{u_3} \underbrace{0^{n_4}}_{u_4} \cdots \underbrace{1^{n_{2j-1}}}_{u_{2j-1}} \underbrace{0^{n_{2j}}}_{u_{2j}}
\]
with $j\geq 1$, $n_1, \dots, n_{2j-1} \geq 1$ and $n_{2j} \geq 0$.
Let $M$ be such that $w=u_1 u_2 \dots u_M$
where $u_M$ is the last non-empty block of zeroes or ones.


To construct the trie $\mathcal{T}$, begin with a vertical linear tree $T_w$ with 
nodes 
$v_0$, %$v_1$, 
$\dots$, $v_d$. %, drawn vertically. 
Let $T_w$ be rooted at $\epsilon = v_0$ and let node $v_i$ be the left child of node $v_{i-1}$ for all $i=1,\dots,d$. 
Label the edges 
of $T_w$ 
with the letters of $w$ such that the edge between nodes $v_{i-1}$ and $v_{i}$ is labeled $w_{i}$. We identify each node $v$ by the path of edge labels from $\epsilon$ to $v$. 

Starting from the bottom of the vertical linear tree $T_w$, we define a tree $T_l$ for every $l \in \{M-1, \dots, 2, 1\}$. Each tree is rooted at the node $u_1 \dots u_l1$ if $l$ is even and $u_1 \dots u_l0$ if $l$ is odd. 
First, let $T_{M-1}$ be the (linear) subtree of $T_w$ consisting of the last $n_M$ nodes.

We then attach a copy of $T_{M-1}$ to each node (on the vertical tree $T_w$) of the form
\[
\begin{cases}
  u_1u_2 \dots u_{M-2}1^j, & \text{if $u_{M-1}$ is a block of 1s}\\
  u_1u_2 \dots u_{M-2}0^j, & \text{if $u_{M-1}$ is a block of 0s}
\end{cases}
~~~~~~~ \text{ for $j \in \{0,1 \dots, n_{M-1}-1\}$.}
\]
Let the root of each copy of $T_{M-1}$ be the right child of the node of $T_w$ that this root is attached to. This results in a (non-linear) tree $T_w'$ that is larger than $T_w$. 

Let $T_{M-2}$ be the %(non-linear) 
subtree of this larger tree $T_w'$ such that its root is   
 $u_1 \dots u_{M-2}1$ if $M-2$ is even and $u_1 \dots u_{M-2}0$ if $M-2$ is odd and $T_{M-2}$ contains all the descendants of this root.  
Then attach a copy of $T_{M-2}$ to each node of the form
\[
\begin{cases}
 u_1 u_2 \dots  u_{M-3}1^j, & \text{if $u_{M-2}$ is a block of 1s}\\
 u_1 u_2 \dots u_{M-3}0^j, & \text{if $u_{M-2}$ is a block of 0s}
 \end{cases}
~~~~~~~ \text{ for $ j\in \{0,1,...,n_{M-2}-1\}$.}
\]
Again, let the root of each copy of $T_{M-2}$ be the right child of the node of $T_w$ that this root is attached to. 

Let $T_{M-3}$ be the subtree of this larger tree such that it is rooted at  
 $u_1$$\dots$$u_{M-3}1$ (resp., $u_1 \dots u_{M-3}0$) if $M-3$ is even (resp., odd) and $T_{M-3}$ contains all descendants of this root.  


Continue as such until after we attach a copy of $T_2$. If $n_1=1$ then no copy of $T_1$ is added (as in \cref{fig:trie101110,fig:subwordtrie_10010111} (left)). If $n_1 > 1$ then a copy of $T_1$ is added to each node of the form $1^j, j\in \{0, 1,\dots ,n_1 -1\}$ (as in~\cite[Example~8]{LRS17}).

When $T_l$ is copied, keep its respective edge labels. The new edge connecting a copy of $T_l$ to the original vertical linear tree $T_w$ has the same label as the edge (of $T_w$) above the root of the original copy of $T_l$. 



\begin{example}
\label{example:fig:trie101110}
\cref{fig:trie101110} (left) shows the complete trie of subwords for the word $101110$. Since $w = \underbrace{1^1}_{u_1}\underbrace{0^1}_{u_2}\underbrace{1^3}_{u_3}\underbrace{0^1}_{u_4}$, we have $M = 4$.  
The subtree $T_3$ is the sole diamond node on $T_w$ because $T_3$ is rooted at the node $u_1u_2u_30$. We then attach a copy of $T_3$ to the nodes $ u_1u_21^j, j\in\{0,1,2\}$. The root of $T_2$ is the node $u_1u_21$ (the square node) and we attach a copy of $T_2$ to the node $u_10^j, j \in \{0\}$. Lastly, because $n_1 = 1$, no copy of $T_1$ is added.
See also \cref{fig:subwordtrie_10010111} (left) and~\cite[Figs.~3-4]{LRS17}.
\begin{figure}[ht]
\begin{center}
\def\xfigscale{1.33}
\def\yfigscale{0.85}
\input{trie101110}
~~~
\input{antichaintrie_101110}
~~~
\input{trie_antichainsof101110}
\caption{Trie of subwords of \textcolor{blue}{101110} (left); 
antichain trie corresponding to \textcolor{blue}{101110} (center) and 
its corresponding antichains (right)}
\label{fig:trie101110} % left
\label{fig:ex:antichaintrie_101110} % center
\label{fig:trie_antichainsof101110} % right
\end{center}
\end{figure}

\end{example}\label{ex:trieofsubwords_101110}

\section{Antichain trie}
\label{sec:antichain_trie}
We define an antichain analog of the~\cite{LRS17} trie of subwords, call it the \defn{antichain trie}, and assign a distinct antichain to each of its nodes. 

\begin{definition}[Antichain trie]
Given a binary word $w$ of length $d$, construct the trie of subwords as above, but remove all edge labels (of $1$s and $0$s). We label each node $v$ with a non-distinct label $L(v)$ as follows. 
First, we label the $d+1$ nodes of the leftmost vertical linear tree $T_w$. 
Starting from the top left node ($\epsilon$) and moving down, label $\epsilon$ as $0$, then its descendants as $1, 2,\dots,d$. When we attach copies of $T_{M-1},\dots,T_1$, we keep these original node labels (so that two different nodes may have the same label $k$). 
See \cref{fig:trie101110} (center). 

To each node $v$, we associate the path $\epsilon, v_1, \dots,v_{\ell}$ along the vertices from $\epsilon$ to $v$. Let $p(v)$ be the sequence of labels $L(\epsilon)=0, L(v_1), \dots,L(v_\ell)$ of these vertices. 
Note that $p(v)$ is a unique ordered subsequence of $(0,1, \dots,d)$. 
Let $A(\epsilon)=\emptyset$, and for the rest of the nodes $v$, let  
\[ A(v)=\Big\{ j \in \{ 1,2,\dots, d\} ~ | ~ \text{$j$ is the largest number in a block of consecutive integers in $p(v)$} \Big\}.\]  
\end{definition}



\begin{proposition}
\label{prop:antichain_trie}
Let $P$ be the poset corresponding to a binary word $w$. 
Then for each node $v$ of the antichain trie of $w$, the set $A(v)$ is a distinct antichain of $P$.
\end{proposition}


\begin{example} 
In \cref{fig:trie_antichainsof101110} (right), we have labeled every node $v$ with $A(v)$. For example, if $v$ is the node obtained by the path $p(v) = (0, 1, 2, 3, 6 )$ of \cref{fig:ex:antichaintrie_101110} (center), then $A(v) = \{3,6\}$. For the node $v$ obtained by walking along $p(v) = (0, 1, 3, 4, 6)$, we have the antichain $A(v) = \{1, 4, 6\}$. 
\end{example}




\begin{example} \label{ex:antichainsof10010111}
Let $w= 10010111$. %of length $d=8$. 
\cref{hasse_10010111} shows the Hasse diagram of the 8-element poset $P$ corresponding to $w$. \cref{fig:subwordtrie_10010111} (left) depicts the trie of subwords for $w$. Write  $w =\underbrace{1^1}_{u_1}\underbrace{0^2}_{u_2}\underbrace{1^1}_{u_3} \underbrace{0^1}_{u_4}\underbrace{1^3}_{u_5} $, so $M = 5$. The root of $T_4$ is $u_1u_2u_3u_41$ (the diamond node), the root of $T_3$ is $u_1u_2u_30$ (the square node), and the root of $T_2$ is $u_1u_21$ (the 
star node). 
\cref{fig:antichaintrie_10010111} (right) shows the antichain trie for $w$. 
Lastly, \cref{fig:antichainsof10010111} shows the $32$ antichains of $P$ which we assign to the $32$ nodes of the antichain trie. 


\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[xscale=0.9,yscale=0.6,>=latex]
\def\posetedgecolor{blue}
\node(1) at (0,0) {{$1$}}; 
\node(2) at (1,-1) {{$2$}}; 
\node(3) at (2,-2) {{$3$}}; 
\node(4) at (3,-1) {{$4$}}; 
\node(5) at (4,-2) {{$5$}}; 
\node(6) at (5,-1) {{$6$}}; 
\node(7) at (6,0) {{$7$}}; 
\node(8) at (7,1) {{$8$}}; 

\node[\posetedgecolor] at (-0.7,0) {$\underline{1}$};
\draw[-, line width = 1pt] (2) -- (1) node[\posetedgecolor,pos=0.7,below] {\small $0$}; 
\draw[-, line width = 1pt]  (3) -- (2) node[\posetedgecolor,pos=0.7,below] {\small $0$}; ; 
\draw[-, line width = 1pt] (3) -- (4) node[\posetedgecolor,pos=0.2,above] {\small $1$}; ; 
\draw[-, line width = 1pt] (5) -- (4) node[\posetedgecolor,pos=0.7,below] {\small $0$}; ;
\draw[-,line width=1pt] (5) -- (6) node[\posetedgecolor,pos=0.2,above] {\small $1$}; ; 
\draw[-, line width = 1pt] (6) -- (7) node[\posetedgecolor,pos=0.2,above] {\small $1$}; ; 
\draw[-, line width = 1pt] (7) -- (8) node[\posetedgecolor,pos=0.2,above] {\small $1$}; ; 
\end{tikzpicture}

\caption{The Hasse diagram of the poset corresponding to the word \textcolor{blue}{10010111}.} \label{hasse_10010111}
\end{center}
\end{figure}

\begin{figure}[h!]
\def\xfigscale{1.2}
\def\yfigscale{0.75}
\begin{center}
\input{subwordtrie_10010111}~~~~
\input{antichaintrie_10010111}
\caption{The trie of subwords (left) and the antichain trie (right) of $10010111$}
\label{fig:subwordtrie_10010111} % left
\label{fig:antichaintrie_10010111} % right
\begin{tikzpicture}[xscale=1.8,yscale=0.9,>=latex]
\def\posetedgecolor{blue} % macro
\node(empty) at (0,0) {$\emptyset$};
\node(0-1) at (0,-1) {$\{1\}$};
\node(0-2) at (0,-2) {$\{2\}$};
\node(0-3) at (0,-3) {$\{3\}$};
\node(0-4) at (0,-4) {$\{4\}$};
\node(0-5) at (0,-5) {$\{5\}$};
\node(0-6) at (0,-6) {$\{6\}$};
\node(0-7) at (0,-7) {$\{7\}$};
\node(0-8) at (0,-8) {$\{8\}$};

\node(1-5-6) at (1,-5) {$\{4,6\}$};
\node(1-6-7) at (1,-6) {$\{4,7\}$};
\node(1-7-8) at (1,-7) {$\{4,8\}$};

\node(2-4-5) at (2,-4) {$\{3,5\}$};
\node(2-5-6) at (2,-5) {$\{3,6\}$};
\node(2-6-7) at (2,-6) {$\{3,7\}$};
\node(2-7-8) at (2,-7) {$\{3,8\}$};

\node(3-3-4) at (3,-3) {$\{2,4\}$};
\node(3-4-5) at (3,-4) {$\{2,5\}$};
\node(3-5-6) at (3,-5) {$\{2,6\}$};
\node(3-6-7) at (3,-6) {$\{2,7\}$};
\node(3-7-8) at (3,-7) {$\{2,8\}$};

\node(4-4-6) at (4,-4) {$\{2,4,6\}$};
\node(4-5-7) at (4,-5) {$\{2,4,7\}$};
\node(4-6-8) at (4,-6) {$\{2,4,8\}$};

\node(5-2-4) at (5,-2) {$\{1,4\}$};
\node(5-3-5) at (5,-3) {$\{1,5\}$};
\node(5-4-6) at (5,-4) {$\{1,6\}$};
\node(5-5-7) at (5,-5) {$\{1,7\}$};
\node(5-6-8) at (5,-6) {$\{1,8\}$};

\node(6-3-6) at (6,-3) {$\{1,4,6\}$};
\node(6-4-7) at (6,-4) {$\{1,4,7\}$};
\node(6-5-8) at (6,-5) {$\{1,4,8\}$};

\draw[-] (empty) 
-- (0-1) node[\posetedgecolor,pos=0.5,right,left] {}
 -- (0-2) node[\posetedgecolor,pos=0.2,below] {} 
 -- (0-3) node[\posetedgecolor,pos=0.5,above] {}
 -- (0-4) node[\posetedgecolor,pos=0.5,left] {}
 -- (0-5) node[\posetedgecolor,pos=0.5,right=1pt] {}
 -- (0-6) node[\posetedgecolor,pos=0.5,left=1mm] {}
 -- (0-7) node[\posetedgecolor,pos=0.5,left=1mm] {}
 -- (0-8) node[\posetedgecolor,pos=0.5,left=1mm] {};

\draw[-] 
-- (1-5-6) node[\posetedgecolor,pos=0.5,right,left] {}
 -- (1-6-7) node[\posetedgecolor,pos=0.2,below] {} 
 -- (1-7-8) node[\posetedgecolor,pos=0.5,above] {};
 
 \draw[-] 
-- (2-4-5) node[\posetedgecolor,pos=0.5,right,left] {}
 -- (2-5-6) node[\posetedgecolor,pos=0.2,below] {} 
 -- (2-6-7) node[\posetedgecolor,pos=0.5,above] {}
 --(2-7-8) node[\posetedgecolor,pos=0.5,above] {};
 
  \draw[-] 
-- (3-3-4) node[\posetedgecolor,pos=0.5,right,left] {}
 -- (3-4-5) node[\posetedgecolor,pos=0.2,below] {} 
 -- (3-5-6) node[\posetedgecolor,pos=0.5,above] {}
 --(3-6-7) node[\posetedgecolor,pos=0.5,above] {}
 --(3-7-8) node[\posetedgecolor,pos=0.5,above]{};

 \draw[-] 
-- (4-4-6) node[\posetedgecolor,pos=0.5,right,left] {}
 -- (4-5-7) node[\posetedgecolor,pos=0.2,below] {} 
 -- (4-6-8) node[\posetedgecolor,pos=0.5,above] {};

 \draw[-] 
-- (5-2-4) node[\posetedgecolor,pos=0.5,right,left] {}
 -- (5-3-5) node[\posetedgecolor,pos=0.2,below] {} 
 -- (5-4-6) node[\posetedgecolor,pos=0.5,above] {}
 --(5-5-7) node[\posetedgecolor,pos=0.5,above] {}
 --(5-6-8) node[\posetedgecolor,pos=0.5,above] {};
 
  \draw[-] 
-- (6-3-6) node[\posetedgecolor,pos=0.5,right,left] {}
 -- (6-4-7) node[\posetedgecolor,pos=0.2,below] {} 
 -- (6-5-8) node[\posetedgecolor,pos=0.5,above] {};

 
\draw[-] (0-1) -- (5-2-4) node[\posetedgecolor,pos=0.5,right,left] {};
\draw[-] (0-2) -- (3-3-4) node[\posetedgecolor,pos=0.5,right,left] {$$};
\draw[-] (0-3) -- (2-4-5) node[\posetedgecolor,pos=0.5,right,left] {$$};
\draw[-] (0-4) -- (1-5-6) node[\posetedgecolor,pos=0.5,right,left] {$$};

\draw[-] (5-2-4) -- (6-3-6) node[\posetedgecolor,pos=0.5,right,left] {$$};
\draw[-] (3-3-4) -- (4-4-6) node[\posetedgecolor,pos=0.5,right,left] {$$};
\end{tikzpicture}
\caption{Antichains corresponding to nodes of \cref{fig:antichaintrie_10010111} (right)}\label{fig:antichainsof10010111}
\end{center}
\end{figure}
\end{example}

\begin{remark}
Given an antichain trie, 
let a \defn{vertical branch} be a linear subtree with nodes $v_1,\dots,v_{r+1}$ ($r\geq 1$) so that $v_1$ is either the root $\epsilon$ or is the right child of its parent (in particular, it is not a left child), $v_{i+1}$ is the left child of $v_i$ for $i=1,\dots,r$,
and $v_{r+1}$ is not a parent. 
For example, in \cref{fig:ex:antichaintrie_101110} (center), the original left-most vertical tree and the subtree labeled $\{3,4,5,6\}$ are 
the only vertical branches 
while \cref{fig:antichaintrie_10010111} (right) has $7$ vertical branches.  
Note that, by construction of the antichain trie, 
a vertical move (downward) from a node $v$ to its left child $v'$ 
removes the label $L(v)$ from $A(v)$ and replaces it with the label $L(v')=L(v)+1$.

Similarly, let a \defn{horizontal branch} be a linear subtree with nodes $v_1,\dots,v_{r+1}$ ($r\geq 1$) so that $v_1$ is the left child of some node (in particular, $v_1$ cannot be a right child), $v_{i+1}$ is the right child of $v_i$ for all $i=1,\dots, r$, 
and $v_{r+1}$ does not have a right child. For example, in \cref{fig:ex:antichaintrie_101110} (center), the subtrees labeled $\{1,3,6\}$, $\{2,6\}$, $\{3,6\}$, and $\{4,6\}$ are the horizontal branches, with $2$ different horizontal branches both labeled by $\{4,6\}$. 
The trie in \cref{fig:antichaintrie_10010111} (right) has exactly $4$ horizontal branches, labeled by $\{1,4, 6 \}$, 
$\{ 2,4,6\}$, $\{ 3, 5 \}$, and $\{ 4, 6\}$.  
A horizontal move (to the right) from a node $v$ to its right child $v'$ adds to the antichain $A(v)$ the (positive integer) label $L(v')$ of $v'$ which is greater than $L(v)+1$. 
\end{remark}
 

\section{Bijection between antichains and subwords}\label{sec:bijection_antichains_subwords}
\label{sec:bijection_between_antichains_and_subwords}
Let $w=w_1 \dots w_d$ be a binary word of length $d$. Let $P=\{ P_1=1,\dots, P_d=d\}$ be the corresponding piecewise-linear poset whose Hasse diagram $H$ has edges labeled by $w_2,\dots,w_d$.
We now define a map $f$ from the antichains in $P$ to the subwords of $w$. 
\begin{definition}[]\label{def:injective_map}
Let $f(\emptyset)$ be the empty subword. 
If $A = \{A_1, A_2 \dots, A_r\}$ is a nonempty antichain in $P$,   
%If $A$ is  the empty antichain, then it is mapped to the empty subword. 
let $f(A)$ be the subword of $w$ which is constructed as follows: The first letter is 1. The next letters are the (possibly empty) sequence of edge labels of $H$ between $P_1$ and $A_1$. If $A$ contains one element, we are done. If $A$ contains more than one element, jump to the first minimal or maximal element $M_1$ appearing after $A_1$. Record the labels of edges between $M_1$ and $A_2$. Next, jump to the first minimal or maximal element $M_2$ appearing after $A_2$. Record the labels of edges between $M_2$ and $A_3$. Continue as such until we finish  recording the edge labels between $M_{r-1}$ and $A_r$.
\end{definition}

\def\aa{1}
\def\bb{2}
\def\cc{3}
\def\dd{4}
\def\ee{5}
\def\ff{6}
\def\gg{7}
\def\hh{8}
\def\ii{9}
\def\jj{10}
\begin{example}
\label{example:antichain_to_subword}
\def\AntichainToSubwordScaleX{0.8}
\def\AntichainToSubwordScaleY{1}
In \cref{fig:example:antichain_to_subword}, 
the antichains $A$=$\{ A_1$=$\circled{\dd}$, $A_2$=$\circled{\jj}\}$ 
and $A$=$\{ A_1$=$\circled{\aa}$, $A_2$=$\circled{\cc}$, $A_3$=$\circled{\gg}$, $A_4$=$\circled{\ii}\}$ 
are mapped to the subwords 
s=\textcolor{blue}{\underline{1}\boxed{011}\boxed{01100}} and 
s=\textcolor{blue}{\underline{1}\framebox(7,12){}\framebox(10,12){1}\framebox(20,12){01}\framebox(10,12){0}} of $w=10010111$. 

\begin{figure}[ht]
\begin{center}
\input{antichain101101100}
\hspace{-8mm}
\input{antichain11010}
\caption{
The antichains mapped to 
s=\textcolor{blue}{\underline{1}\boxed{011}\boxed{01100}} (left) and 
s=\textcolor{blue}{\underline{1}\framebox(7,12){}\framebox(10,12){1}\framebox(20,12){01}\framebox(10,12){0}} (right) of $w=10010111$.
}
\label{fig:example:antichain_to_subword}
\end{center}
\end{figure}
\end{example}


\begin{theorem}
\label{thm:antichain_to_subword}
The map $f$ given in \cref{def:injective_map} is a bijection from the antichains in $P$ to the subwords of $w$. 
\end{theorem}
\begin{proof}
To show that $f$ is surjective, let $s$ be a subword of $w=w_1 w_2 \dots w_d$. If $s$ is nonempty, write $s=w_{i_1}w_{i_2} \dots w_{i_\ell}$ in such a way that each index $i_k$ is as small as possible (see \cref{ex:inverse_map_11010}). Note that $w_{i_1}=w_1=1$ per our definition of subwords. 
Partition $w_{i_1}, w_{i_2}, \dots, w_{i_\ell}$ into a set $\Sigma=\Sigma_s$ of (at least one)  maximal blocks of subsequences of $w$ such that each subsequence is a consecutive subsequence.  

Let \[A=A_\Sigma=\{ j \in P | (w_i, w_{i+1} \dots, w_j) \in \Sigma \}.\]
In other words, $(w_1)\in \Sigma$ if and only if $1 \in A$; if $2\leq n \leq d$, then $n\in A$ if and only if the node $n$ in the Hasse diagram $H$ is immediately to the right of a block in $\Sigma$.

We claim that $A$ is an antichain.
If $\Sigma$ only contains one block, then $A$ consists of one element, and hence $A$ is an antichain in $P$.
Otherwise, let $(w_i,\dots,w_j)$, where $3\leq i\leq d$, be a second block in $\Sigma$. 
If $w_i=0$, then $w_{i-1}=1$ since the indices $i_k$'s for the $w_{i_k}$'s were chosen to be as small as possible. Likewise, if $w_i=1$, then $w_{i-1}=0$. This means that the node $i-1$ (which is not in $A$) between $w_{i-1}$ and $w_{i}$ is either a minimal or maximal element of $P$. Hence no node to the left of $i-1$ is related to the node $j$. Similarly, if there is another block $(w_{i'},\dots,w_{j'})$ of $\Sigma$ which appears after  $(w_i,\dots,w_j)$, the node $j$ is not related to the node $j'$. This shows that $j$ is not related to any other element in $A$.

To show that the map is injective, assume $f(A) = f(A')$. Then $f(A) = s = f(A')$ for some subword $s=w_{i_1} \dots w_{i_\ell}$. Let $\Sigma_s$ be the set of maximal blocks of $w_{i_1}, \dots, w_{i_\ell}$ as defined on the first paragraph of this proof. But both $A$ and $A'$ are defined by the same set $\Sigma_s$ of maximal blocks, so $A = A'$.
\end{proof}

\begin{example}\label{ex:inverse_map_11010}
Consider the word $w=w_1 \dots w_{10} = 1011101100$. %of length $10$. 
Identify $w_2,\dots,w_{10}$ with the edges of the Hasse diagram $H$ of $P$, see \cref{fig:poset1011101100}. 
We write the subword s=\textcolor{blue}{$11010$} as $s=w_1 w_3 w_6 w_7 w_9$ so that the index of each letter $w_{i_k}$ is as small as possible.  Breaking $w_1 w_3 w_6 w_7 w_9$ into maximal blocks of consecutive subsequences of $w$ gives four blocks $(w_1)$, $(w_3)$, $(w_6, w_7)$, and $(w_9)$. We build an antichain as follows. Since $(w_1)$ is a block, we take the left-most node of $H$, node $1$.
We take the nodes of $H$ to the right of the other three blocks, nodes $3$, $7$, and $9$. Therefore, the subword 11010 corresponds to the antichain $\{
\circled{1},\circled{3},\circled{7},\circled{9}\}$.

\begin{figure}[h]
\begin{center}
\input{poset1011101100}
\caption{Hasse diagram representing $1011101100$; the antichain corresponding to the subword \textcolor{blue}{$\underline{1}\boxed{1}\boxed{01}\boxed{0}$} is $\{ 1,3,7,9\}$.}\label{fig:poset1011101100}
\end{center}
\end{figure}
\end{example}


\section{Subwords to snake graph matchings}
\label{sec:subwords_to_snake_graph_matchings}

\subsection{Background}
We review the theory of snake graphs developed in~\cite{Pro05, MSW11, MSW13, CS13}.

\begin{definition}
A \defn{snake graph} is a nonempty connected sequence of square tiles~
\begin{tikzpicture}[scale=.25]
\draw (0,0) -- (1,0) -- (1,1) -- (0,1) -- cycle;
\end{tikzpicture}.
To build a snake graph $G$ with $d$ tiles, start with one tile, then glue a new tile to the north or the east of the previous tile. We refer to the southwest-most tile of $G$ as the first tile $G_1$ and the northeast-most tile as the last tile $G_d$. \cref{fig:minimalmatching} (left) illustrates a snake graph with $10$ tiles.
\end{definition}
 


\begin{definition}
A \defn{matching} of a graph $G$ is a subset of non-adjacent edges of $G$.
A \defn{perfect matching} of $G$ is a matching where every vertex of $G$ is adjacent to exactly one edge of the matching, see \cref{fig:snake_graph_matching}.
Define the \defn{minimal matching} $P_{\text{min}}$ to be the unique perfect matching of $G$ which contains the first south edge and only boundary edges, see \cref{fig:minimalmatching} (center).

\begin{figure}[h]
\begin{center}
\input{def_pm_min_and_dk}
\caption{A snake graph (left); the minimal perfect matching (center); another perfect matching  of the snake graph (right)}\label{fig:snake_graph_matching}
\label{fig:minimalmatching}
\end{center}
\end{figure}
\end{definition}

A cluster algebra~\cite{FZ02} is a commutative algebra with distinguished generators called \defn{cluster variables} which can be written as Laurent polynomials with positive coefficients. In the case of a family of cluster algebras called \defn{cluster algebras from surfaces}, given such a Laurent polynomial $x_\gamma$, it was shown in~\cite[Thm.~4.17]{MSW11} that $x_\gamma$ can be associated to a certain snake graph $G_\gamma$ and that $x_\gamma$ can be written as a sum over all perfect matchings of $G_\gamma$. In particular, the terms of $x_\gamma$ are in bijection with the perfect matchings of $G_\gamma$.


The following allows us to associate a snake graph to a binary word. 

\begin{definition}[{\cite[Sec.~2.1]{CS13}}]
\label{def:sign_function}
A \defn{sign function} on a snake graph $G$ is a map from the set of edges of G to 
$\{+,-\}$ 
such that, for every tile of $G$, the north edge and the west edge have the same sign, 
 the south edge and the east edge have the same sign, and 
 the sign on the north edge is opposite to the sign on the south edge.

\begin{figure}[ht]
\begin{center}
\input{sign_function}
\caption{
Corresponding sign function 
(left and center) and sign sequence (right) of the snake graph for the binary expansion $\textcolor{blue}{\underline{1}011101100}$.}
\label{fig:plain_snake_graph}\label{fig:example:sign_function}
\label{fig:signsequence}
\end{center}
\end{figure}
\end{definition}

Note that there are exactly two sign functions on every snake graph. 
We consider only the sign function where the south edge of the first tile has label $-$, see \cref{fig:example:sign_function} (left). 
Since we study binary expansions, we replace $+$ with $1$ and $-$ and $0$, see \cref{fig:example:sign_function} (center). 


Given the sign function of a snake graph $G$ whose west edge of the first tile
 has sign~$1$, 
let the \defn{sign sequence} of $G$ be the sequence $(1,w_2,\dots,w_d)$ where 
$w_2, \dots, w_d$ 
are the signs of the interior edges of the snake graph, see \cref{fig:signsequence} (right). 
As this sequence uniquely determines a snake graph, we can associate to each binary word $w=1w_2\dots w_d$ a snake graph $G(w)$. 

\subsection{Bijection from subwords to perfect matchings}
An \defn{order filter} %(or dual order ideal) 
is 
a subset $F$ of $P$ such that if $t \in F$ and $s \geq t$, then $s \in F$.
The perfect matchings of a snake graph $G$ is known to form a lattice
 isomorphic to the lattice of order filters of the piecewise-linear poset corresponding to $G$
~\cite[Thm.~2]{Pro02}, \cite[Sec.~5]{MSW13}. 
It is also known that the map which sends an order filter to its set of minimal elements 
is a bijection between the order filters and the antichains in a poset. 
Therefore, by \cref{thm:antichain_to_subword}, there is a bijection from the subwords of $w$ to the perfect matchings of $G(w)$. 


\begin{theorem}
\label{thm:subwords_to_snake_graph_matchings}
Given a binary subword $w$ and its corresponding snake graph $G=G(w)$,  
the following map $pm$ from the subwords of $w$ to the perfect matchings of $G$ is a bijection: 

\begin{itemize}
\item 
Let $s$ be a subword of $w$. 
If $s$ is the empty word, let $pm(s)$ be $P_{\text{min}}$. 
Otherwise, write $s=w_{i_1}w_{i_2} \dots w_{i_\ell}$ in such a way that each index $i_k$ is as small as possible (as we do in \cref{sec:bijection_antichains_subwords}) and 
circle the edges of $G$ corresponding to the sign sequence for $s$.

\item For each block $L$ 
of consecutive circled edges, let $\square_L$ be the tile which is immediately north/east of the last edge in $L$. 

\item Let $fil(\square_L)$ be 
the smallest connected sequence of tiles such that $\square_L \in fil(\square_L)$ and the set of edges bounding $fil(\square_L)$ not in $P_{\text{min}}$ forms a perfect matching of $fil(\square_L)$.

\item Let $ fil(s)= \bigcup_{L} fil(\square_L)$, and 
define $pm(s)$ to be the symmetric difference $\{$edges bounding $fil(s)\} \ominus P_{\text{min}}$. 
\end{itemize}
\end{theorem}

\begin{example}
\label{example:subword_to_pm}
Consider the word $w = 1011101100$. 
In \cref{fig:square_L:s101101100},  
we circle the edges of $G$ corresponding to $s=\textcolor{blue}{101101100}$. 
The corresponding $2$ blocks of shaded tiles  
are 
$\left\{ \boxed{d}, \boxed{e} \right\}$ 
and 
$\left\{ \boxed{h}, \boxed{i}, \boxed{j} \right\}$, 
and 
$pm(s)$ 
is the set of thick  edges.
In \cref{fig:square_L:s11010}, 
we circle the edges of $G$ corresponding to $s=\textcolor{blue}{11010}$.
Note that $fil\left(\boxed{g}\right)=\left\{\boxed{g}, \boxed{h}, \boxed{i} \right\}
=fil\left(\boxed{i}\right)$.  
The $3$ blocks of shaded tiles are 
$\left\{ \boxed{a} \right\}$, 
$\left\{ \boxed{c}, \boxed{d}, \boxed{e}\right\}$, and $\left\{\boxed{g}, \boxed{h}, \boxed{i}\right\}$
so that $fil(11010)$
=$\left\{ \boxed{a}, \boxed{c}, \boxed{d}, \boxed{e}, \boxed{g}, \boxed{h}, \boxed{i}\right\}$.  

\def\myscalematching{0.6}
\begin{figure}[h!]
\begin{center}
\input{highlightedsubword101101100}
\hspace{-2.5cm}
$\square_{\textcolor{blue}{1011}}$=$\boxed{d}$ and $\square_{\textcolor{blue}{01100}}$=$\boxed{j}$ 
\hspace{-0.5cm}
\input{fil_dj}
\hspace{-1.4cm}
\input{pm_dj}
\caption{Tiles $\square_L$ associated to blocks $L$ of circled edges (left); 
the set $fil(s)$ of shaded tiles and the set $pm(s)$  of thick solid edges (right) for the subword 
s=\textcolor{blue}{$\boxed{1011}\boxed{01100}$}. 
}
\label{fig:square_L:s101101100}
\label{fig:example:pm_dk}
\input{highlightsubword11010}
\hspace{-2.9cm}
{\small $\square_{\textcolor{blue}{1}}$=$\boxed{a}$, $\square_{\textcolor{blue}{1}}$=$\boxed{c}$ , $\square_{\textcolor{blue}{01}}$=$\boxed{g}$, $\square_{\textcolor{blue}{0}}$=$\boxed{i}$}
\hspace{-0.7cm}
\input{pm_acgi}
\caption{Tiles $\square_L$ associated to blocks $L$ of circled edges (left);
 the set $fil(s)$ of shaded tiles and the set $pm(s)$ of thick solid edges (right) for the subword s=$\textcolor{blue}{\boxed{1}\boxed{1}\boxed{01}\boxed{0}}$. 
 }
\label{fig:square_L:s11010}\label{fig:example:pm_acgi}
\end{center}
\end{figure}
\end{example}


\acknowledgements{
This project was inspired by conversations with M.~Stipulanti and L.~Tarsissi during the conference ``Sage Days 82 : Women in Sage", held January 2017 in Paris, funded by the OpenDreamKit project. We thank the organizers (V.~Pons, J.~Balakrishnan and 
J.~Striker) for creating such a productive environment. We are also grateful for helpful conversations with R.~Schiffler and  for useful comments from the anonymous referees. 
}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way

\sloppy
\printbibliography
\fussy

\end{document}