\documentclass[final]{FPSAC2022}

\usepackage{tabu}
\usepackage{makecell}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
\newtheorem{question}[theorem]{Question}

\theoremstyle{definition}
\newtheorem{definition}{Definition}
\theoremstyle{remark}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}


\usepackage{mathrsfs}

\usepackage{tikz}
\usetikzlibrary{calc,through,backgrounds,shapes,matrix}

\newcommand{\defn}[1]{\textcolor{blue}{\emph{#1}}}

\newcommand{\defs}{\overset{\mathsf{def}}{=}}

\newcommand{\row}{\mathsf{Row}}
\newcommand{\pop}{\mathsf{Pop}^\downarrow}
\newcommand{\popdown}{\mathsf{Pop}^\downarrow}
\newcommand{\popup}{\mathsf{Pop}^\uparrow}
\newcommand{\D}{\mathcal{D}}
\newcommand{\U}{\mathcal{U}}
\newcommand{\DR}{\overline{\mathcal{D}}}
\newcommand{\UR}{\overline{\mathcal{U}}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\I}{\mathrm{Ind}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\In}{\mathrm{In}}
\newcommand{\Out}{\mathrm{Out}}
\newcommand{\face}{\mathrm{Face}}
\newcommand{\shard}{\mathrm{Shard}}
\newcommand{\popnone}{\mathsf{Pop}}

\title{Semidistrim Lattices}

\author[C.~Defant and N.~Williams]{Colin Defant\thanks{\href{mailto:cdefant@princeton.edu}{cdefant@princeton.edu}. Supported by a Fannie and John Hertz Foundation Fellowship and an NSF Graduate Research Fellowship.}\addressmark{1} \and
Nathan Williams\thanks{\href{mailto:nathan.williams1@utdallas.edu}{nathan.williams1@utdallas.edu}. Supported by a Simons Foundation Collaboration Grant.}\addressmark{2}}

\address{\addressmark{1}Department of Mathematics, Princeton University, Princeton, NJ \\
\addressmark{2}Department of Mathematical Sciences, University of Texas at Dallas, Dallas, TX}

\received{}


%\revised{}

\abstract{We introduce \emph{semidistrim lattices}, a simultaneous generalization of semidistributive and trim lattices that preserves many of their common properties.  We prove that the elements of a semidistrim lattice correspond to the independent sets in an associated graph called the \emph{Galois graph}, that products and intervals of semidistrim lattices are semidistrim, and that the order complex of a semidistrim lattice is either contractible or homotopy equivalent to a sphere. Semidistrim lattices have a natural \emph{rowmotion} operator, which simultaneously generalizes Barnard's $\overline\kappa$ map on semidistributive lattices as well as Thomas and the second author's rowmotion on trim lattices.  Every lattice has an associated \emph{pop-stack sorting} operator that sends an element $x$ to the meet of the elements covered by $x$. For semidistrim lattices, we are able to derive several intimate connections between rowmotion and pop-stack sorting, one of which involves independent dominating sets of the Galois graph.}

\keywords{lattice, trim lattice, semidistributive lattice, rowmotion, pop-stack sorting}

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

%\renewbibmacro{in:}{}


\begin{document}

\maketitle

\section{Introduction}

All lattices in this extended abstract are assumed to be finite.  Two families of lattices that extend the family of distributive lattices are the family of \emph{semidistributive} lattices and the family of \emph{trim} lattices. The union of these two families contains several well-studied classes of lattices such as weak orders of finite Coxeter groups, facial weak orders of simplicial hyperplane arrangements, finite Cambrian lattices, biCambrian lattices, $\nu$-Tamari lattices, Grid-Tamari lattices, and lattices of torsion classes of Artin algebras.
Although these two families are distinct (see~\Cref{fig:semidistrim}), they share many common properties. For example, the following hold for each lattice $L$ in each of these families:
\begin{itemize}
    \item every interval of $L$ is also in the family;
    \item there is a canonical bijection between join- and meet-irreducible elements of $L$;
    \item cover relations of $L$ are canonically labeled by join-irreducible elements;
    \item each element in $L$ is uniquely determined by the labels of its down-covers and also by the labels of its up-covers;
    \item the collection of down-cover label sets of the elements of $L$ equals the collection of up-cover label sets of the elements of $L$, and each of these collections is equal to the collection of independent sets in a certain graph called the \emph{Galois graph};
   \item there is a natural way of defining a certain bijective operator called \emph{rowmotion} on $L$;
   \item $L$ is crosscut simplicial; in particular, its order complex is either contractible or homotopy equivalent to a sphere.
\end{itemize}

In this extended abstract of the article \cite{Semidistrim}, we develop a theory of \emph{semidistrim lattices}, which we propose as a common generalization of semidistributive and trim lattices.  An example of a semidistrim lattice that is neither semidistributive nor trim is illustrated on the right of~\Cref{fig:semidistrim}. We will see that semidistrim lattices satisfy all of the bulleted items listed above and much more. In particular, we will define a bijective rowmotion operator $\row_L$ on a semidistrim lattice $L$, and we will see that $\row_L$ is intimately related to the \emph{pop-stack sorting} operator $\pop_L$, which is defined by $\pop_L(x)=x\wedge\bigwedge\{y\in L:y\lessdot x\}$. Along the way, we will use the pop-stack sorting operator to define (sometimes noninvertible) rowmotion operators on meet-semidistributive lattices. 

\begin{figure}[htbp]
\begin{center}
\raisebox{-.5\height}{\scalebox{0.6}{\begin{tikzpicture}[scale=1]
\node[shape=circle,fill=black, scale=0.5] (0) at (0,0) {};
\node[shape=circle,fill=black, scale=0.5] (1) at (-1,1) {};
\node[shape=circle,fill=black, scale=0.5] (2) at (1,1) {};
\node[shape=circle,fill=black, scale=0.5] (3) at (-1,2) {};
\node[shape=circle,fill=black, scale=0.5] (4) at (1,2) {};
\node[shape=circle,fill=black, scale=0.5] (5) at (0,3) {};
\draw[very thick] (0) to (1) to (3) to (5) to (4) to (2) to (0);
\end{tikzpicture}}}
\qquad\qquad\qquad
\raisebox{-.5\height}{\scalebox{0.6}{\begin{tikzpicture}[scale=1]
\node[shape=circle,fill=black, scale=0.5] (0) at (0,0) {};
\node[shape=circle,fill=black, scale=0.5] (1) at (-1,1) {};
\node[shape=circle,fill=black, scale=0.5] (2) at (2,2) {};
\node[shape=circle,fill=black, scale=0.5] (3) at (0,2) {};
\node[shape=circle,fill=black, scale=0.5] (4) at (1,3) {};
\node[shape=circle,fill=black, scale=0.5] (5) at (-2,2) {};
\node[shape=circle,fill=black, scale=0.5] (6) at (0,4) {};
\draw[very thick] (0) to (1) to (5) to (6) to (4) to (2) to (0);
\draw[very thick] (1) to (3) to (4);
\end{tikzpicture}}}
\qquad\qquad\qquad
\raisebox{-.5\height}{\scalebox{0.6}{\begin{tikzpicture}[scale=1]
\node[shape=circle,fill=black, scale=0.5] (0) at (0,0) {};
\node[shape=circle,fill=black, scale=0.5] (1) at (-1,1) {};
\node[shape=circle,fill=black, scale=0.5] (2) at (2,2) {};
\node[shape=circle,fill=black, scale=0.5] (3) at (0,2) {};
\node[shape=circle,fill=black, scale=0.5] (4) at (1,3) {};
\node[shape=circle,fill=black, scale=0.5] (5) at (-2,2) {};
\node[shape=circle,fill=black, scale=0.5] (6) at (0,4) {};
\node[shape=circle,fill=black, scale=0.5] (7) at (1,1) {};
\draw[very thick] (0) to (1) to (5) to (6) to (4) to (2) to (7) to (0);
\draw[very thick] (1) to (3) to (4);
\end{tikzpicture}}}
\end{center}
\caption{{\it Left}: A semidistributive lattice that is not trim.  {\it Middle}: A trim lattice that is not semidistributive.  {\it Right}: A semidistrim lattice that is not trim or semidistributive.}
\label{fig:semidistrim}
\end{figure}



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

We assume basic familiarity with standard terminology from the theory of posets. For example, we write $x\lessdot y$ to indicate that an element $y$ covers an element $x$. Given elements $x$ and $y$ in a poset $P$ with $x\leq y$, the \defn{interval} $[x,y]$ is defined to be the set $[x,y]=\{z\in P:x\leq z\leq y\}$. We write $\min(P)$ and $\max(P)$ for the set of minimal elements of $P$ and the set of maximal elements of $P$, respectively. The \defn{order complex} of $P$ is the abstract simplicial complex whose faces are the chains of $P$. 


A \defn{lattice} is a poset $L$ such that any two elements $x,y\in L$ have a unique greatest lower bound, which is called their \defn{meet} and denoted $x\wedge y$, and a unique least upper bound, which is called their \defn{join} and denoted $x\vee y$. The meet and join operations are associative and commutative, so it makes sense to consider the meet and join of an arbitrary subset $X\subseteq L$; we denote these by $\bigwedge X$ and $\bigvee X$, respectively. Each lattice has a unique minimal element, which we denote by $\widehat 0$, and a unique maximal element, which we denote by $\widehat 1$. 

Let $L$ be a lattice. An element $j\in L$ is called \defn{join-irreducible} if it covers exactly one element; if this is the case, we denote by $j_*$ the unique element covered by $j$. An element $m\in L$ is called \defn{meet-irreducible} if it is covered by exactly one element; if this is the case, we denote by $m^*$ the unique element covering $m$. We write $\J_L$ and $\M_L$ for the set of join-irreducible elements of $L$ and the set of meet-irreducible elements of $L$, respectively. 


If we can write $L=[\widehat 0,m_0]\sqcup[j_0,\widehat 1]$ for some $j_0,m_0\in L$, then we call the pair $(j_0,m_0)$ a \defn{prime pair} for $L$. In this case, $j_0$ is called \defn{join-prime} and $m_0$ is called \defn{meet-prime}. Join-prime elements are necessarily join-irreducible, and meet-prime elements are necessarily meet-irreducible.  

A lattice $L$ is \defn{join-semidistributive} if for all $a,b\in L$ with $a\leq b$, the set $\{w\in L:w\vee a=b\}$ has a unique minimal element. Dually, $L$ is called \defn{meet-semidistributive} if for all $a,b\in L$ with $a\leq b$, the set $\{w\in L:w\wedge b=a\}$ has a unique maximal element. A lattice is \defn{semidistributive} if it is both join-semidistributive and meet-semidistributive.

We say a lattice $L$ is \defn{extremal} if it has a maximum-length chain $\widehat 0=x_0\lessdot x_1\lessdot x_2\lessdot \cdots \lessdot x_n=\widehat 1$ such that $|\J_L|=|\M_L|=n$~\cite{markowsky92primes}.   An element $x\in L$ is called \defn{left modular} if for all $y,z\in L$ with $y \leq z$, we have the equality
$(y \vee x) \wedge z = y \vee (x \wedge z)$.  A lattice is called \defn{left modular} if it has a maximal chain of left modular elements.  A lattice is called \defn{trim} if it is extremal and left modular~\cite{thomas2006analogue,thomas2019rowmotion}.

\Cref{fig:semidistrim} shows a semidistributive lattice that is not trim and a trim lattice that is not semidistributive.  It was shown in~\cite[Theorem 1.4]{thomas2019rowmotion} that an extremal semidistributive lattice is necessarily trim.

\section{New Definitions}
Our goal in this section is to build up the definition of a semidistrim lattice. Our definitions are guided by a desire to generalize semidistributive and trim lattices as broadly as possible while still retaining a good amount of structure. 

For a general lattice $L$, the sets $\J_L$ and $\M_L$ could have different cardinalities. However, there are several interesting lattices where these sets do have the same size, and in these cases, we can ask for a ``canonical'' bijection between them. To this end, we define a \defn{pairing} on $L$ to be a bijection $\kappa\colon \J_L\to \M_L$ such that $j\vee\kappa(j)=\kappa(j)^*$ and $j\wedge \kappa(j)=j_*$ for all $j\in\J_L$. We say $L$ is \defn{uniquely paired} if it has a unique pairing; in this case, we write $\kappa_L$ for the unique pairing on $L$. When $L$ is uniquely paired and $x\in L$, we let $J_L(x)=\{j\in\J_L:j\leq x\}$ and $M_L(x)=\{j\in\J_L:\kappa_L(j)\geq x\}$. 

Markowsky defined a \emph{poset of irreducibles} for a general lattice $L$. When $L$ is uniquely paired, we can specialize this construction and obtain a (simple) directed graph $G_L$ called the \defn{Galois graph} of $L$. The vertex set of $G_L$ is the set $\J_L$ of join-irreducible elements of $L$. Given distinct $j,j'\in\J_L$, there is an edge $j\to j'$ in $G_L$ if and only if $j\not\leq\kappa_L(j')$. 

We now impose additional structure on uniquely paired lattices; this new structure is an analogue of interval-dismantlability (see \cite{adaricheva2018interval}) that additionally requires a certain compatibility condition for join-irreducible elements and for meet-irreducible elements. More precisely, we define a uniquely paired lattice $L$ to be \defn{compatibly dismantlable} if it has cardinality $1$ or if it contains a prime pair $(j_0,m_0)$ such that the following compatibility conditions hold:
\begin{itemize}
    \item $[j_0,\widehat{1}]$ is compatibly dismantlable, and there is a bijection
    \[\alpha\colon\{j\in \J_L : j_0 \leq \kappa_L(j)\} \to \J_{[j_0,1]}\]
     given by $\alpha(j)=j_0\vee j$ such that $\kappa_{[j_0,\widehat 1]}(\alpha(j))=\kappa_L(j)$ for all $j\in \J_L$ with $j_0\leq \kappa_L(j)$;
    \item $[\widehat{0},m_0]$ is compatibly dismantlable, and there is a bijection \[\beta\colon\{m\in \M_L : \kappa_L^{-1}(m) \leq m_0\} \to \M_{[0,m_0]}\] given by $\beta(m)=m_0\wedge m$ such that $\kappa_{[\widehat 0,m_0]}^{-1}(\beta(m))=\kappa_L^{-1}(m)$ for all $m\in\M_L$ with $\kappa_L^{-1}(m)\leq m_0$.
\end{itemize}
We call such a prime pair $(j_0,m_0)$ a \defn{dismantling pair} for $L$.

\begin{figure}[htbp]
\begin{center}
\raisebox{-.5\height}{\scalebox{0.6}{\begin{tikzpicture}[scale=2]
\node[shape=circle,fill=black,scale=0.5,label={[xshift=0ex, yshift=-4.5ex]$\widehat{0}$}] (0) at (0,0) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=-2ex, yshift=-2ex]$j_0$}] (j2) at (-1,1) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=-2ex, yshift=-2ex]$j_1$}] (j1) at (0,1) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=2.5ex, yshift=-1ex]$m_1$},label={[xshift=2.5ex, yshift=-3ex]$j_2$}] (j0) at (1,1) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=-2ex, yshift=-3ex]$j_3$},label={[xshift=-2ex, yshift=-1ex]$m_4$}] (j3) at (-1,2) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=2.5ex, yshift=-3ex]$j_4$},label={[xshift=2.5ex, yshift=-1ex]$m_3$}] (j4) at (-.5,2) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=2.5ex, yshift=-2ex]$m_0$}] (m2) at (1,2) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=-2.5ex, yshift=-2ex]$m_2$}] (m0) at (0,3) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=0ex, yshift=0ex]$\widehat{1}$}] (1) at (1,4) {};
\draw[very thick] (0) to (j2) to (j3) to (m0) to (1) to (m2) to (j0) to (0);
\draw[very thick] (0) to (j1) to (m0) to (j4) to (j2);
\draw[very thick] (j1) to (m2);
\end{tikzpicture}}}
\hspace{1in}
\raisebox{-.5\height}{\scalebox{0.7}{\begin{tikzpicture}[scale=2]
\node[shape=circle,draw=black,very thick] (2) at (0,0) {$j_0$};
\node[shape=circle,draw=black,very thick] (0) at (0,-1) {$j_2$};
\node[shape=circle,draw=black,very thick] (1) at (0,1) {$j_1$};
\node[shape=circle,draw=black,very thick] (3) at (1,0) {$j_3$};
\node[shape=circle,draw=black,very thick] (4) at (-1,0) {$j_4$};
\draw[->,very thick] (0) to (4);
\draw[->,very thick] (0) to (3);
\draw[->,very thick] (4) to (2);
\draw[->,very thick] (3) to (2);
\draw[->,very thick] (2) to (1);
\draw[<->,very thick] (4) to (1);
\draw[<->,very thick] (3) to (1);
\end{tikzpicture}}}
\end{center}

\caption{A compatibly dismantlable lattice and its Galois graph.}
\label{fig:reduced}
\end{figure}

\Cref{fig:reduced} illustrates a compatibly dismantlable lattice $L$ with dismantling pair $(j_0,m_0)$. The join-irreducible and meet-irreducible elements are named in such a way that $\kappa_L(j_i)=m_i$ for all $0\leq i\leq 4$. The join-irreducible elements $j\in \J_L$ satisfying $j_0\leq \kappa_L(j)$ are $j_2,j_3,j_4$. These elements correspond bijectively to the join-irreducible elements of $L^0$: we have $\alpha(j_2)=j_0\vee j_2=\widehat 1$, $\alpha(j_3)=j_0\vee j_3=j_3$, and $\alpha(j_4)=j_0\vee j_4=j_4$. The meet-irreducible elements $m\in \M_L$ satisfying $\kappa_L^{-1}(m)\leq m_0$ are $m_1$ and $m_2$. These elements correspond bijectively to the meet-irreducible elements of $L_0$: we have $\beta(m_1)=m_0\wedge m_1=m_1$ and $\beta(m_2)=m_0\wedge m_2=j_1$. Notice how $\alpha$ and $\beta$ are compatible with the pairings $\kappa_L$, $\kappa_{[\widehat 0, m_0]}$, and $\kappa_{[j_0,\widehat 1]}$. For example, $\kappa_{[j_0,\widehat 1]}(\alpha(j_2))=\kappa_{[j_0,\widehat 1]}(\widehat 1)=m_2=\kappa_L(j_2)$. 


Let us say a uniquely paired lattice $L$ is \defn{overlapping} if for every cover relation $x\lessdot y$, the set $J_L(y)\cap M_L(x)$ is a singleton. Suppose $L$ is overlapping. We obtain an edge-labeling of the Hasse diagram of $L$ with join-irreducible elements by labeling each edge $x\lessdot y$ with the unique join-irreducible $j_{xy}\in J_L(y)\cap M_L(x)$. For each $x\in L$, we define $\D_L(x)=\{j_{yx}:y\lessdot x\}$ and $\U_L(x)=\{j_{xy}:x\lessdot y\}$. 

\begin{proposition}[\cite{Semidistrim}]
Compatibly dismantlable lattices are overlapping.
\end{proposition}

\begin{theorem}[\cite{Semidistrim}]\label{thm:labels}
Let $L$ be a compatibly dismantlable lattice.  Every element $x \in L$ is uniquely determined by its downward label set $\D_L(x)$, and it is also uniquely determined by its upward label set $\U_L(x)$. More precisely, \[x = \bigvee \D_L(x) = \bigwedge\kappa_L(\U_L(x)).\]
\end{theorem}

The preceding results show that compatibly dismantlable lattices satisfy some nice properties, but they are still lacking in other regards. For example, the family of compatibly dismantlable lattices is not closed under taking intervals (see \cite{Semidistrim} for an example). It is also not clear how to (naturally) define a bijective rowmotion operator on these lattices. By imposing one additional condition, we will obtain our titular lattices, which end up satisfying several additional desiderata. 

An \defn{independent set} of a graph $G$ is a subset $I$ of the vertex set of $G$ such that no two vertices of $I$ are adjacent. Let $\I(G)$ denote the collection of independent sets of $G$. 

\begin{definition}[\cite{Semidistrim}]
A lattice $L$ is \defn{semidistrim} if it is compatibly dismantlable and $\D_L(x)$ and $\U_L(x)$ are independent sets of the Galois graph $G_L$ for all $x \in L$.
\label{def:semidistrim2}
\end{definition}

\section{Structural Theorems}

Our first theorem about semidistrim lattices shows that they are named appropriately. 

\begin{theorem}[\cite{Semidistrim}]
Semidistributive lattices are semidistrim, and trim lattices are semidistrim. 
\end{theorem}

The next theorem will be crucial for defining rowmotion on semidistrim lattices. 

\begin{theorem}[\cite{Semidistrim}]
\label{thm:independent}
Let $L$ be a semidistrim lattice. The maps $\D_L\colon L\to\I(G_L)$ and $\U_L\colon L\to\I(G_L)$ are bijections.
\end{theorem}

If $L$ is semidistrim and $x\in L$, then the sets $\D_L(x)$ and $\U_L(x)$ are independent sets in $G_L$ by definition. The next theorem tells us more precisely how these sets fit together within the Galois graph. 

Suppose $G$ is a directed graph. An \defn{orthogonal pair} of $G$ is a pair $(X,Y)$ such that $X$ and $Y$ are disjoint independent sets of $G$ and such that there does not exist an edge of the form $j\to j'$ with $j\in X$ and $j'\in Y$. An orthogonal pair $(X,Y)$ is called \defn{tight} if the following additional conditions hold: 
\begin{itemize}
    \item If $j$ is a vertex of $G$ that is not in $X\cup Y$, then $(X\cup\{j\},Y)$ and $(X,Y\cup\{j\})$ are not orthogonal pairs. 
    \item If $j\to j'$ is an edge in $G$ such that $j\not\in X\cup Y$ and $j'\in X$, then $((X\setminus\{j'\})\cup\{j\},Y)$ is not an orthogonal pair.
    \item If $j'\to j$ is an edge in $G$ such that $j\not\in X\cup Y$ and $j'\in Y$, then $(X,(Y\setminus\{j'\})\cup\{j\})$ is not an orthogonal pair.
\end{itemize}

\begin{theorem}[\cite{Semidistrim}]\label{thm:tops}
Let $L$ be a semidistrim lattice. For every $x\in L$, the pair $(\D_L(x),\U_L(x))$ is a tight orthogonal pair of $G_L$. 
\end{theorem}

We now turn our attention to operations on lattices that preserve semidistrimness. Recall that if $P$ and $P'$ are two posets, then their \defn{product} is the poset $P\times P'$ whose underlying set is the Cartesian product of $P$ and $P'$, where $(x,x')\leq (y,y')$ if and only if $x\leq y$ in $P$ and $x'\leq y'$ in $P'$.

\begin{theorem}[\cite{Semidistrim}]
Products of semidistrim lattices are semidistrim.
\end{theorem}

The next theorem is one of the crucial properties of the family of semidistrim lattices. It is particularly profitable because it allows us to use inductive arguments to prove further properties of semidistrim lattices. 

\begin{theorem}[\cite{Semidistrim}]\label{thm:intervals}
Intervals in semidistrim lattices are semidistrim. 
\end{theorem}

Suppose $L$ is a compatibly dismantlable lattice with dismantling pair $(j_0,m_0)$. By the definition of a compatibly dismantlable lattice, the unique pairings $\kappa_{L_0}$ and $\kappa_{L^0}$ on the intervals $L_0=[\widehat 0,m_0]$ and $L^0=[j_0,\widehat 1]$ are compatible with the pairing $\kappa_L$ via the maps $\alpha$ and $\beta$. If we additionally assume that $L$ is semidistrim, then the preceding theorem tells us that every interval in $L$ is semidistrim; the next corollary tells us that the pairings on the intervals of $L$ are compatible with $\kappa_L$. 

\begin{corollary}[\cite{Semidistrim}]\label{cor:intervals_compatible}
Let $L$ be a semidistrim lattice, and let $[u,v]$ be an interval in $L$. There are bijections $\alpha_{u,v}\colon J_L(v)\cap M_L(u)\to\J_{[u,v]}$ and $\beta_{u,v}\colon\kappa_L(J_L(v)\cap M_L(u))\to\M_{[u,v]}$ given by $\alpha_{u,v}(j)=u\vee j$ and $\beta_{u,v}(m)=v\wedge m$, respectively. Moreover, $\kappa_{[u,v]}(\alpha_{u,v}(j))=\beta_{u,v}(\kappa_L(j))$ for all $j\in J_L(v)\cap M_L(u)$.
\end{corollary}

To end this section, let us record how the Galois graph and the edge labels of an interval in a semidistrim lattice relate to those of the entire lattice. 

\begin{corollary}[\cite{Semidistrim}]\label{cor:galois_label_intervals}
Let $[u,v]$ be an interval in a semidistrim lattice $L$. The bijection $\alpha_{u,v}\colon J_L(v)\cap M_L(u)\to\J_{[u,v]}$ given by $\alpha_{u,v}(j)=u\vee j$ is an isomorphism from an induced subgraph of the Galois graph $G_L$ to the Galois graph $G_{[u,v]}$.  If $u\leq x\lessdot y\leq v$ and $j_{xy}$ is the label of the cover relation $x\lessdot y$ in $L$, then $\alpha_{u,v}(j_{xy})$ is the label of the same cover relation in $[u,v]$.  
\end{corollary}


\section{Poset Topology}
The \defn{crosscut complex} of a lattice $L$ is the abstract simplicial complex whose faces are the sets $A$ of atoms of $L$ such that $\bigvee A\neq \widehat 1$. We say $L$ is \defn{crosscut simplicial} if for all $u,v\in L$ with $u\leq v$, the crosscut complex of the interval $[u,v]$ contains all proper subsets of the set of atoms of $[u,v]$ as faces. It is known \cite[Theorem~10.8]{bjornertopological} that the order complex of a lattice is homotopy equivalent to its crosscut complex; it follows that if $L$ is crosscut simplicial, then every interval in $L$ has an order complex that is either contractible or homotopy equivalent to a sphere. McConville \cite{mcconville2017crosscut} proved that semidistributive lattices are crosscut simplicial; in fact, Barnard \cite{barnard19canonical} showed that a lattice is semidistributive if and only if it is join-semidistributive and crosscut simplicial. Thomas \cite{thomas2006analogue} proved that the order complex of a trim lattice must be contractible or homotopy equivalent to a sphere. We generalize these results to semidistrim lattices in the following theorem. 

\begin{theorem}[\cite{Semidistrim}]
Semidistrim lattices are crosscut simplicial. Hence, the order complex of a semidistrim lattice is either contractible or homotopy equivalent to a sphere. 
\end{theorem}



\section{Rowmotion and Pop-Stack Sorting}\label{sec:pop_and_row}

Let $L$ be a lattice. Following \cite{defant21meeting}, we define the \defn{pop-stack sorting operator} $\popdown_L\colon L\to L$ and the \defn{dual pop-stack sorting} operator $\popup_L\colon L\to L$ by 
\[
\popdown_L(x)=x\wedge\bigwedge\{y\in L:y\lessdot x\}\quad\text{and}\quad\popup_L(x)=x\vee\bigvee\{y\in L:x\lessdot y\}.
\] In particular, $\popdown_L(\widehat 0)=\widehat 0$, and $\popup_L(\widehat 1)=\widehat 1$. 
When $L$ is the right weak order on the symmetric group $S_n$, $\pop_L$ coincides with a combinatorially-defined operator called the \emph{pop-stack sorting map} (see \cite{Asinowski2,ClaessonPop,defant21meeting,defant2021stack}). Pop-stack sorting operators on lattices were introduced in \cite{defant21meeting, defant2021stack} as generalizations of the pop-stack sorting map.

Now suppose $L$ is semidistrim. \Cref{thm:independent} tells us that the maps $\D_L\colon L\to\I(G_L)$ and $\U_L\colon L\to\I(G_L)$ are bijections. We define \defn{rowmotion} to be the bijection $\row_L\colon L\to L$ defined by declaring $\row_L(x)$ to be the unique element of $L$ that satisfies $\U_L(\row(x))=\D_L(x)$. 
This definition of rowmotion extends the rowmotion operators on distributive, semidistributive, and trim lattices considered recently by several authors~\cite{barnard19canonical,striker2018rowmotion,thomas2019independence,thomas2019rowmotion}.

Our goal in this section is to show that pop-stack sorting, dual pop-stack sorting, and rowmotion are closely related. While discussing the connections among these operators, we will be led to questions and results that are new even for distributive lattices. 

\begin{theorem}[\cite{Semidistrim}]
Let $L$ be a semidistrim lattice. For $x\in L$, we have 
\begin{align*}\row_L(x) = \bigwedge\kappa_L(\D_L(x)) &\text{ and } \row_L^{-1}(x) = \bigvee \U_L(x); \\ 
\popdown_L(x) = x \wedge \bigwedge\kappa_L(\D_L(x)) &\text{ and } \popup_L(x) = x \vee \bigvee\U_L(x).\end{align*}  In particular, $\pop_L(x) = x \wedge \row_L(x) \text{ and } \popup_L(x) = x \vee \row_L^{-1}(x)$. In fact, $\row_L(x)\in\max\{z\in L:\pop_L(x)= x\wedge z\}$ and $\row_L^{-1}(x)\in\min\{z\in L:\popup_L(x)= x\vee z\}$
\label{thm:pop_and_row}
\end{theorem}

If $L$ is a meet-semidistributive lattice and $a,b\in L$ are such that $a\leq b$, then the set $\{z\in L:a=b\wedge z\}$ has a unique maximal element. Therefore, if $L$ is both meet-semidistributive and semidistrim, then \Cref{thm:pop_and_row} tells us that for every $x \in L$, $\row_L(x)$ is the unique maximal element of $\{z \in L:  \pop_L(x)=x\wedge z\}$. This is interesting because it provides a natural way to extend the definition of rowmotion to arbitrary meet-semidistributive lattices that might not be semidistrim. More precisely, if $L$ is a meet-semidistributive lattice, then we define \defn{rowmotion} to be the operator $\row_L\colon L\to L$ such that for every $x\in L$, the element $\row_L(x)$ is the unique maximal element of $\{z \in L:  \pop_L(x)=x\wedge z\}$. Let us remark that this rowmotion operator is \emph{not} necessarily bijective in general (see \Cref{fig:meet_semi}). In fact, we have the following proposition. 

\begin{proposition}[\cite{Semidistrim}]\label{prop:bijective_meet_semi}
A lattice $L$ is semidistributive if and only if it is meet-semidistributive and the rowmotion operator $\row_L\colon L\to L$ is bijective. 
\end{proposition}

The previous proposition implies that a lattice is semidistributive if and only if it is meet-semidistributive and semidistrim. 

\begin{figure}[htbp]
\begin{center}
\raisebox{-.5\height}{\scalebox{1}{\begin{tikzpicture}[scale=1]
\node[shape=circle,fill=black,scale=0.5,label={[xshift=0ex, yshift=-4.5ex]$\widehat{0}$}] (0) at (0,0) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=-2ex, yshift=-2ex]$d$}] (d) at (-1,1) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=2ex, yshift=-2ex]$e$}] (e) at (1,1) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=-2ex, yshift=-2ex]$a$}] (a) at (-2,2) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=-2ex, yshift=-2ex]$b$}] (b) at (0,2) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=2ex, yshift=-2ex]$c$}] (c) at (2,2) {};
\node[shape=circle,fill=black,scale=0.5,label={[xshift=0ex, yshift=1ex]$\widehat{1}$}] (1) at (0,3) {};
\draw[very thick] (0) to (d) to (a) to (1) to (b) to (d);
\draw[very thick] (1) to (c) to (e) to (0);
\draw[very thick] (b) to (e);
\end{tikzpicture}}}
\hspace{1in}
\raisebox{-.5\height}{\scalebox{1}{\begin{tikzpicture}[scale=1]
\node (0) at (0,0) {$\widehat{0}$};
\node (d) at (2,3) {$d$};
\node (e) at (-2,3) {$e$};
\node (a) at (-1,2) {$a$};
\node (b) at (0,1) {$b$};
\node (c) at (1,2) {$c$};
\node (1) at (0,-1) {$\widehat{1}$};
\draw[very thick,->] (e) to (a);
\draw[very thick,->]  (a) to (b);
\draw[very thick,->] (b) to (0);
\draw[very thick,->] (d) to (c);
\draw[very thick,->]  (c) to (b);
\draw[very thick,->, bend left]  (0) to (1);
\draw[very thick,->, bend left]  (1) to (0);
\end{tikzpicture}}}
\end{center}
\caption{{\it Left:} A meet-semidistributive lattice $L$ that is not semidistrim.  {\it Right: } The action of rowmotion on $L$.}
\label{fig:meet_semi}
\end{figure}


Let us now turn back to semidistrim lattices. The next proposition will be crucial for establishing further connections among pop-stack sorting, dual pop-stack sorting, and rowmotion. The proof of this proposition is quite short, but this is because it invokes \Cref{thm:intervals}, which does most of the heavy lifting.

\begin{proposition}[\cite{Semidistrim}]\label{prop:pop_label_containment}
If $L$ is a semidistrim lattice and $x \in L$, then \[\D_L(x) \subseteq \U_L(\pop_L(x))\quad\text{and}\quad\U_L(x) \subseteq \D_L(\popup_L(x)).\]
\end{proposition}

\begin{proof}
The second containment follows from the first by considering the dual lattice, so we only prove the first containment. The proof is by induction on $|L|$. Let $u=\pop_L(x)$. Let $\alpha_{u,x}\colon J_L(v)\cap M_L(u)\to\J_{[u,x]}$ be the bijection from \Cref{cor:intervals_compatible}. Since every element covered by $x$ is in $[u,x]$, it follows from \Cref{cor:galois_label_intervals} that $\D_{[u,x]}(x)=\alpha_{u,x}(\D_L(x))$ and that $\U_{[u,x]}(x)\subseteq\alpha_{u,x}(\U_L(u))$. The interval $[u,x]$ is semidistrim by \Cref{thm:intervals}. If $[u,x]$ is a proper interval of $L$, then we can use induction to see that $\D_{[u,x]}(x)\subseteq \U_{[u,x]}(u)$. In this case, $\D_L(x)=\alpha_{u,x}^{-1}(\D_{[u,x]}(x))\subseteq\alpha_{u,x}^{-1}(\U_{[u,x]}(u))\subseteq\U_L(u)$, as desired. Now suppose $[u,x]=L$. This means that $x=\widehat 1$ and $u=\pop_L(\widehat 1)=\widehat 0$. Then $\row_L(\widehat{1}) = \row_L(\widehat{1}) \wedge \widehat{1} = \pop_L(\widehat{1})$, so $\D_L(\widehat{1}) =\U_L(\row_L(\widehat 1))= \U_L(\pop_L(\widehat{1}))$ by the definition of rowmotion.  
\end{proof}

We are now in a position to discuss deeper connections among $\row_L$, $\pop_L$, and $\popup_L$. Let us begin with a fairly innocent question about rowmotion on a semidistrim lattice $L$. How many times does rowmotion on $L$ ``go down''? More precisely, how many elements $x\in L$ have the property that $\row_L(x)\leq x$? This question appears to be new even when $L$ is distributive. We will see that the answer is connected to $\pop_L$ and $\popup_L$, as well as independent dominating sets in the Galois graph $G_L$. Before giving more details, let us consider a natural process where we alternately apply $\pop_L$ and $\popup_L$. 

Suppose $L$ is semidistrim. Begin with some element $z\in L$. Let $x_1=\popdown_L(z)$, $y_1=\popup_L(x_1)$, $x_2=\popdown_L(y_1)$, $y_2=\popup_L(x_2)$, and so on. In general, $y_i=\popup_L(x_i)$, and $x_{i+1}=\pop_L(y_i)$. It follows from \Cref{prop:pop_label_containment} that $\D_L(z)\subseteq\U_L(x_1)\subseteq\D_L(y_1)\subseteq\U_L(x_2)\subseteq\D_L(y_2)\subseteq\cdots$. Appealing to \Cref{thm:labels}, we find that we have a chain 
\begin{equation}\label{eq:chain}
    \cdots\leq x_2\leq x_1\leq z\leq y_1\leq y_2\leq\cdots.
\end{equation}
This chain is obviously finite because $L$ is finite. Therefore, there exists a positive integer $k$ such that $\popup_L(x_k)=y_k$ and $\pop_L(y_k)=x_k$. This motivates the following definition. Given $x,y\in L$, we say that $(x,y)$ is a \defn{popping pair} if $\popup_L(x)=y$ and $\popdown_L(y)=x$. 

In general, when one is faced with a set $X$ and a noninvertible operator $f\colon X\to X$, it is natural to ask for a description or enumeration of the image of $f$. For example, the structural and enumerative properties of the image of the classical pop-stack sorting map on $S_n$ were studied in~\cite{Asinowski2}. The next proposition connects the images of $\pop_L$ and $\popup_L$ with popping pairs. 

\begin{proposition}[\cite{Semidistrim}]\label{prop:popping_pairs_images}
Let $L$ be a semidistrim lattice, and let $z\in L$. Then $z$ is in the image of $\pop_L$ if and only if there exists $y\in L$ such that $(z,y)$ is a popping pair. Similarly, $z$ is in the image of $\popup_L$ if and only if there exists $x\in L$ such that $(x,z)$ is a popping pair.  
\end{proposition}

\Cref{prop:popping_pairs_images} implies that when we constructed the chain $\cdots\leq x_2\leq x_1\leq z\leq y_1\leq y_2\leq\cdots$ in \eqref{eq:chain}, the process actually stabilized after at most two steps. In other words, \[x_1=x_2=x_3=\cdots\quad\text{and}\quad y_1=y_2=y_3=\cdots.\]

A set $I$ of vertices in a (directed or undirected) graph $G$ is called \defn{dominating} if every vertex of $G$ is either in $I$ or is adjacent to a vertex in $I$.  An \defn{independent dominating set} of $G$ is an independent set of $G$ that is dominating. We write $\I^\mathrm{dom}(G)$ for the collection of independent dominating sets of $G$. 

\begin{theorem}\label{thm:ind_dom} 
Let $L$ be a semidistrim lattice, and let $x \in L$. Then $\row_L(x) \leq x$ if and only if $\D_L(x)$ is an independent dominating set of $G_L$. Moreover,
\[|\{ x \in L : \row_L(x) \leq x\}|=|\pop_L(L)|=|\popup_L(L)|=|\I^\mathrm{dom}(G_L)|.\]
\end{theorem}

Let us remark that the equality $|\pop_L(L)|=|\popup_L(L)|$ in \Cref{thm:ind_dom} is interesting in its own right and is not a simple consequence of the definitions of $\pop_L$ and $\popup_L$. Indeed, it is easy to construct examples of lattices where this equality \emph{fails}. 

\section{Further Directions}
The article \cite{Semidistrim} provides several open problems that we hope will stimulate further development of the theory of semidistrim lattices. We list some of these problems here. 

Birkhoff's representation theorem characterizes the Galois graphs of finite distributive lattices as the (directed) comparability graphs of finite posets. The recent article \cite{reading2019fundamental} characterizes the Galois graphs of finite semidistributive lattices. It would be very interesting and useful to have a characterization of the Galois graphs of semidistrim lattices. 

Products and intervals of semidistrim lattices are again semidistrim. It would be interesting to have other lattice operations that preserve the family of semidistrim lattices. In particular, is every quotient of a semidistrim lattice necessarily semidistrim?

In \Cref{sec:pop_and_row}, we showed how the pop-stack sorting operator can be used to define rowmotion on a meet-semidistributive lattice $L$ that need not be semidistrim; namely, for $x\in L$, we defined $\row_L(x)$ to be the unique maximal element of $\{z\in L:\pop_L(x)=x\wedge z\}$. We saw in \Cref{prop:bijective_meet_semi} that this rowmotion operator is noninvertible whenever $L$ is meet-semidistributive but not semidistributive. Virtually all reasonable questions that one might wish to ask about these operators are open. For example, it would be interesting to describe the periodic points or the image of rowmotion on such a lattice. What can be said about the maximum number of preimages that an element can have under rowmotion? Perhaps there are interesting families of meet-semidistributive lattices where these noninvertible rowmotion operators have desirable properties.  

The image of the classical pop-stack sorting map on $S_n$, which coincides with $\pop_L$ when $L$ is the right weak order on $S_n$, was studied in~\cite{Asinowski2}. \Cref{thm:ind_dom} motivates the investigation of the image of $\pop_L$ for other nice families of semidistrim lattices $L$. It is also natural to refine the enumeration by considering the generating function \[\popnone(L;q) = \sum_{b\in\pop_L(L)}q^{|\U_L(b)|}=\sum_{b\in\popup_L(L)}q^{|\D_L(b)|},\] where the second equality follows from \Cref{prop:pop_label_containment} and \Cref{prop:popping_pairs_images}. It follows from \Cref{thm:ind_dom} that $\popnone(L;q)$ enumerates the independent dominating sets in $\widetilde G_L$ according to cardinality.  We write $[q^i]\popnone(L;q)$ for the coefficient of $q^i$ in $\popnone(L;q)$.  Write $\mathrm{Tamari}(W)$ for the Tamari lattice of type $W$, $\mathrm{Camb}_\mathrm{bi}(W)$ for the bipartite Cambrian lattice of type $W$, and $J(\Phi^+_W)$ for the lattice of order ideals of the root poset of type $W$.


\begin{conjecture}[\cite{Semidistrim}] The following equalities hold:
\begin{align*}
[q^{n-1}]\popnone(\mathrm{Weak}(B_n);q)&=3^n - 2n - 1, \\
\popnone(\mathrm{Tamari}(A_n);q)&=\sum_{k=0}^n \frac{1}{k+1}\binom{2k}{k} \binom{n}{2k} q^{n-k}  & \hspace{-32pt} \text{(\href{https://oeis.org/A055151}{A055151}),} \\
\popnone(\mathrm{Tamari}(B_n);q)&=\sum_{k=0}^{\lfloor \frac{n+1}{2} \rfloor} \binom{n-1}{k}\binom{n+1-k}{k} q^{n-k} & \hspace{-32pt} \text{see (\href{https://oeis.org/A025566}{A025566}),} \\
\popnone(\mathrm{Camb}_\mathrm{bi}(A_n);q)&=
\sum_{k=1}^{\lfloor\frac{(n+3)}{2}\rfloor} \frac{k (-1)^{k-1}}{n-k+3} \sum_{j=0}^{n-k+3}  \binom{j}{n-j+3} \binom{n-k+3}{j} q^{j-2} \\ & & \hspace{-32pt}  \text{see (\href{https://oeis.org/A089372}{A089372}),} \\
\popnone(J(\Phi^+_{A_n});q)&=\sum_{k=0}^n \frac{1}{k+1} \sum_{j=0}^{n-k+1} \binom{k+1}{j-1}\binom{k+1}{j} \binom{n-j+1}{n-k-j+1} q^{k+1} \\ & & \hspace{-32pt}  \text{(\href{https://oeis.org/A145904}{A145904}),}\\
\popnone(J(\Phi^+_{B_n});q)&=(-q)^n+\sum_{k=0}^n \sum_{j=1}^{k} \binom{k+1}{j}\binom{n-k-1}{j-1}\binom{n-j}{n-k}q^k & \hspace{-32pt} \text{(\href{https://oeis.org/A103881}{A103881}).}
\end{align*}
\label{conj:enumerations}
\end{conjecture}


Proposition~5 in \cite{Asinowski2} states that $[q^{n-2}]\popnone(\mathrm{Weak}(A_{n-1});q)=2^n-2n$. When $q=1$, the part of \Cref{conj:enumerations} concerning $J(\Phi^+_{A_n})$ is equivalent to \cite[Proposition~4.3]{Sapounakis}.   While this abstract was under review, the identity for $\popnone(\mathrm{Tamari}(A_n);q)$ was proven in~\cite{hong2022pop}.

\printbibliography

\end{document}
