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

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


\usepackage[utf8]{inputenc}
%\usepackage{cleveref}
%\usepackage{soul}
%\usepackage{comment}
%\usepackage{changes}
%\usepackage{booktabs}
%\usepackage{stmaryrd}
\usepackage{tikz}
%\usepackage{ytableau}
\setlength{\parindent}{.5cm}
\usepackage[colorinlistoftodos]{todonotes}
%\usepackage[disable]{todonotes}
\newcommand{\matjaz}[1]{\todo[size=\tiny,inline,color=yellow!30]{#1 \\ \hfill --- M.}}
\newcommand{\sara}[1]{\todo[size=\tiny,inline,color=blue!30]{#1 \\
\hfill --- S.}}

\newcommand{\p}[1]{\mathcal #1}
\renewcommand{\u}[1]{\underline{#1}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\R}{{\mathbb R}}

%\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{open}[theorem]{Open problem}
%\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
%\theoremstyle{remark}
\theoremstyle{definition}
\newtheorem{defin}[theorem]{Definition}
\newtheorem{alg}[theorem]{Algorithm}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}


\newcommand\scalemath[2]{\scalebox{#1}{\mbox{\ensuremath{\displaystyle #2}}}}

\newcommand{\rd}[1]{{\color{red} #1}}
\newcommand{\floor}[1]{\lfloor {#1} \rfloor}
\newcommand{\ceiling}[1]{\lceil {#1} \rceil}
\newcommand{\longto}{\longrightarrow}
\newcommand{\ASM}{\operatorname{ASM}}
\newcommand{\CSM}{\operatorname{CSM}}
\newcommand{\MT}{\operatorname{MT}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\quilt}{\operatorname{Quilts}}
\newcommand{\rank}{\operatorname{rank}}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\maxrank}{maxrank}
\DeclareMathOperator{\rk}{quiltrank}
\newcommand{\Matkn}{\mathcal{M}_{k \times n}(\mathbb{C})}
\newcommand{\Fullrk}{\mathcal{F}_{k \times n}(\mathbb{C})}
\newcommand{\W}{\mathcal{W}}
\newcommand{\given}{\, | \,}
\newcommand{\ber}{b}



%\date{\today}
%\author{\texorpdfstring{Sara C. Billey}{Sara C. Billey}}
%\author{\texorpdfstring{Matja\v z Konvalinka}{Matja\v z Konvalinka}}



%\newtheorem{thm}{Theorem}
%\newtheorem{lem}{Lemma}

\usepackage{lipsum}

%% define your title in the usual way
\title{Quilts of Alternating Sign Matrices}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author{\texorpdfstring{Sara Billey\thanks{\href{mailto:billey@uw.edu}{billey@uw.edu}}\addressmark{1} \and Matjaž Konvalinka\thanks{\href{mailto:matjaz.konvalinka@fmf.uni-lj.si}{matjaz.konvalinka@fmf.uni-lj.si}}\addressmark{2}}{Sara Billey and Matjaž Konvalinka}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of Washington, Seattle, WA, USA \\
\addressmark{2}Faculty of Mathematics and Physics, University of Ljubljana \& Institute for Mathematics, Physics and Mechanics, Ljubljana, Slovenia}

%% 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{In this extended abstract, we present new objects, \emph{quilts of
alternating sign matrices} with respect to two given posets. 
%%
 For example, the rank function on all submatrices of a matrix gives rise
to a quilt with respect to two Boolean lattices.
%%
When the two posets are chains, a quilt is equivalent to an
alternating sign matrix and its corresponding corner sum matrix.  Quilts
also generalize the monotone Boolean functions counted by the Dedekind
numbers.  They form a distributive lattice with many beautiful
properties and contain many classical and well known sublattices, such
as the lattice of matroids of a given rank and ground set.  While
enumerating quilts is hard in general, we prove two major enumerative
results, when one of the posets is an antichain and when one of them
is a chain. We also give some bounds for the number of quilts when one
poset is the Boolean lattice.}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Alternating sign matrices, Bruhat order, Dedekind numbers,
posets}

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

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

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

The \textit{rank} of a matrix is fundamental in mathematics, science,
and engineering.  The notion of rank can also be associated to graphs,
matroids, and partial orders.  One can refine the rank function to
submatrices, subgraphs, etc.\ as well to get a family of ranks to
associate to each object.  We observe that such families always follow
certain Boolean growth rules leading to the concept of a generalized
rank function, which we call a quilt.  The goal of this paper is to
consider families of generalized rank functions and their connection
with the well-studied alternating sign matrices (ASMs). We present
some applications and some related enumeration results.



The application that motivated us to study quilts comes from the
geometry of spanning line configurations and an analog of Bruhat order
based on a cell decomposition of that space used by Pawlowski and
Rhoades \cite{PR}.  They posed the problem of characterizing the
covering relations in the poset given by containment of cell closures.
While that problem is still open, the lattice of quilts on a chain
poset with a Boolean poset naturally contains the poset, now also
called the medium roast Fubini--Bruhat order
\cite{Billey-Ryan}.  Hence, we can use quilts to study the
vanishing flag minors defining the cell closures in the spanning line
configurations.  See the full length version of this abstract
\cite{Billey-Konvalinka-Quilts} for details. Note that due to length
limitations, we omit all proofs in this extended abstract.

\section{Background}\label{sec:background}

We recall some history and background to motivate the main new
concepts. See \cite{ASMs} for more background.  

If a matrix has $k$ rows and $n$ columns, we say it has \emph{size}
$k \times n$.  An \emph{alternating sign matrix} (or ASM for short) is
a matrix of size $k \times n$ with entries in $\{-1,0,1\}$ such that
in each row and each column the non-zero entries alternate, the
leftmost non-zero entry in every row and the bottommost non-zero entry
in every column is $1$, if $k \leq n$, the rightmost non-zero entry in
every row is $1$, and if $k \geq n$, the topmost non-zero entry in
every column is $1$.  In particular, if $n = k$, the non-zero entries
of every row and every column alternate and begin and end with $1$.
Note that what we call an ASM is typically called a \emph{rectangular}
or \emph{truncated} ASM in the literature; we will instead emphasize
that we have a \emph{square} ASM when $n = k$. Denote the set of all
ASMs of size $k \times n$ by $\ASM_{k,n}$.  For example, every
permutation matrix is a square ASM, but already for $n=3$ there are
more than $n!$ square ASMs.  A very famous result tells us that
$|\ASM_{n,n}| = \prod_{j=0}^{n-1} \frac{(3j+1)!}{(n+j)!}$.  See
\Cref{ex:rectangularASMs} for the asymptotics of $|\ASM_{k,n}|$.

Given $A=(a_{i,j}) \in \ASM_{k,n}$, we can define a new matrix
$C(A)=(c_{ij})$, called its \emph{corner sum matrix}, or CSM for
short, of size $(k+1) \times (n+1)$ by setting $c_{ij}=0$ if $i=k+1$
or $j=1$, and $c_{ij}=\sum_{i'=i}^{k}\sum_{j'=1}^{j}a_{i',j'}$ otherwise. For an
example, see \eqref{eq:anotherCSM}.  In the resulting matrix $C(A)$,
the entries change by $0$ or $1$ when moving to the right or up, and
the bottom row and the leftmost column always consist of
$0$'s. Furthermore, if $k \geq n$, the top row consists of $C_{n}=
\{0,1,\ldots,n \}$, and if $k \leq n$, the rightmost column consists
of $C_{k}=\{0,1,\ldots,k \}$. Conversely, given a matrix $B$, with
rows numbered $0,1,\ldots,k$ and starting at the bottom, and columns
numbered $0,1,\ldots,n$ and starting on the left, satisfying these
properties, the $k \times n$ matrix $A=(a_{ij})$ given by $a_{i,j}
=b_{i,j}-b_{i-1,j}-b_{i,j-1}+b_{i-1,j-1}$ for all $i\in [k]$ and $j\in
[n]$ is an ASM.  Therefore, we can equivalently define CSMs directly
as follows using the notation $(i,j) \lessdot (i',j')$ to mean the
covering relation in $C_k \times C_n$.

\begin{defin}\label{def:CSM}
A \emph{$(k,n)$-corner sum matrix (CSM)} is a map $f \colon C_k \times C_n
\longto \N$ satisfying:
\begin{itemize}
 \item $f(i,0) = 0$ for $i = 0,\ldots,k$,\ $f(0,j) = 0$ for $j = 0,\ldots,n$,
 \item $f(k,n) = \min\{k,n\}$, and
 \item if $(i,j) \lessdot (i',j')$ in $C_k \times C_n$, then $f(i',j') \in \{f(i,j),f(i,j)+1\}$.
\end{itemize}
Let $\CSM_{k,n}$ denote the set of all $(k,n)$-CSMs.  We
refer to the third condition in the definition of a CSM as a
\textit{Boolean growth rule}, which is a central concept in this
paper.
\end{defin}

One more way to think of ASMs/CSMs is as monotone
triangles (MTs). Given a CSM $f \colon C_k \times C_n \longto \N$,
record the positions of \emph{jumps} in each row, denoted by
\begin{equation}\label{eq:jumps}
J_f(i) = \{j \in [n] \colon f(i,j) = f(i,j-1) + 1\}.
\end{equation}
Then, the \emph{monotone triangle} (MT) corresponding to $f$ is the
``triangular array'' of jump sequences with rows $J_{f}(k), \dotsc,
J_{f}(2), J_{f}(1)$ (from top to bottom).   The rows of the monotone triangle are
\emph{interlacing} in the sense that if $J_f(i)=\{s_{1}<s_{2}<\cdots <
s_{p} \}$ and $ J_f(i+1)= \{t_{1}<t_{2}<\cdots < t_{q}\}$ then either
$p= q - 1$ and
\begin{equation}\label{eq:interlacing.1}
t_1 \leq s_1 \leq t_2 \leq s_2 \leq \dots \leq s_{q-1}
\leq t_{q},
\end{equation}
or $p=q$ and
\begin{equation}\label{eq:interlacing.2}
t_1 \leq s_1 \leq t_2 \leq s_2 \leq \dots
\leq t_{q} \leq s_{q}.
\end{equation}
Clearly, the original CSM can be recovered from its interlacing jump
sets by the Boolean growth property, so there are easy bijections
between the ASMs, CSMs, and MTs for given $k,n$.  For an example with
$k=5$ and $n=6$, consider 
\begin{tiny}
\begin{equation}\label{eq:anotherCSM}
A=\begin{bmatrix}
%0 & 0 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & -1 & 1 & 0 \\
1 & -1 & 0 & 1 & -1 & 1 \\
0 & 1  & 0 & -1 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0
\end{bmatrix},
\hspace{.2in}
C(A)=
\begin{bmatrix}
0 & 1 & 2 & 3 & 3 & 4 & 5 \\
0 & 1 & 1 & 2 & 3 & 3 & 4 \\
0 & 0 & 1  & 2 & 2 & 3 & 3 \\
0 & 0 & 0 & 1 & 2 & 2 & 2 \\
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix},
\hspace{.2in}
MT(A)=\begin{array}{ccccccccc} 1&&2&&3&&5&&6 \\ &1&&3&&4&&6& \\
&&2&&3&&5&& \\ &&&3&&4&&& \\ &&&&3.&&&& \end{array}
\end{equation}
\end{tiny}
%since the jump sequences are $J_f(0) = \emptyset$,
%$J_f(1) = \{3\}$, $J_f(2) = \{3,4\}$, $J_f(3) = \{2,3,5\}$, $J_f(4) =
%\{1,3,4,6\}$, $J_f(5) = \{1,2,3,5,6\}$.


%\caption{An ASM with its corresponding CSM and monotone triangle.}
%\label{eq:anotherCSM}
%\end{figure}
% $$\begin{array}{ccccccccc} 1&&2&&3&&5&&6 \\ &1&&3&&4&&6& \\
% &&2&&3&&5&& \\ &&&3&&4&&& \\ &&&&3.&&&& \end{array}
% $$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{remark}\label{rem:TerwilligerPoset}
Terwilliger introduced a poset $\Phi_{n}$ on the subsets of $[n]$ with
covering relations given by $S \lessdot T$ whenever $S$ and $T$ are
interlacing in the sense of \eqref{eq:interlacing.1}.  The poset
$\Phi_{n}$ contains the Boolean lattice $B_{n}$ as a subposet.  He
showed maximal chains in $\Phi_{n}$ are in bijection with $\ASM_{n,n}$,
just as the maximal chains of $B_{n}$ are in bijection with $S_{n}$
\cite[Theorem 3.4]{Terwilliger.2018}.  Building on this work, Hamaker and
Reiner \cite{hamakerreiner} showed that $\Phi_{n}$ is a shellable
poset, introduced a notion of descents for monotone triangles, and connected them to a
generalization of the Malvenuto--Reutenauer Hopf algebra of
permutations.  
\end{remark}

\section{Dedekind Maps and Quilts} \label{sec:def}

In this section, we introduce a generalization of the Dedekind
numbers, which count the number of monotone increasing Boolean
functions \cite[A000372]{oeis}.  Such functions are closely related to
the CSMs defined in \Cref{def:CSM} and are natural precursors to the
notion of a quilt defined later in this section. Assume all posets
below are finite, ranked, and have a unique minimal element $\hat 0$
and unique maximal element $\hat 1$.


\begin{defin}\label{def:Dedekin.map}
A \emph{Dedekind map of rank $k$} on a poset $P$ is a surjective map $f \colon
P \to C_k$ satisfying $x \lessdot y \Rightarrow f(y) \in
\{f(x),f(x)+1\}$.  The set of all Dedekind maps of rank $k$ on $P$ is
denoted by $D_k(P)$, their union by $D(P)$, and we write $d_k(P) =
|D_k(P)|$ and $d(P) = |D(P)| = \sum_k d_k(P)$ for the \emph{$k$th Dedekind number
of $P$} and \emph{Dedekind number of $P$}, respectively.
\end{defin}

\begin{example}\label{ex:matroid.dedekind}
 The rank function of a matroid on
ground set $[n]$ of rank $k$ is a Dedekind map of rank $k$ on the
Boolean lattice $B_{n}$.
\end{example}


Observe that for a Dedekind map of rank $k$, $f \colon P \to C_k$, the following
conditions are satisfied: $f(\hat 0) = 0$; $f(\hat 1) = k$; and if $x \lessdot y$, then $f(y) \in \{f(x),f(x)+1\}$ (Boolean growth). Consequently, $f(x) \leq \rank x$ for all $x \in P$. The $k$-Dedekind
number of a chain is $d_k(C_n) = \binom n k$.  For the antichain poset
$A_{2}(j)$, we have $d_1(A_2(j)) = 2^j$.

\begin{remark}\label{rem:sharp.P}
Given $f \in D_1(P)$, the set of minimal elements satisfying $f(x) =
1$ is a non-empty antichain in $P \setminus \{\hat 0\}$; so $d_1(P)$
counts the number of antichains in $P$ (except for $\emptyset$ and
$\{\hat 0\}$), which is a \#P-complete problem \cite{antichains}.
% SB says: now cutting non-essential references See also
%\cite{Sapozhenko} on antichain enumeration in ranked posets.
In particular, $d_1(B_n)+2$ is the classical Dedekind number and is
notoriously difficult to compute. The exact value for $n = 9$ was
first computed in 2023, thirty years after the value for $n=8$
\cite{JAKEL.2023}.
\end{remark}

\begin{lemma} \label{lemma:dedekindupper}
 For any poset $P$ and $k \geq 1$, we have $d_k(P) \leq d_1(P)^k$.
\end{lemma}



Every column of a CSM of size $(k+1) \times (n+1)$  can be seen as a Dedekind
map on $C_k$ and every row as a Dedekind map on $C_n$.  As one reads
left to right in columns or bottom to top in rows, another Boolean
growth rule must hold.  This second type of Boolean growth rule gives rise to the
following graphs.


\begin{defin}\label{def:Dedekind.graphs}
Let $G_D(P)$ denote the \emph{Dedekind graph of $P$}, defined as the
directed graph with vertex set given by the Dedekind maps in $D(P)$
and an edge from $f$ to $g$ if $g(x) \in \{f(x),f(x)+1\}$ for all $x
\in P$. The \emph{restricted Dedekind graph of $P$}, $G'_D(P)$, is the
directed graph with vertex set $D(P)$ and an edge from $f$ to $g$ if
$g(\hat 1_P) = f(\hat 1_P) + 1$ and $g(x) \in \{f(x),f(x)+1\}$ for all
$x \in P$.
\end{defin}


\begin{prop}\label{prop:Dedekind.walks}
For any $1\leq k\leq n $, the map between the set $CSM_{k,n}$ and the
set of walks in the Dedekind graph $G_{D}(C_{n})$ from its unique sink
to a vertex in $D_{k}(C_{n})$ determined by the consecutive list of
columns is a bijection.
\end{prop}

Recall the definition of interlacing sets and monotone triangles from
\Cref{sec:background}.  The Dedekind graph of a chain $C_{n}$ also
respects the interlacing conditions.  The next statement follows from
\Cref{prop:Dedekind.walks}. See \Cref{prop:interlacing} for more
connections with the interlacing conditions.


\begin{cor}\label{rem:interlacing}
The restricted Dedekind graph $G'_{D}(C_{n})$ is isomorphic to the
directed graph on $B_n$, with an edge from $S$ to $T$ if $|S| = |T| -
1$ and the sets $S$ and $T$ are interlacing: $t_1 \leq s_1 \leq t_2
\leq s_2 \leq \dots \leq s_{|T|-1} \leq t_{|T|}$. Similarly, the
Dedekind graph $G_D(C_n)$ is isomorphic to the directed graph on $B_n$,
edges as above plus an edge from $S$ to $T$ whenever $|S| = |T|$ and
$t_1 \leq s_1 \leq t_2 \leq s_2 \leq \dots \leq t_{|T|} \leq
s_{|T|}$.
\end{cor}

The following is the main definition of this paper.  It generalizes
the definition of a CSM in \Cref{def:CSM}.

\begin{defin} \label{def:quilt}
 Let $P$ and $Q$ be finite ranked posets with least and greatest
elements. A \emph{quilt of alternating sign matrices of type $(P,Q)$}
is a map $f \colon P \times Q \longto \N$ satisfying:
\begin{itemize}
 \item $f(x,\hat 0_Q) = 0$ for all $x \in P$,\ $f(\hat 0_P,y) = 0$ for all $y \in Q$,
 \item $f(\hat 1_P, \hat 1_Q) = \min\{\rank P,\ \rank Q\}$, and
 \item if $(x,y) \lessdot (x',y')$ in $P \times Q$, then $f(x',y') \in
 \{f(x,y),f(x,y)+1\}$ (Boolean growth).
\end{itemize}
We will also call such a map an \emph{ASM quilt} or just a
\emph{quilt} for short. The set of all quilts of type $(P,Q)$ will be denoted by $\quilt(P,Q)$.
\end{defin}

\begin{remark}\label{rem:ASMquiltname}
A quilt of type $(C_k, C_n)$ is a CSM on $C_k \times C_n$, so there
is also a corresponding ASM and MT. Similarly, for any $f \in
\quilt(P,Q)$ and any pair of maximal chains $\hat 0_P = x_0 \lessdot x_1 \lessdot \dots \lessdot x_{k-1} \lessdot
x_k = \hat 1_P$, $\hat 0_Q = y_0 \lessdot y_1 \lessdot \dots \lessdot y_{n-1} \lessdot y_n = \hat 1_Q$ in $P$ and $Q$, the map
$(i,j) \mapsto f(x_i,y_j)$ is a CSM on $C_k \times C_n$, which again
has a corresponding ASM and MT.  So we can think of quilts as encoding
collections of alternating sign matrices, one for each pair of maximal
chains in the two posets, appropriately ``pieced'' together like the
fabric of a quilt.%, hence the name ``ASM quilt''.
\end{remark}


\begin{example}\label{ex:all.minors.quil}
Let $M$ be a $k \times n$ matrix of full rank.  The function
$f_{M}:B_{k} \times B_{n} \longrightarrow \mathbb{N}$ given by setting
$f_{M}(I,J)$ to be the rank of the submatrix of $M$ in rows $I$ and
columns $J$ is a quilt of type $(B_{k}, B_{n})$.
\end{example}

The following lemma also shows that the entire rank function of the smaller ranked
poset is encoded in each quilt.  This justifies our claim that quilts
generalize rank functions of posets.


\begin{lemma}\label{lem:chains.bounds}
Let $f \in \quilt(P,Q)$.  If $\rank P \geq \rank Q$, then $f(\hat 1_P,y) = \rank_{Q}
y$ for all $y \in Q$.  If $\rank P \leq \rank Q$, then $f(x, \hat 1_{Q}) = \rank_{P} x$ for all $x \in P$.
\end{lemma}

 There is a natural partial order on $\quilt(P,Q)$: we say that $f
\leq g$ if $f(x,y) \leq g(x,y)$ for all $x \in P$, $y \in Q$. For $P =
C_k$, $Q = C_n$, this is the well-known partial order on the set of
CSMs or ASMs generalizing Bruhat order on the symmetric group
\cite{LS-MacNeille}. We will call $\quilt(P,Q)$ the \emph{quilt
lattice}, as justified by the following.

\begin{theorem} \label{thm:lattice}
Let $P,Q$ be finite ranked posets with least and greatest elements.
The poset $\quilt(P,Q)$ is a distributive lattice ranked by $$\rk f =
\sum_{x \in P,\, y \in Q} f(x,y) - \sum_{x \in P,\, y \in Q} f_{\hat
0}(x,y),$$ where $f_{\hat 0}(x,y) = \max\{0,\rank x + \rank y -
\max\{n,k\}\}$ is the least element of $\quilt(P,Q)$. The greatest
element of $\quilt(P,Q)$ is $f_{\hat 1}(x,y) = \min\{\rank x,\ \rank
y\}$.
\end{theorem}


As mentioned in the introduction, our motivating example comes from
vanishing flag minors where the posets are the Boolean lattice and the
other one is a chain.  We will call a quilt in $\quilt(P,C_n)$ or
$\quilt(C_n,P)$ a \emph{chain quilt}, a quilt in $\quilt(P,A_2(j))$ or
$\quilt(A_2(j),P)$ an \emph{antichain quilt}, a quilt in
$\quilt(P,B_n)$ or $\quilt(B_n,P)$ a \emph{Boolean quilt}.

There are three important ways to think of a chain quilt $f \in
\quilt(P,C_n)$. One is to see it as a sequence of Dedekind maps in
$D(P)$ that correspond with a walk in the Dedekind graph $G_D(P)$,
generalizing \Cref{prop:Dedekind.walks}. Another is to say that $f$
maps an arbitrary $x \in P$ to the sequence
$(f(x,0),f(x,1),\ldots,f(x,n))$ of length $n+1$. This sequence has the
property that every two consecutive elements are either equal or they
differ by one. We also have $f(y,i) \in \{f(x,i),f(x,i)+1\}$ when $x
\lessdot y$. The element $\hat 0_P$ is mapped to the zero sequence,
and the sequence corresponding to $\hat 1_P$ ends with $\min\{\rank
P,\ n\}$. 

Another equivalent, and probably even more intuitive, way to represent a chain quilt $f:P \times
C_{n} \longrightarrow \mathbb{N}$ is to say that it is a map that
sends $x \in P$ to the set of \emph{jumps of $f$ at $x$}, $J_f(x) =
\{ i \colon f(x,i) = f(x,i-1) + 1\} \subseteq [n]$. We will call this
the \emph{monotone triangle (MT) form} of the quilt $f$. It is easy
to go back from the MT form of a quilt: given $J:P \longrightarrow B_{n}$,
then $f(x,i)=|J(x)\cap [i]|$ defines $f \colon P \times C_n \longrightarrow \mathbb{N}$.
The Boolean growth condition translates into adjacent sets interlacing for quilts in MT form, see \Cref{prop:interlacing}.


 The first picture on the left in
\Cref{fig:quilts.2.5} shows an element
$f \in \quilt(B_3,C_2)$, where 
$$f(\{2 \},1)= f(\{1,2\},1) = f(\{2,3\},1) = f(\{1,2,3\},1) = 1$$ and
$f(T,1)=0$ for all other subsets $T$, while $f(\{2,3 \},2)=f(\{1,2,3
\},2)=2$.  The second picture is the MT form of $f$, where we omit
braces and commas for the sets.  The third picture in
\Cref{fig:quilts.2.5} represent a chain quilt $g \in \quilt(B_3,C_5)$.
Note how the top element of $f$ is $01\ldots n$, and the rightmost
element of every sequence in the picture for $g$ is equal to its rank,
as stated in \Cref{lem:chains.bounds}.  The fourth picture is the MT
form for $g$.




\begin{small}
\begin{figure}[ht]
\begin{center}
\scalemath{0.9}{\begin{tikzpicture}
\node (X0) at (0,0) {$000$};
\draw (-0.25,0.25) -- (-1.25,0.75);\draw (0,0.25) -- (0,0.75);\draw (0.25,0.25) -- (1.25,0.75);
\node (X11) at (-1.5,1) {$001$}; \node (X12) at (0,1) {$011$}; \node (X13) at (1.5,1) {$001$};
\draw (-1.5,1.25) -- (-1.5,1.75);\draw (-1.25,1.25) -- (-0.25,1.75);\draw (-0.25,1.25) -- (-1.25,1.75);\draw (0.25,1.25) -- (1.25,1.75);\draw (1.25,1.25) -- (0.25,1.75);\draw (1.5,1.25) -- (1.5,1.75);
\node (X21) at (-1.5,2) {$011$}; \node (X12) at (0,2) {$001$}; \node (X13) at (1.5,2) {$012$};
\draw (-0.25,2.75) -- (-1.25,2.25);\draw (0,2.75) -- (0,2.25);\draw (0.25,2.75) -- (1.25,2.25);
\node (X3) at (0,3) {$012$};
\end{tikzpicture}
\quad 
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.25,0.25) -- (-1.25,0.75);\draw (0,0.25) -- (0,0.75);\draw (0.25,0.25) -- (1.25,0.75);
\node (X11) at (-1.5,1) {$2$}; \node (X12) at (0,1) {$1$}; \node (X13) at (1.5,1) {$2$};
\draw (-1.5,1.25) -- (-1.5,1.75);\draw (-1.25,1.25) -- (-0.25,1.75);\draw (-0.25,1.25) -- (-1.25,1.75);\draw (0.25,1.25) -- (1.25,1.75);\draw (1.25,1.25) -- (0.25,1.75);\draw (1.5,1.25) -- (1.5,1.75);
\node (X21) at (-1.5,2) {$1$}; \node (X12) at (0,2) {$2$}; \node (X13) at (1.5,2) {$12$};
\draw (-0.25,2.75) -- (-1.25,2.25);\draw (0,2.75) -- (0,2.25);\draw (0.25,2.75) -- (1.25,2.25);
\node (X3) at (0,3) {$12$};
\end{tikzpicture}
\quad \quad
\begin{tikzpicture}
\node (X0) at (0,0) {$000000$};
\draw (-0.25,0.25) -- (-1.25,0.75);\draw (0,0.25) -- (0,0.75);\draw (0.25,0.25) -- (1.25,0.75);
\node (X11) at (-1.5,1) {$000111$}; \node (X12) at (0,1) {$001111$}; \node (X13) at (1.5,1) {$000001$};
\draw (-1.5,1.25) -- (-1.5,1.75);\draw (-1.25,1.25) -- (-0.25,1.75);\draw (-0.25,1.25) -- (-1.25,1.75);\draw (0.25,1.25) -- (1.25,1.75);\draw (1.25,1.25) -- (0.25,1.75);\draw (1.5,1.25) -- (1.5,1.75);
\node (X21) at (-1.5,2) {$001122$}; \node (X12) at (0,2) {$011112$}; \node (X13) at (1.5,2) {$001112$};
\draw (-0.25,2.75) -- (-1.25,2.25);\draw (0,2.75) -- (0,2.25);\draw (0.25,2.75) -- (1.25,2.25);
\node (X3) at (0,3) {$011123$};
\end{tikzpicture}
\qquad
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.25,0.25) -- (-1.25,0.75);\draw (0,0.25) -- (0,0.75);\draw (0.25,0.25) -- (1.25,0.75);
\node (X11) at (-1.5,1) {$3$}; \node (X12) at (0,1) {$2$}; \node (X13) at (1.5,1) {$5$};
\draw (-1.5,1.25) -- (-1.5,1.75);\draw (-1.25,1.25) -- (-0.25,1.75);\draw (-0.25,1.25) -- (-1.25,1.75);\draw (0.25,1.25) -- (1.25,1.75);\draw (1.25,1.25) -- (0.25,1.75);\draw (1.5,1.25) -- (1.5,1.75);
\node (X21) at (-1.5,2) {$24$}; \node (X12) at (0,2) {$15$}; \node (X13) at (1.5,2) {$25$};
\draw (-0.25,2.75) -- (-1.25,2.25);\draw (0,2.75) -- (0,2.25);\draw (0.25,2.75) -- (1.25,2.25);
\node (X3) at (0,3) {$145$};
\end{tikzpicture}}
\end{center}
\caption{Two ways to visualize quilts of types $(B_{3},C_{2})$ and
$(B_{3},C_{5})$.} \label{fig:quilts.2.5}
\end{figure}
\end{small}


%% SB says:  This must have been lingering but unfinished so I'm
%% cutting it.
% The following shows the two quilts from \Cref{fig:quilts.2.5} in MT form, where we
% omit braces and commas for sets since all integers are below $10$.

% \begin{center}

% \end{center}

\begin{prop} \label{prop:interlacing}
 Take $f \in \quilt(P,C_n)$. For all $x,y \in P$ with $x \lessdot y$,
the sets $S = J_f(x)$ and $T = J_f(y)$ are interlacing as in
\eqref{eq:interlacing.1} and \eqref{eq:interlacing.2}.  When $n \leq
\rank P$, $ J_f(\hat 1_P) = [n]$. When $n \geq \rank P$, we have
$|J_{f}(x)| = \rank x$ for all $x \in P$.
\end{prop}

The general problem of enumerating quilts is hard, as the following
theorem shows.

\begin{theorem} \label{thm:complexity}
 Computing $|\quilt(P,Q)|$ for general $P$ and $Q$ is a \#P-complete problem.
\end{theorem}

Even though computing $|\quilt(P,Q)|$ for general $P$ and $Q$ is
out of reach, we do have a simple upper bound.  Let  $b(P) = \sum_{x \in P}
\rank x$.

\begin{theorem} \label{thm:upperbound}
 If $\rank P \leq \rank Q$, then $|\quilt(P,Q)| \leq d_1(Q)^{b(P)}$.
\end{theorem}

Observe from the definitions that for all posets $P,Q$ with $\rank P =
k$ and $\rank Q = n$, the map $\iota \colon \CSM_{k,n} \longto
\quilt(P,Q)$ given by $\iota(f)(x,y) = f(\rank x,\ \rank y)$ is a
lattice embedding.  The lattice $\quilt(C_k,B_n)$, $n \geq k$, also
contains (among others) the following three overlapping subposets:
\begin{itemize}
\item Matroids on ground set $[n]$ with rank $k$ are embedded into
$\quilt(C_k,B_n)$ via the map that sends a matroid on $[n]$ to the
quilt $f:C_{k}\times B_{n} \longrightarrow \mathbb{N}$ with $f(i,T) =
\min\{i,\ \rank T\}$, where $\rank T$ is the cardinality of the largest
independent set contained in $T$.
\item The rank functions of flag matroids $\mathcal{M}$ on the ground set
$[n]$ with ranks $\mathbf{k}=(k_1, \ldots ,k_s)$ and rank functions
$\rank_1,\ldots, \rank_s$ can also be encoded as a Boolean-chain
quilt. Specifically, the embedding into $\quilt(C_{k_{s}},B_n)$ is
given by 
$f_{\mathcal{M}}(i,X)$ is either 
$\min\{ i, \rank_1 X\}$ if  $1\leq i\leq k_{1}$ or 
$\min\{ \rank_j X +i-k_{j} , \rank_{j+1} X\}$ if 
$k_{j}< i\leq k_{j+1}, 1 \leq j \leq s-1.$
\item The medium roast Fubini--Bruhat order embeds into
$\quilt(C_k,B_n)$ via northerly rank conditions \cite{Billey-Ryan}.
\end{itemize}


\begin{theorem}
 Let $P$ and $Q$ be finite ranked posets with least and greatest
elements. If $\varphi$ is an (involutive) antiautomorphism of $P$, $\rank P \geq \rank Q$, then $\Phi \colon \quilt(P,Q) \to \quilt(P,Q)$, where $\Phi f(x,y) = \rank y - f(\varphi(x), y)$, is an (involutive) antiautomorphism of the lattice $\quilt(P,Q)$. Given an involutive antiautomorphism $\varphi \colon P \to P$, there is an action of the dihedral group $D_4$ acting on $\quilt(P,P)$ that sends the horizontal reflection of the square to $\Phi$ and the diagonal reflection of the square to $\Sigma$. If $\rank P \geq 2$, the action is faithful.
\end{theorem}

Take posets $P_1$ and $P_2$ with the same rank. The \emph{disjoint union} $P_1 + P_2$ is the poset we get by ``merging'' $\hat 0_{P_1}$ with $\hat 0_{P_2}$ and $\hat 1_{P_1}$ with $\hat 1_{P_2}$, and adding the other elements of $P_1$ and $P_2$ without any new relations. For example, $A_2(j_1) + A_2(j_2)$ is isomorphic to $A_2(j_1 + j_2)$. Write $j P$ for the disjoint union of $j$ copies of $P$. For example, $A_2(j) = j C_2$.

\begin{prop}
 Assume that $\rank P_1 = \rank P_2 \geq \rank Q$. Then the map
 $$\Theta \colon \quilt(P_1 + P_2, Q) \longto \quilt(P_1, Q) \times \quilt(P_2, Q)$$
 defined by $f \mapsto (f_1,f_2)$, $f_i(x_i,y) = f(x_i,y)$ for $x_i \in P_i, y \in Q$, is an isomorphism of lattices.
\end{prop}


\begin{cor} \label{cor:powerofasm}
 For $k \geq n$ and arbitrary positive integer $j$, $|\quilt(j C_k,
C_n)| = |\ASM_{k \times n}|^{j}$. For any $i,j,n$, we have $|\quilt(i
C_n, j C_n)| = |\ASM_{n \times n}|^{ij}$.
\end{cor}

\section{Enumerative results}

\subsection{Enumeration of antichain quilts} \label{sec:antichain}

%1, 4, 199, 3813042, 410131245
We next consider the case of counting the number of quilts of type
$(P,Q)$ when $Q$ is an antichain poset.  The enumeration is in terms
of the number of antichains in convex cut sets of $P$.  We say that a
subset $S$ of a poset $P$ is \emph{convex} if $x,y \in S$ implies
$[x,y] \subseteq S$. We say that $S$ is a \emph{cut set} if it
intersects every maximal chain in $P$. If you have a convex cut set
$C$, it makes sense to say that an element $x \in P \setminus C$ is
\emph{above $C$} or \emph{below $C$}: $x$ lies on a maximal chain, the
maximal chain intersects $C$ in some element $x'$, and $x$ is above
$C$ if $x > x'$ and below $C$ if $x < x'$. This is well defined, as
$x' < x < x''$ for $x',x'' \in C$ would imply $x \in C$. For example,
if $\rank P \geq 2$, then $C=P \setminus \{\hat 0_P, \hat 1_P\}$ is a
convex cut set, $\hat 0_P$ is below $C$, and $\hat 1_P$ is above $C$.


Recall from \Cref{rem:sharp.P} that $d_1(P)$ counts the number of nonempty
antichains in $P$ other than $\{\hat 0\}$. Such antichains are in
bijection with antichains in $P \setminus \{\hat 0_P, \hat 1_P\}$.
For any $S \subseteq P$, denote by $\alpha_P(S)$ the number of
antichains in $S$.  Then, we have $\alpha_P(P \setminus \{\hat 0_P,
\hat 1_P\}) = d_1(P)$.  Given two infinite sequences $(a_{n})$ and
$(b_{n})$, we write $a_{n} \sim b_{n}$ to mean $a_{n}/b_{n}
\rightarrow 1$ as $n$ goes to infinity.


\begin{theorem} \label{thm:antichain}
 Take a ranked poset $P$ with least and greatest elements, $\rank P \geq 2$, and $j \geq 1$. We have
 \begin{equation} \label{eq:antichain}
 |\quilt(P,A_2(j))| = \sum_C \alpha_P(C)^j,
 \end{equation}
 where the sum is over all subsets $C$ of $P \setminus \{\hat 0_P,\hat
 1_P\}$ that are convex cut sets of $P$. In particular, as $j$ goes to
 infinity, we have $|\quilt(P,A_2(j))| \sim  d_1(P)^j$.
\end{theorem}


\begin{cor} \label{prop:chainbyantichain}
 We have $|\quilt(C_k,A_2(j))| = \sum_{i=2}^k (k+1-i)i^j$ for $j \geq 1$, $k \geq 2$.
 \end{cor}

\subsection{Enumeration of chain quilts} \label{sec:chain}

% Given a finite poset $P$, we will consider the enumeration of chain
% quilts $\quilt(P,C_{n})$ in this section. The formulas are in terms
% of \emph{fundamental} and \emph{standard} quilts for $P$.  We begin
% with some additional notation and vocabulary.

Recall that $b(P) = \sum_{x \in P} \rank x$. If $f \in
\quilt(P,C_{b(P)})$, we say that $i \in [b(P)]$ is a \emph{jump for
$f$} if there exists $x \in P$ so that $f(x,i) = f(x,i-1) + 1$. If the
set of jumps of $f$ is equal to $[m]$, we say that $f$ is
\emph{$m$-fundamental for $P$}. A \emph{standard} quilt is one that is
$b(P)$-fundamental. Let $F_m(P)$ be the set of all $m$-fundamental
quilts for $P$. Let $S(P) = F_{b(P)}$ and $F(P) = \bigcup_m F_m(P)$.
Observe that a chain quilt is $m$-fundamental if and only if its MT form
contains precisely the elements $1,\ldots,m$. In particular, it is
standard if and only if its MT form contains exactly one of each of
$1,\ldots,b(P)$.

\begin{theorem}  \label{thm:chainenumeration}
 For a fixed poset $P$ of rank $k$ with least and greatest elements
and any integer $n \geq k$, the number of chain quilts of type $(P,
C_{n})$ is given by a polynomial in $n$. Namely, 
\begin{equation} \label{eq:chainenumeration}
|\quilt(P, C_n)| = \sum_{m = k}^{b(P)} |F_m(P)| \binom n
m \sim \frac{|S(P)|}{b(P)!}
\cdot n^{b(P)}.  \end{equation}
\end{theorem}

\begin{example}

Consider $P = B_2$.  We have $b(P) =
4$, and there are four $2$-fundamental, five $3$-fundamental, and two
$4$-fundamental (standard) quilts, presented here in MT form. 
\begin{small}
 \begin{center}
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.1,0.25) -- (-0.3,0.75);\draw (0.1,0.25) -- (0.3,0.75);
\node (X11) at (-0.4,1) {$1$}; \node (X12) at (0.4,1) {$1$\:};
\draw (-0.3,1.25) -- (-0.1,1.75);\draw (0.3,1.25) -- (0.1,1.75);
\node (X2) at (0,2) {$12$};
\end{tikzpicture}
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.1,0.25) -- (-0.3,0.75);\draw (0.1,0.25) -- (0.3,0.75);
\node (X11) at (-0.4,1) {$1$}; \node (X12) at (0.4,1) {$2$\:};
\draw (-0.3,1.25) -- (-0.1,1.75);\draw (0.3,1.25) -- (0.1,1.75);
\node (X2) at (0,2) {$12$};
\end{tikzpicture}
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.1,0.25) -- (-0.3,0.75);\draw (0.1,0.25) -- (0.3,0.75);
\node (X11) at (-0.4,1) {$2$}; \node (X12) at (0.4,1) {$1$\:};
\draw (-0.3,1.25) -- (-0.1,1.75);\draw (0.3,1.25) -- (0.1,1.75);
\node (X2) at (0,2) {$12$};
\end{tikzpicture}
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.1,0.25) -- (-0.3,0.75);\draw (0.1,0.25) -- (0.3,0.75);
\node (X11) at (-0.4,1) {$2$}; \node (X12) at (0.4,1) {$2$\:};
\draw (-0.3,1.25) -- (-0.1,1.75);\draw (0.3,1.25) -- (0.1,1.75);
\node (X2) at (0,2) {$12$};
\end{tikzpicture}
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.1,0.25) -- (-0.3,0.75);\draw (0.1,0.25) -- (0.3,0.75);
\node (X11) at (-0.4,1) {$1$}; \node (X12) at (0.4,1) {$2$\:};
\draw (-0.3,1.25) -- (-0.1,1.75);\draw (0.3,1.25) -- (0.1,1.75);
\node (X2) at (0,2) {$13$};
\end{tikzpicture}
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.1,0.25) -- (-0.3,0.75);\draw (0.1,0.25) -- (0.3,0.75);
\node (X11) at (-0.4,1) {$2$}; \node (X12) at (0.4,1) {$1$\:};
\draw (-0.3,1.25) -- (-0.1,1.75);\draw (0.3,1.25) -- (0.1,1.75);
\node (X2) at (0,2) {$13$};
\end{tikzpicture}
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.1,0.25) -- (-0.3,0.75);\draw (0.1,0.25) -- (0.3,0.75);
\node (X11) at (-0.4,1) {$2$}; \node (X12) at (0.4,1) {$2$\:};
\draw (-0.3,1.25) -- (-0.1,1.75);\draw (0.3,1.25) -- (0.1,1.75);
\node (X2) at (0,2) {$13$};
\end{tikzpicture}
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.1,0.25) -- (-0.3,0.75);\draw (0.1,0.25) -- (0.3,0.75);
\node (X11) at (-0.4,1) {$2$}; \node (X12) at (0.4,1) {$3$\:};
\draw (-0.3,1.25) -- (-0.1,1.75);\draw (0.3,1.25) -- (0.1,1.75);
\node (X2) at (0,2) {$13$};
\end{tikzpicture}
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.1,0.25) -- (-0.3,0.75);\draw (0.1,0.25) -- (0.3,0.75);
\node (X11) at (-0.4,1) {$3$}; \node (X12) at (0.4,1) {$2$\:};
\draw (-0.3,1.25) -- (-0.1,1.75);\draw (0.3,1.25) -- (0.1,1.75);
\node (X2) at (0,2) {$13$};
\end{tikzpicture}
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.1,0.25) -- (-0.3,0.75);\draw (0.1,0.25) -- (0.3,0.75);
\node (X11) at (-0.4,1) {$2$}; \node (X12) at (0.4,1) {$3$\:};
\draw (-0.3,1.25) -- (-0.1,1.75);\draw (0.3,1.25) -- (0.1,1.75);
\node (X2) at (0,2) {$14$};
\end{tikzpicture}
\begin{tikzpicture}
\node (X0) at (0,0) {$\emptyset$};
\draw (-0.1,0.25) -- (-0.3,0.75);\draw (0.1,0.25) -- (0.3,0.75);
\node (X11) at (-0.4,1) {$3$}; \node (X12) at (0.4,1) {$2$};
\draw (-0.3,1.25) -- (-0.1,1.75);\draw (0.3,1.25) -- (0.1,1.75);
\node (X2) at (0,2) {$14$};
\end{tikzpicture}
\end{center}%\caption{All fundamental quilts for $B_2$.} \label{fig:fundamentalB2}
\end{small}
Therefore it follows from \Cref{thm:chainenumeration} that for $n \geq 2$,
 $$|\quilt(B_2,C_n)| = 4 \binom n 2 + 5 \binom n 3 + 2 \binom n 4 = \frac{n^4}{12}+\frac{n^3}{3}+\frac{5 n^2}{12}-\frac{5 n}{6} \sim 2 \cdot \frac{n^4}{4!}.$$
\end{example}

\begin{example} \label{ex:rectangularASMs}
 We can think of a standard quilt for $P = C_k$ as a monotone triangle (in the classical sense) in which all numbers $1,\ldots,\binom{k+1}2$ appear. After an up-down reflection and a $45^\circ$ rotation, we get a shifted standard Young tableau of shape $(k,k-1,\ldots,1)$. For example, for $k=3$, we get monotone triangles $\begin{smallmatrix} 1&&3&&6 \\ &2&&5& \\ &&4&& \end{smallmatrix}$ and $\begin{smallmatrix} 1&&4&&6 \\ &2&&5& \\ &&3&& \end{smallmatrix}$ and shifted standard Young tableaux $\begin{smallmatrix} 1 & 2 & 4 \\ & 3 & 5 \\ & & 6 \end{smallmatrix}$ and $\begin{smallmatrix} 1 & 2 & 3 \\ & 4 & 5 \\ & & 6 \end{smallmatrix}$. The hook-length formula for shifted standard Young tableaux \cite{Thr} gives (for fixed $k$ and $n \to \infty$) $|\ASM_{k,n}| \sim \frac{\prod_{i=0}^{k-1} (2i)!}{\prod_{i=0}^{k-1} (k + i)!} \cdot n^{\binom{k+1}2}$.
\end{example}


There is in fact one more way to compute $|\quilt(P,C_n)|$ and prove
the polynomiality property via the  Transfer-Matrix Method
\cite[Theorem 4.7.2]{ec1}  using the adjacency matrix $A_D(P)$ of the
Dedekind graph of $P$ defined in \Cref{def:Dedekind.graphs}.


\begin{theorem} \label{thm:graph}
 For a finite poset $P$ of rank $k\geq 1$ with least and greatest elements,  we have
\begin{equation}\label{eq:transfer.1}
\sum_{n=k}^\infty |\quilt(P, C_n)|  x^n = (I - x
 A_D(P))^{-1}_{1,d(P)} = \frac{(-1)^{d(P)-1}}{(1-x)^{d(P)}} \det T(P),
\end{equation}
 where $T(P)$ is the transfer-matrix $I - x A_D(P)$ with the
the column indexing the unique source and the row indexing the unique
sink in $G_D(P)$ removed.
%the first column and last row removed.
In particular, the sequence
 $0,0,\ldots,0$, $|\quilt(P, C_k)|, |\quilt(P, C_{k+1})|,\ldots$ is given
 by a polynomial of degree $< d(P)$.
 Furthermore,
\begin{equation}\label{eq:transfer.2}
\sum_{n=0}^{k-1} |\quilt(P, C_n)| x^n = \sum_{i=1}^{d(P)-1} (I - x A'_D(P))^{-1}_{1,i} =  \sum_{i=1}^{d(P)-1} (-1)^{i-1} \det T'(P)_i,
\end{equation}
  where $T'(P)_i$ is the matrix $I - x A'_D(P)$ with the source column and $i$-th row removed.
\end{theorem}


There is an easy bijection between $k \times n$ ASMs and monotone
triangles with all possible length $k$ top row sequences.  Such a top
row sequence will be denoted by $(a_1,\ldots,a_k)$ with $1 \leq a_1 <
a_2 < \dots < a_k \leq n$. Fischer proved that the cardinality of
$\MT(a_1,\ldots,a_k)$, the set of monotone triangles with top row
$(a_1,\ldots,a_k)$, is a polynomial in variables $a_1,\ldots,a_k$, and
she also found an explicit (operator) formula for
$|\MT(a_1,\ldots,a_k)|$, see \cite{MTs}. The definition can be
extended to arbitrary chain quilts: given a poset $P$ of rank $k$ and
$1 \leq a_1 < a_2 < \dots < a_k \leq n$, define
$\MT_P(a_1,\ldots,a_k)$ as the set of quilts $f \in \quilt(P,C_n)$ for
which $J_f(\hat 1_P) = \{a_1,\ldots,a_k\}$.  Let $J_f(\hat 1_P)_i$ denote the
$i$-th largest element of the set.

\begin{theorem} \label{thm:mt}
 For a finite poset $P$ of rank $k$ with least and greatest elements,
we have \begin{equation} \label{eq:mt} |\MT_P(a_1,\ldots,a_k)| =
\sum_{f \in F(P)} \prod_{i=2}^k \binom{a_i-a_{i-1}-1}{J_f(\hat 1_P)_i -
J_f(\hat 1_P)_{i-1}-1}, \end{equation} 
\end{theorem}



\subsection{Enumeration of Boolean quilts} \label{sec:boolean}

Exact enumeration of Dedekind maps for $B_{n}$ and Boolean quilts is at least as difficult as
finding a formula for the Dedekind numbers. However, some bounds can
be given. For example, we can construct $2^{\binom n{\floor{n/2}}}$
$1$-Dedekind maps on $B_{n}$ by taking $f(T) = 0$ for $|T| <
\floor{n/2}$, $f(T) = 1$ for $|T| > \floor{n/2}$, $f(T) \in \{0,1\}$
for $|T| = \floor{n/2}$. It follows that $d_1(B_n) \geq 2^{\binom
n{\floor{n/2}}}$.
%SB says: now cutting non-essential references
% In 1966, Hansel proved that $d_1(B_n) \leq 3^{\binom n{\floor{n/2}}}$
% \cite{hansel}.
Kleitman \cite{kleitman} proved the upper bound $d_1(B_n) \leq 2^{(1+c \ln n/\sqrt n)\binom{n}{\floor{n/2}}}$ for some constant $c$. We use that result for the following.


\begin{lemma} \label{lem:booleandedekind}
 There exists a constant $c > 0$ so that $d_k(B_n) \leq 2^{k(1+c \ln n/\sqrt n)\binom{n}{\floor{n/2}} }$ for all $1\leq k\leq n$. Furthermore, for every $\varepsilon > 0$, $d_k(B_n) \geq 2^{(k-\varepsilon) \binom n {\floor{n/2}}}$ for large enough $n$.
\end{lemma}

\begin{theorem}\label{thm:bounds}
Let $P$ be a finite ranked poset with least and greatest
elements. There exists a constant $c>0$ so that $2^{\binom n{\floor{n/2}}} \leq |\quilt(P,B_n)| \leq
2^{b(P) (1+c \ln n/\sqrt n)\binom n{\floor{n/2}}}$ if $n \geq \rank P$. If $n \geq 2
\rank P$, we have the improved lower bound $|\quilt(P,B_n)| \geq d_1(P)^{\binom
n{\floor{n/2}}}$.
In particular, $$ 2^{\binom
k{\floor{k/2}} \binom n{\floor{n/2}}}\leq |\quilt(B_k,B_n)| \leq
2^{k2^{k-1} (1+c \ln n/\sqrt n)\binom n{\floor{n/2}}} \qquad \mbox{for } n \geq 2k.$$
\end{theorem}



\begin{remark}
\Cref{thm:bounds}  guarantees that for a poset $P$, there are positive numbers $A_P$ and $B_P$ such that $(\ln |\quilt(P,B_n)|)/\binom{n}{\floor{n/2}} \in [A_P,B_P]$ for $n \geq \rank P$.  It is natural to ask if the limit $L(P) = \lim_{n \to \infty} {\ln |\quilt(P,B_n)|/}{\binom{n}{\floor{n/2}}}$ exists. By the last part of the theorem, if $L(B_k)$ exists, it must be in the interval $\left[\binom k{\floor{k/2}} \ln 2, k2^{k-1} \ln 2\right]$. We do not have enough data to state an explicit conjecture, but we believe that the limit does indeed exist; if we had to venture a guess as to what this number would be, we would say $L(P) = b(P) \ln 2$. In other words, we believe that $2^{b(P) \binom n{\floor{n/2}}}$ is the best estimate for $|\quilt(P,B_n)|$ among functions of the form $C^{\binom n{\floor{n/2}}}$.
\end{remark}

\section{Final remarks} \label{sec:final}

In this section, we discuss some possible avenues for future research.

\textbf{Representability.} Call a quilt $f \in
\quilt(B_k, B_n)$ \emph{representable} if there exists a matrix $A \in
\R^{k \times n}$, $\rank A = \min\{k,n\}$, so that $f(I,J)$ is equal
to the rank of the matrix obtained by taking rows in $I$ and columns
in $J$ in the matrix $A$. It would be interesting to characterize the representable quilts of type $(B_{k}, B_{n})$.

%%SB says: we didn't discuss this enough here to be understandable yet.
% \textbf{Dedekind--MacNeille completion.} What is the Dedekind--MacNeille
% completion of the medium roast Fubini--Bruhat partial order?  
% This complete lattice must be
% isomorphic to a sublattice of $\quilt(C_{k},B_{n})$ and contain the
% quilts of the form $f_{w}$ for $w \in W_{n,k}$. It would also be interesting to find the Dedekind--MacNeille completion of the poset of representable quilts of type $(B_{k},B_{n})$.

\textbf{Quilt polytopes.} There are beautiful results about the polytopes of alternating sign
matrices, matroids, and flag matroids, see e.g.~\cite{striker} and
\cite{CAMERON.DINU.MICHALEK.SEYNNAEVE}.  In 2018, Sanyal--Stump
\cite{Sanyal-Stump.2018} defined the \emph{Lipschitz polytope} of a
poset $P$, denoted $\mathcal{L}(P)$, as the set of functions $f \in
\mathbb{R}^{P}$ such that $ 0\leq f(a)\leq 1$ for all minimal elements
$a \in P$ and $0\leq f(y)-f(x)\leq 1 $ for all $x \lessdot y$ in $P$.
Therefore, the vertices of the Lipschitz polytopes are closely related
to the Dedekind maps on $P$.  This variation on Boolean growth leads
us to define $\mathcal{L}(P,Q)$ for a pair of finite ranked posets
$P,Q$ with least and greatest as the set of functions $f \in
\mathbb{R}^{P\times Q}$ satisfying the boundary conditions $f(x,\hat 0_Q) =0$ for all $x \in P$, $f(\hat 0_P,y) =0$ for
all $y \in Q$, $f(\hat 1_P, \hat 1_Q) = \min\{\rank P,\  \rank
Q\}$, and $0\leq f(x',y')-f(x,y)\leq 1$ if $(x,y) \lessdot (x',y')$ in $P \times Q$ (bounded growth).
Thus, integer lattice points of $\mathcal{L}(P,Q)$ are exactly the
quilts of type $(P,Q)$.  What is the Ehrhart polynomial for these
generalized Lipschitz polytopes?  What more can be said about these
polytopes?

\textbf{Enumeration.} As we stated in the introduction, one of the
most fascinating facts in the area is that there is a product formula
for the number of square ASMs. \Cref{cor:powerofasm} gives a
simple generalization of this statement. Is there a simple formula for
$|\quilt(P,P)|$ for some family of posets $P \neq j C_n$? Can we at
least find asymptotic formulas for $|\quilt(P_n,P_n)|$ for some nice
families of posets $P_n$, or upper and lower estimates?  Can we
improve the bounds for $|\quilt(P,B_n)|$ beyond \Cref{thm:bounds}?

%% SB says: Also a bit more technical than what is written here.
% \textbf{Monotone triangles.} In \Cref{sec:chain}, we proved
% that $m_P(a_1,\ldots,a_k)=|\MT_P(a_1,\ldots,a_k)|$ is a polynomial
% function of $a_{1},\dotsc ,a_{k}$. For $P = C_k$, the crucial results
% are the \emph{operator formula}, expressing the number of monotone
% triangles via the number of Gelfand--Tsetlin patterns, and the
% \emph{rotation formula}, which states that
% $m_{C_k}(a_2,\ldots,a_k,a_1-k)| = (-1)^{k-1} m_{C_k}(a_1,\ldots,a_k)$,
% see~\cite[Theorem 1]{MTs} and~\cite[Lemma 5]{Fischer.2005}. Is there a
% way to generalize these results to arbitrary (or at least some)
% posets?

\textbf{Generalizing ASM.} The literature on permutations and
alternating sign matrices provide a rich source of problems for
quilts, some of which are mentioned in the introduction and
\Cref{rem:TerwilligerPoset}. What can be said about the interlacing
Boolean lattice with both types of interlacing conditions?  Following
Hamaker--Reiner \cite{hamakerreiner}, what are the descents for
quilts? Can we generalize their result on shellability to an (appropriately defined) Dedekind poset?   Is there a Hopf algebra
interpretation for quilts and an analog of the shuffle product?  See
also the work of Cheballah--Giraudo--Maurice, who defined a Hopf
algebra with basis given by alternating sign matrices \cite{CGM}.

%% Is $\quilt(P,Q)$ a shellable poset?

%%SB says: editing
% We could also consider generalizing Terwilliger's extension of the
% Boolean lattice to include interlacing sets not just of the type in
% \eqref{eq:interlacing.1}, but also to include
% \eqref{eq:interlacing.2}.  What can be said about the interlacing
% Boolean lattice with both types of interlacing conditions?

% Mills--Robbins--Rumsey gave two analogs of the number of inversions of
% an ASM.  The one that determines the rank of an ASM $A$ in the poset
% is
% \begin{equation}\label{eq:MRR.inv}
% \inv(A)=\sum_{i<r,j>s} a_{ij}a_{rs}.
% \end{equation}
% We know the rank of a quilt is given in \Cref{thm:lattice} by
% \[
% \rk f
% = \sum_{x \in P,y \in Q} f(x,y) - \sum_{x \in P,y \in Q} f_{\hat
% 0}(x,y).
% \]
% Is there an ASM form of a quilt that could be useful in some way and
% give rise to an inversion formula generalizing \eqref{eq:MRR.inv}?


% How do flips and compatible pairs from Robbin--Rumsey
% \cite[p. 172]{Robbins-Rumsey} relate to the realizablility of a family
% of ASMs as a quilt?



\acknowledgements{We would like to thank Anders Claesson, Herman Chau, Ilse Fischer, Hans
H\"ongesberg, Stark Ryan, Raman Sanyal, Jessica Striker, and Joshua
Swanson for helpful conversations.}

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



\end{document}
