\documentclass[finalversion]{FPSAC2020}
\articlenumber{65}
\addbibresource{independence.bib}

\usepackage{amsmath, amsfonts, amssymb, amsthm, mathtools, thmtools, wasysym, graphics, graphicx, xcolor, frcursive,xparse,comment,ytableau,stmaryrd,bbm,array,colortbl,tensor}
\usepackage[all]{xy}
\usepackage[boxed,norelsize]{algorithm2e}


\usepackage{url, hypcap}
%\hypersetup{colorlinks=true, citecolor=darkblue, linkcolor=darkblue}

\usepackage{tikz}
\usetikzlibrary{calc,through,backgrounds,shapes,matrix}
\hyphenation{semi-brick}

%\hyphenation{semi-distributive}
\definecolor{darkblue}{rgb}{0.0,0,0.7} % darkblue color
\newcommand{\darkblue}{\color{darkblue}} % darkblue command
\definecolor{darkred}{rgb}{0.7,0,0} % darkred color
\newcommand{\darkred}{\color{darkred}} % darkred command
\definecolor{lightgrey}{rgb}{0.7,0.7,0.7} % darkred color
\newcommand{\lightgrey}{\color{lightgrey}} % darkred command

%\definecolor{meet}{RGB}{141,195,216}
%\definecolor{join}{RGB}{238,147,99}

\definecolor{meet}{RGB}{255,205,111}
\definecolor{join}{RGB}{0,77,178}



%\definecolor{meet}{RGB}{52,123,152}
%\definecolor{join}{RGB}{184,78,20}
%#8DC3D8
%#EE9363

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{openproblem}[theorem]{Open Problem}
\newtheorem{remark}[theorem]{Remark}
\usepackage[procnames]{listings}
\usepackage[all]{xy}
\usepackage[T1]{fontenc}
\crefformat{footnote}{#2\footnotemark[#1]#3}
\crefformat{conjecture}{Conjecture~#2#1#3}

\usepackage[cal=boondoxo]{mathalfa}
\usepackage[colorinlistoftodos]{todonotes}

\newcommand{\nathan}[1]{\todo[size=\tiny,color=green!30]{#1 \\ \hfill --- N.}}
\newcommand{\Nathan}[1]{\todo[size=\tiny,inline,color=green!30]{#1
      \\ \hfill --- N.}}
\newcommand{\hugh}[1]{\todo[size=\tiny,color=purple!30]{#1\\ \hfill --- H.}}
\newcommand{\Hugh}[1]{\todo[size=\tiny,inline,color=purple!30]{#1
      \\ \hfill --- H.}}
%\newcommand{\defn}[1]{\emph{\darkblue #1}}
\newcommand{\defn}[1]{\emph{#1}}

\newcommand{\rhog}{\rho_{\textit{gl}}}
\newcommand{\rhol}{\rho_{\textit{loc}}}
\newcommand{\Po}{\mathcal{P}}
\newcommand{\Q}{\mathcal{Q}}
\newcommand{\LL}{\mathcal{L}}
\newcommand{\JJ}{\mathcal{J}}
\newcommand{\MM}{\mathcal{M}}
\newcommand{\x}{x}
\newcommand{\al}{\mathcal{D}}
\newcommand{\br}{\mathcal{U}}
\newcommand{\xx}{\mathbf{x}}
\newcommand{\y}{y}
\newcommand{\tog}{\mathrm{flip}}
\newcommand{\row}{\mathrm{row}}
\newcommand{\cov}{\mathrm{cov}}
\newcommand{\down}{\mathrm{D}}
\newcommand{\up}{\mathrm{U}}
%\newcommand{\tog}{\tau^\gamma}
\newcommand{\Camb}{\mathrm{Camb}}
\newcommand{\Krew}{\mathrm{Krew}}
\newcommand{\trip}{\mathrm{top}}
\newcommand{\mut}{\mathrm{tog}}
\newcommand{\la}{\mathcal{l}}
\usetikzlibrary{math}
\usepackage{xifthen}
\usepackage{xstring}
\SetKwInput{kwset}{set}
\usetikzlibrary{arrows,backgrounds,calc,trees}
\pgfdeclarelayer{background}
\pgfsetlayers{background,main}
\renewcommand{\mod}{\operatorname{mod}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Ext}{\operatorname{Ext}}
\newcommand{\tors}{\operatorname{tors}}

\newcommand{\convexpath}[2]{
[
    create hullnodes/.code={
        \global\edef\namelist{#1}
        \foreach [count=\counter] \nodename in \namelist {
            \global\edef\numberofnodes{\counter}
            \node at (\nodename) [draw=none,name=hullnode\counter] {};
        }
        \node at (hullnode\numberofnodes) [name=hullnode0,draw=none] {};
        \pgfmathtruncatemacro\lastnumber{\numberofnodes+1}
        \node at (hullnode1) [name=hullnode\lastnumber,draw=none] {};
    },
    create hullnodes
]
($(hullnode1)!#2!-90:(hullnode0)$)
\foreach [
    evaluate=\currentnode as \previousnode using \currentnode-1,
    evaluate=\currentnode as \nextnode using \currentnode+1
    ] \currentnode in {1,...,\numberofnodes} {
  let
    \p1 = ($(hullnode\currentnode)!#2!-90:(hullnode\previousnode)$),
    \p2 = ($(hullnode\currentnode)!#2!90:(hullnode\nextnode)$),
    \p3 = ($(\p1) - (hullnode\currentnode)$),
    \n1 = {atan2(\y3,\x3)},
    \p4 = ($(\p2) - (hullnode\currentnode)$),
    \n2 = {atan2(\y4,\x4)},
    \n{delta} = {-Mod(\n1-\n2,360)}
  in
    {-- (\p1) arc[start angle=\n1, delta angle=\n{delta}, radius=#2] -- (\p2)}
}
-- cycle
}

\Crefname{algocf}{Algorithm}{Algorithms}
\crefname{algocf}{algorithm}{algorithms}


\title{Independence Posets}

\author{Hugh Thomas\thanks{\href{mailto:hugh.ross.thomas@gmail.com}{hugh.ross.thomas@gmail.com}. Partially supported by the Canada Research Chairs program and an NSERC Discovery Grant.}\addressmark{1} \and Nathan Williams\thanks{\href{mailto:nathan.f.williams@gmail.com}{nathan.f.williams@gmail.com}.  Partially supported by a Simons Foundation Collaboration Grant 585380.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}LaCIM, Universit\'e du Qu\'ebec \`a Montr\'eal, Montreal, Canada \\ \addressmark{2}University of Texas at Dallas, Dallas, TX, USA}

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



\abstract{
Let $G$ be an acyclic directed graph. For each vertex $g \in G$, we define an involution on the independent sets of $G$.  We call these involutions \emph{flips}, and use them to define the  \emph{independence poset} for $G$---a new partial order on independent sets of $G$.  Our independence posets are a generalization of distributive lattices, eliminating the lattice requirement: an independence poset that is a graded lattice is always a distributive lattice.  Many well-known posets turn out to be special cases of our construction.}

\resume{Soit $G$ un graphe orient\'e acyclique. Pour chaque sommet $g \in G$, nous d\'efinissons une involution sur les ensembles ind\'ependants de $G$. Nous appelons ces involutions des \emph{flips}. Nous les utilisons pour d\'efinir une structure d'ensemble ordonn\'e sur les ensembles ind\'ependants de $G$, que nous nommons le \emph{poset d'ind\'ependance} de $G$.  Nos posets d'ind\'ependance g\'en\'eralisent les treillis distributifs en soustrayant la condition d'\^etre un treillis: un poset d'ind\'ependance qui est un treillis gradu\'e est un treillis distributif.  Il s'av\`ere que plusieurs ensembles ordonn\'es bien connus peuvent \^etre exprim\'es comme des posets d'ind\'ependance.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Poset, lattice, independent set, rowmotion.}



\begin{document}
\maketitle

\section{Introduction}
A \defn{trim lattice} is an extremal left-modular lattice~\cite{thomas2006analogue}.  Trim lattices were introduced to serve as analogues of distributive lattices without the graded hypothesis: a graded trim lattice is a distributive lattice, and every distributive lattice is trim.  

In~\Cref{lem:flip_eq_cov}, we define the \defn{independence poset} $\trip(G)$ on the set of independent sets of a directed acyclic graph $G$, using an explicit description of cover relations as certain \defn{flips}.  Our independence posets further generalize distributive lattices by removing the lattice requirement: an independence poset that is a lattice is always a trim lattice.  In other words, the common intersection of lattices and independence posets are exactly the trim lattices.\footnote{An interactive poster version of this extended abstract can be found online at \cite{TWposter}.}

\begin{theorem}
\label{thm:lattice_trim}
If $\trip(G)$ is a lattice, then it is a trim lattice.  Every trim lattice can be realized as an independence poset for a unique (up to isomorphism) acyclic directed graph $G$.
\end{theorem}

The class of independence posets therefore includes all distributive lattices, Tamari lattices, Cambrian lattices, Fuss-Cambrian lattices, and torsion pairs of finite type tilted Artin algebras.  We construct the underlying graph $G$ for distributive and Cambrian lattices in~\Cref{sec:examples}.

Many of these examples have naturally-defined cyclic actions on their elements; \Cref{eq:global_row} defines \defn{rowmotion} on independence posets, a common generalization of these cyclic actions. We show in \Cref{thm:main_thm} that rowmotion can be computed in two other ways: as a walk on the Hasse diagram of the independence poset, and as a composition of reorientations of the underlying directed graph.  This first method computes rowmotion within a \emph{fixed} independence poset (\defn{rowmotion in slow motion}), while the second relies on a sequence of bijections between independence posets for different orientations of the same underlying undirected graph (\defn{rowmotion by deformotion}).

\section{Independent sets and tight orthogonal pairs}
 We always take $G$ to be a finite acyclic directed graph; by acyclic, we mean that $G$ contains no oriented cycles. The transitive closure of $G$ defines a poset, which we refer to as \defn{$G$-order}.  Our convention is that $g_1\geq g_2$ in $G$-order if and only if there is a directed path in $G$ from $g_1$ to $g_2$; when we compare vertices of $G$, we will always mean a comparison in $G$-order.  We write $\ell$ for a linear extension of $G$-order, and $\ell'$ for a reverse linear extension of $G$-order.  We write $\simeq$ for an isomorphism of posets.
 
Recall that an \defn{independent set} $\mathcal{A} \subseteq G$ is a set of pairwise non-adjacent vertices of $G$.  As we now explain, the orientation provided by $G$ allows us to complete an independent set to a pair of independent sets, either of which determines the other.

\begin{definition}
A pair $(\al,\br)$ of independent sets of $G$ is called \defn{orthogonal} if there is no edge in $G$ from an element of $\al$ to an element of $\br$.  An orthogonal pair of independent sets $(\al,\br)$ is called \defn{tight} if whenever any element of $\al$ is increased (removed and replaced by a larger element with respect to $G$-order) or any element of $\br$ is decreased, or a new element is added to either $\al$ or $\br$, then the result is no longer an orthogonal pair of independent sets.  We abbreviate {\bf t}ight {\bf o}rthogonal {\bf p}air by \defn{top}, and we write \defn{$\trip(G)$} for the set of all tops of $G$.
\label{def:top}
\end{definition}

Some examples are given in~\Cref{fig:first_examples}.  \Cref{thm:trip_ind} shows that an independent set can be completed to a tight orthogonal pair in exactly two ways.

\begin{figure}[htbp]
\[\begin{array}{cc|cc}
\scalebox{.7}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=join,text=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=meet] at (2,0) {3};
\node (4) [circle,thick,draw,fill=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}&
\scalebox{.7}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}&
\scalebox{.7}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=meet] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}&
\scalebox{.7}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=join,text=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}\\
\scalebox{0.7}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}&
\scalebox{0.7}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=join,text=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=white] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}&
\scalebox{0.7}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=join,text=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}&
\scalebox{0.7}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=join,text=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}\\
\multicolumn{2}{c}{\text{Orthogonal, not tight}} & \multicolumn{2}{c}{\text{Tight (and orthogonal)}}
\end{array}\]
\caption{Eight pairs of independent sets $(\al,\br)$ for two different orientations of a path graph.  The blue vertices correspond to the elements of $\al$, while the orange vertices correspond to $\br$. }
\label{fig:first_examples}
\end{figure}

% (see~\Cref{map:oneG,map:zeroG}, and~\Cref{fig:alg_ex23}).



\begin{definition}
Let $g \in G$ and define $G_g$ to be the directed graph obtained by deleting the vertex $g$ from $G$ (along with all edges to $g$), and  $G_g^\circ$ the directed graph obtained by deleting all vertices and edges adjacent to $g$ in $G$ (along with $g$ itself).
\end{definition}


\begin{theorem}
\label{thm:trip_ind}
Let $\mathcal{I}$ be an independent set of a directed acyclic graph $G$.  Then there exists a unique $(\mathcal{I},\br) \in \trip(G)$ and a unique $(\al,\mathcal{I})\in \trip(G)$.
\end{theorem}

\begin{comment}
\begin{proof}
Let $\mathcal{I}$ be an independent set.  We show that~\Cref{map:oneG} produces an element $(\al,\mathcal{I}) \in \trip(G)$ (this algorithm is illustrated in~\Cref{fig:alg_ex23}).  By construction, the output of \Cref{map:oneG} is an orthogonal pair of independent sets.  We claim it is tight.  Suppose the output is not tight.  Then at least one of the following still results in an orthogonal pair of independent sets: (i) some $g \in G$ could be added to $\al$, (ii) some $g' \in \al$ could be increased to $g \in G$, (iii) some $g\in G$ could be added into $\mathcal{I}$, or (iv) some $g' \in \mathcal{I}$ could be decreased to $g\in G$.  Take a maximal $g$ among all such elements.  One verifies that~\Cref{map:oneG} would have added it in, which is a contradiction.

We now show by induction on $|G|$ that given $\mathcal{I}$, the tight orthogonal pair $(\al,\mathcal{I})$ is unique.  The base case for $|G|=1$ is trivial.  We now suppose $(\al,\mathcal{I})$ and $(\al',\mathcal{I})$ are two different tight orthogonal pairs. Let $g$ be minimal in $G$.

If $g \not \in \mathcal{I}$, the restriction of $(\al,\mathcal{I})$ and $(\al',\mathcal{I})$ to $G_g$ are  tight orthogonal pairs of $G_g$; by induction, they must coincide except possibly at $g$.  But since $\al \neq \al'$ then either $\al \subset \al'$ or $\al' \subset \al$, which contradicts tightness.

Otherwise, $g \in \mathcal{I}$.  The restriction of $(\al,\mathcal{I})$ and $(\al',\mathcal{I})$ to  $G_g^\circ$ are now  tight orthogonal pairs of $G_g^\circ$ and coincide.  But by definition, there can be no elements of either $\al$ or $\al'$ adjacent to $g$ and so  $(\al,\mathcal{I})$ and $(\al',\mathcal{I})$ coincide.

A similar argument produces the unique tight orthogonal pair $(\mathcal{I},\br)$. %
\end{proof}
\end{comment}

\begin{algorithm}[htbp]
\DontPrintSemicolon
\KwIn{An acyclic directed graph $G$ and an independent set $\mathcal{I}$.}
\KwOut{An element $(\al,\mathcal{I}) \in \trip(G)$.}
\kwset{$\al=\{\}$}
\For{$k$ in $\ell'$}{
    \lIf{$\left\{\begin{tabular}{l} $k \not \in \mathcal{I}$\\ $i \to k \not \in G$ for $i \in \al$ \\ $k \to i\not \in G$ for $i \in \mathcal{I}$ \end{tabular}\right\}$}{add $k$ to $\al$}
}
\Return $(\al,\mathcal{I})$\;
\caption{The greedy construction of the unique $(\al,\mathcal{I}) \in \trip(G)$ using any reverse linear extension $\ell'$ of $G$-order, given an independent set $\mathcal{I}$.}
\label{map:oneG}
\end{algorithm}

\begin{comment}
\begin{algorithm}[htbp]
\DontPrintSemicolon
\KwIn{An acyclic directed graph $G$ and an independent set $\mathcal{I}$.}
\KwOut{An element $(\mathcal{I},\br) \in \trip(G)$.}
\kwset{$\br=\{\}$}
\For{$k$ in $\ell$}{
    \lIf{$\left\{\begin{tabular}{l} $k \not \in \mathcal{I}$\\ $i \to k \not \in G$ for $i \in \mathcal{I}$ \\ $k \to i\not \in G$ for $i \in \br$ \end{tabular}\right\}$}{add $k$ to $\br$}
}
\Return $(\mathcal{I},\br)$\;
\caption{The greedy construction of the unique $(\mathcal{I},\br) \in \trip(G)$ using any linear extension $\ell$ of $G$-order, given an independent set $\mathcal{I}$.  See~\Cref{fig:alg_ex23} for an example.}
\label{map:zeroG}
\end{algorithm}
\end{comment}

\begin{figure}[htbp]
\begin{center}
$\xymatrix@R-2pc{
&(a) &(b) & (c)\\
 & \raisebox{-0.5\height}{\begin{tikzpicture}[scale=.7]
 	\foreach \i in {0,...,2}{
	  \foreach \j in {0,...,2}{
          \draw[shape=circle,black,fill=white] (\i,\j) circle (.5ex);
      };
	};
    \foreach \i in {0,...,1}{
	  \foreach \j in {0,...,2}{
          \draw[->] (\i+.1,\j) to (\i+.9,\j);
      };
	};
    \foreach \i in {0,...,2}{
	  \foreach \j in {1,...,2}{
           \draw[->] (\i,\j-.1) to (\i,\j-.9);
      };
	};
    \foreach \i in {(0,0),(0,2)}{
          \draw[shape=circle,fill=meet] \i circle (.8ex);
	};
  \end{tikzpicture}} \ar@{|->}[r] &
  \raisebox{-0.5\height}{\begin{tikzpicture}[scale=.7]
  \foreach \i in {0,...,2}{
	  \foreach \j in {0,...,2}{
          \draw[shape=circle,black,fill=white] (\i,\j) circle (.5ex);
      };
	};
    \foreach \i in {0,...,1}{
	  \foreach \j in {0,...,2}{
          \draw[->] (\i+.1,\j) to (\i+.9,\j);
      };
	};
    \foreach \i in {0,...,2}{
	  \foreach \j in {1,...,2}{
           \draw[->] (\i,\j-.1) to (\i,\j-.9);
      };
	};
    \foreach \i in {(0,0),(0,2)}{
          \draw[shape=circle,fill=meet] \i circle (.8ex);
	};
     \foreach \i in {(1,2)}{
          \draw[shape=circle,fill=join] \i circle (.8ex);
	};
  \end{tikzpicture}}  \ar@{|->}[r] & \raisebox{-0.5\height}{\begin{tikzpicture}[scale=.7]
 	\foreach \i in {0,...,2}{
	  \foreach \j in {0,...,2}{
          \draw[shape=circle,black,fill=white] (\i,\j) circle (.5ex);
      };
	};
    \foreach \i in {0,...,1}{
	  \foreach \j in {0,...,2}{
          \draw[->] (\i+.1,\j) to (\i+.9,\j);
      };
	};
    \foreach \i in {0,...,2}{
	  \foreach \j in {1,...,2}{
           \draw[->] (\i,\j-.1) to (\i,\j-.9);
      };
	};
    \foreach \i in {(0,0),(0,2)}{
          \draw[shape=circle,fill=meet] \i circle (.8ex);
	};
     \foreach \i in {(1,0),(1,2),(2,1)}{
          \draw[shape=circle,fill=join] \i circle (.8ex);
	};
  \end{tikzpicture}}\\ \\ \\ \\
   &
  \raisebox{-0.5\height}{\begin{tikzpicture}[scale=.7]
 	\foreach \i in {0,...,2}{
	  \foreach \j in {0,...,2}{
          \draw[shape=circle,black,fill=white] (\i,\j) circle (.5ex);
      };
	};
    \foreach \i in {0,...,1}{
	  \foreach \j in {0,...,2}{
          \draw[->] (\i+.1,\j) to (\i+.9,\j);
      };
	};
    \foreach \i in {0,...,2}{
	  \foreach \j in {1,...,2}{
           \draw[->] (\i,\j-.1) to (\i,\j-.9);
      };
	};
    \foreach \i in {(0,0),(0,2)}{
          \draw[shape=circle,fill=join] \i circle (.8ex);
	};
  \end{tikzpicture}}  \ar@{|->}[r] & \raisebox{-0.5\height}{\begin{tikzpicture}[scale=.7]
 	\foreach \i in {0,...,2}{
	  \foreach \j in {0,...,2}{
          \draw[shape=circle,black,fill=white] (\i,\j) circle (.5ex);
      };
	};
    \foreach \i in {0,...,1}{
	  \foreach \j in {0,...,2}{
          \draw[->] (\i+.1,\j) to (\i+.9,\j);
      };
	};
    \foreach \i in {0,...,2}{
	  \foreach \j in {1,...,2}{
           \draw[->] (\i,\j-.1) to (\i,\j-.9);
      };
	};
    \foreach \i in {(0,0),(0,2)}{
          \draw[shape=circle,fill=join] \i circle (.8ex);
	};
     \foreach \i in {(2,0)}{
          \draw[shape=circle,fill=meet] \i circle (.8ex);
	};
  \end{tikzpicture}}  \ar@{|->}[r] & \raisebox{-0.5\height}{\begin{tikzpicture}[scale=.7]
 	\foreach \i in {0,...,2}{
	  \foreach \j in {0,...,2}{
          \draw[shape=circle,black,fill=white] (\i,\j) circle (.5ex);
      };
	};
    \foreach \i in {0,...,1}{
	  \foreach \j in {0,...,2}{
          \draw[->] (\i+.1,\j) to (\i+.9,\j);
      };
	};
    \foreach \i in {0,...,2}{
	  \foreach \j in {1,...,2}{
           \draw[->] (\i,\j-.1) to (\i,\j-.9);
      };
	};
    \foreach \i in {(0,0),(0,2)}{
          \draw[shape=circle,fill=join] \i circle (.8ex);
	};
     \foreach \i in {(1,1),(2,0),(2,2)}{
          \draw[shape=circle,fill=meet] \i circle (.8ex);
	};
  \end{tikzpicture}} \ar@{|->}[uuuu]_{\row} \\ &(d) &(e) & (f)}$
  \end{center}
\caption{The progression $(a)\mapsto(b)\mapsto(c)$ is an illustration of~\Cref{map:oneG}, which produces the tight orthogonal pair $(c)$ by greedily adding elements to the independent set $(a)$ in a reverse linear extension of $G$-order (from the top left to the bottom right).  The progression $(d)\mapsto(e)\mapsto(f)$ illustrates the dual procedure, which greedily adds elements to the independent set $(d)$ in a linear extension of $G$-order (from the bottom right to the top left).  Rowmotion, defined by~\Cref{eq:global_row}, sends $(f)$ to $(c)$.}
\label{fig:alg_ex23}
\end{figure}



\section{Independence posets}

We specify cover relations to define a poset structure on the tight orthogonal pairs of $G$.

\subsection{Flips}

\begin{definition}
The \defn{flip} of $(\al,\br) \in \trip(G)$ at an element $g \in G$ is the tight orthogonal pair $\tog_g(\al,\br)$ defined as follows (see~\Cref{fig:a_toggle} for an example): if $g \not \in \al$ and $g \not \in \br$, the flip does nothing.  Otherwise, preserve all elements of $\al$ that are not less than $g$ and all elements of $\br$ that are not greater than $g$ (and delete all other elements); after switching the set to which $g$ belongs, then greedily add elements to $\al$ and $\br$ (respecting the conditions to form an orthogonal pair) in the orders $\ell'$ and $\ell$, respectively.
\label{def:flip}
\end{definition}

 \Cref{fig:a_toggle} illustrates a flip on a  tight orthogonal pair in an orientation of $[7]\times [7]$.  
 
\begin{proposition}
\label{prop:flips_work}
For $g\in G$, $\tog_g(\al,\br)\in \trip(G)$.
\end{proposition}

\begin{proof}
The statement follows from the restriction of~\Cref{thm:trip_ind} to the elements of $G$ not less than $g$ and to the elements not greater than $g$.
\end{proof}

\begin{lemma}  Let $g$ be an element of an acyclic directed graph $G$.  Then $\tog_g^2(\al,\br) = (\al,\br).$  If $h$ is incomparable with $g$ in $G$-order, then $\tog_g \circ \tog_h = \tog_h \circ \tog_g$.
\label{lem:flips_invs}
\end{lemma}

\begin{figure}[htbp]
\begin{center}
\raisebox{-0.5\height}{\begin{tikzpicture}[scale=.65]
	\tikzmath{\n=6;\m=6;};
    \node at (3.3,3.2) {$g$};
    \node[anchor=west] at (0,6.6) {$\textcolor{join}{\bullet}$ stays};
    \node[anchor=east] at (6,-.6) {$\textcolor{meet}{\bullet}$ stays};
    \node[anchor=east] at (6,6.6) {$\textcolor{meet}{\bullet},\textcolor{join}{\bullet}$ stay};
     \node[anchor=west] at (0,-.6) {$\textcolor{meet}{\bullet},\textcolor{join}{\bullet}$ stay};
 	\foreach \i in {0,...,\n}{
	  \foreach \j in {0,...,\m}{
          \draw[shape=circle,black,fill=white] (\i,\j) circle (.5ex);
      };
	};
    \foreach \i in {0,...,5}{
	  \foreach \j in {0,...,\m}{
          \draw[->] (\i+.1,\j) to (\i+.9,\j);
      };
	};
    \foreach \i in {0,...,6}{
	  \foreach \j in {1,...,\m}{
           \draw[->] (\i,\j-.1) to (\i,\j-.9);
      };
	};
    \foreach \i in {(0,6),(0,4),(0,1),(1,2),(1,0),(2,4),(2,1),(3,5),(3,3),(3,0),(5,4),(5,2),(5,0),(6,6),(6,1)}{
          \draw[shape=circle,fill=meet] \i circle (.8ex);
	};
     \foreach \i in {(0,3),(1,6),(3,2),(4,6),(4,3),(4,1),(6,5),(6,3),(6,0)}{
          \draw[shape=circle,fill=join] \i circle (.8ex);
	};
    \draw[dotted] (-1,2.5) to (3.5,2.5) to (3.5,7);
    \draw[dotted] (7,3.5) to (2.5,3.5) to (2.5,-1);
  \end{tikzpicture}}
$\xleftrightarrow{\tog_g}$
\raisebox{-0.5\height}{
\begin{tikzpicture}[scale=.65]
	\tikzmath{\n=6;\m=6;};
    \node at (3.3,3.2) {$g$};
    \node[anchor=west] at (0,6.6) {$\textcolor{join}{\bullet}$ stays};
    \node[anchor=east] at (6,-.6) {$\textcolor{meet}{\bullet}$ stays};
    \node[anchor=east] at (6,6.6) {$\textcolor{meet}{\bullet},\textcolor{join}{\bullet}$ stay};
     \node[anchor=west] at (0,-.6) {$\textcolor{meet}{\bullet},\textcolor{join}{\bullet}$ stay};
 	\foreach \i in {0,...,\n}{
	  \foreach \j in {0,...,\m}{
          \draw[shape=circle,black,fill=white] (\i,\j) circle (.5ex);
      };
	};
    \foreach \i in {0,...,5}{
	  \foreach \j in {0,...,\m}{
          \draw[->] (\i+.1,\j) to (\i+.9,\j);
      };
	};
    \foreach \i in {0,...,6}{
	  \foreach \j in {1,...,\m}{
           \draw[->] (\i,\j-.1) to (\i,\j-.9);
      };
	};
    \foreach \i in {(0,5),(0,1),(1,4),(1,2),(1,0),(2,5),(2,3),(2,1),(3,6),(3,4),(3,0),(5,4),(5,2),(5,0),(6,6),(6,1)}{
          \draw[shape=circle,fill=meet] \i circle (.8ex);
	};
     \foreach \i in {(0,3),(1,6),(3,3),(4,6),(4,1),(6,5),(6,3),(6,0)}{
          \draw[shape=circle,fill=join] \i circle (.8ex);
	};
    \draw[dotted] (-1,2.5) to (3.5,2.5) to (3.5,7);
    \draw[dotted] (7,3.5) to (2.5,3.5) to (2.5,-1);
  \end{tikzpicture}}\end{center}
\caption{A flip on a top $(\al,\br)$ in the $7\times 7$ grid oriented from top left to bottom right.  As in~\Cref{fig:first_examples}, the blue vertices correspond to the elements of $\al$, while the orange vertices correspond to the elements of $\br$.  Flipping at the vertex $g$ changes its color, and divides the grid into 5 connected regions (delineated by the dotted lines): the blue vertices not less than $g$ (i.e., not in the bottom right) and the orange vertices not greater than $g$ (i.e., not in the top left) are preserved by the flip.  The orange vertices in the top left are filled in greedily from bottom right to top left; the blue vertices in the bottom right are filled in greedily from top left to bottom right.}
\label{fig:a_toggle}
\end{figure}

\subsection{Independence Relations}
For $G$ an acyclic directed graph, the \defn{independence relations} on $\trip(G)$ are the reflexive and transitive closure of the relations $(\al,\br) < (\al',\br')$ if there is some $g \in \br$ such that $\tog_g(\al,\br)=(\al',\br')$.  

\begin{lemma} Independence relations are antisymmetric, and hence define an \defn{independence poset}, denoted $\trip(G)$.  Flips and cover relations of $\trip(G)$ coincide.\label{lem:flip_eq_cov}
\end{lemma}

\begin{comment}
\begin{proof}
Note that the relation is antisymmetric: any upwards flip from $(\al,\br)$ at $g$
introduces the new element $g$ into $\al$, and the only way to remove it by a subsequent upwards flip is to flip at an element higher than $g$, which then introduces a new element not in $\al$.  No such sequence of flips can therefore terminate at $(\al,\br)$, and so the relation is antisymmetric.


By the definition of $\trip(G)$, every cover relation of $G$
is induced by a flip.
Suppose now that there is some $(\al,\br)\in\trip(G)$, and some $g$
in $\br$, so that $(\al',\br')=\tog_g(\al,\br)>(\al,\br)$.
What has to be checked is that there is no longer sequence of upward flips which
also interpolates between $(\al,\br)$ and $(\al',\br')$.  Any upwards flip from $(\al,\br)$ at $h$ not below
$g$ would introduce the new element $h$ into $\al$, which is not in $\al'$; the only way to remove it by a subsequent upwards flip is to flip at an element higher than $h$, which then introduces a new element not in $\al'$ into $\al$.  No such sequence of flips can therefore terminate at $(\al',\br')$.  Dually, any
upwards flip at $h$ not below $g$ removes an element from $\br$ which is contained in $\br'$, and the only way to restore it is to flip at a still lower element, which removes a different element of $\br'$ from $\br$.  Similarly,
therefore, no such sequence of upwards flips can therefore terminate at $(\al',\br')$.
\end{proof}
\end{comment}

By~\Cref{lem:flip_eq_cov}, the maximum element of $\trip(G)$ is the unique  tight orthogonal pair $\hat{1}$ of the form $(\al,\emptyset)$, and its minimum element $\hat{0}$ is of the form $(\emptyset,\br)$.  

\begin{figure}[htbp]
\raisebox{-0.5\height}{\begin{tikzpicture}[scale=1.4]
\node (a) [align=center] at (0,0) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=meet] at (2,0) {3};
\node (4) [circle,thick,draw,fill=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (b) [align=center] at (-1,1) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=meet] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (c) [align=center] at (1,2) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (f) [align=center] at (-1,2) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=join,text=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=meet] at (2,0) {3};
\node (4) [circle,thick,draw,fill=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (d) [align=center] at (1,1) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=join,text=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (e) [align=center] at (1,3) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=meet] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (g) [align=center] at (-1,3) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=join,text=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (i) [align=center] at (0,4) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=join,text=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\draw[-,thick] (a) to  (b) to  (e) to  (i);
\draw[-,thick] (b) to (f) to (g);%to ();
\draw[-,thick] (d) to (c) to (e);%to ();
%\draw[-,thick] (a) to  (c) to  (e);
\draw[-,thick] (g) to (i);
\draw[-,thick] (a) to (d);
%\draw[-,thick] (c) to (f) to (h) to (i);
\draw[-,thick] (d) to  (g);
%\draw[-,thick,color=join,line width=2pt] (a) to (c) to  (f) to (h) to (i);
\end{tikzpicture}} \hfill
\raisebox{-0.5\height}{\begin{tikzpicture}[scale=1.4]
\node (a) [align=center] at (0,0) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (b) [align=center] at (-1,1) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=meet] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (c) [align=center] at (2,2) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=join,text=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (f) [align=center] at (0,2) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=meet] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (d) [align=center] at (1,1) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=meet] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (e) [align=center] at (1,3) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=join,text=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=meet] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (g) [align=center] at (-1,3) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=join,text=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=white] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (i) [align=center] at (0,4) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=join,text=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\draw[-,thick] (a) to  (b);
\draw[-,thick] (f) to (e) to  (i);
\draw[-,thick] (b) to (g);
\draw[-,thick] (b) to (f);
\draw[-,thick] (d) to (f);%to ();
\draw[-,thick] (d) to (c) to (e);%to ();
%\draw[-,thick] (a) to  (c) to  (e);
\draw[-,thick] (g) to (i);
\draw[-,thick] (a) to (d);
%\draw[-,thick] (c) to (f) to (h) to (i);
%\draw[-,thick] (d) to  (g);
%\draw[-,thick,color=join,line width=2pt] (a) to (c) to  (f) to (h) to (i);
\end{tikzpicture}}
\vspace{2em}

\raisebox{-0.5\height}{\begin{tikzpicture}[scale=1.4]
\node (a) [align=center] at (0,0) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=meet] at (2,0) {3};
\node (4) [circle,thick,draw,fill=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (2) to (3);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (b) [align=center] at (-1,1) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=meet] at (2,0) {3};
\node (4) [circle,thick,draw,fill=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (2) to (3);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (c) [align=center] at (1,2) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick](2) to (3);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (f) [align=center] at (-1,2) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=meet] at (1,0) {2};
\node (3) [circle,thick,draw,fill=join,text=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (2) to (3);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (d) [align=center] at (1,1) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=join,text=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick](2) to (3);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (e) [align=center] at (1,3) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=meet] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (2) to (3);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (g) [align=center] at (-1,3) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=join,text=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (2) to (3);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (i) [align=center] at (0,4) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=join,text=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (2) to (3);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\draw[-,thick] (a) to (b) to (f) to (g) to (i);
\draw[-,thick] (a) to (d) to (c) to (e) to (i);
\draw[-,thick] (d) to (f) to (e);
\end{tikzpicture}} \hfill
\raisebox{-0.5\height}{\begin{tikzpicture}[scale=1.4]
\node (a) [align=center] at (0,0) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=meet] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (b) [align=center] at (-1,1) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=meet] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (c) [align=center] at (2,2) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=meet] at (2,0) {3};
\node (4) [circle,thick,draw,fill=white] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (f) [align=center] at (0,2) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=join,text=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (d) [align=center] at (1,1) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=join,text=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=meet] at (2,0) {3};
\node (4) [circle,thick,draw,fill=white] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (e) [align=center] at (1,3) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=join,text=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=meet] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (g) [align=center] at (-1,3) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=meet] at (0,0) {1};
\node (2) [circle,thick,draw,fill=join,text=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (i) [align=center] at (0,4) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=join,text=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=join,text=white] at (3,0) {4};
\draw[->,thick] (1) to (2);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\draw[-,thick] (a) to  (b);
\draw[-,thick] (f) to (e) to  (i);
\draw[-,thick] (b) to (g);
\draw[-,thick] (d) to (f) to (g);%to ();
\draw[-,thick] (d) to (c) to (e);%to ();
%\draw[-,thick] (a) to  (c) to  (e);
\draw[-,thick] (g) to (i);
\draw[-,thick] (a) to (d);
%\draw[-,thick] (c) to (f) to (h) to (i);
%\draw[-,thick] (d) to  (g);
%\draw[-,thick,color=join,line width=2pt] (a) to (c) to  (f) to (h) to (i);
\end{tikzpicture}}
\caption{Independence posets for four orientations of a path of length $4$.  Each poset has eight elements (the tops drawn in blue and orange as in~\Cref{fig:first_examples,fig:a_toggle}), corresponding to the eight independent sets in the underlying undirected graph.  The top left poset is not a lattice, the bottom left poset is a distributive lattice, and both posets on the right are trim lattices.}
\label{fig:examples}
\end{figure}
%\end{comment}

%\label{sec:flip}


\begin{comment}
\begin{algorithm}[htbp]
\DontPrintSemicolon
\KwIn{$(\al,\br) \in \trip(G)$ and $g \in G$.}
\KwOut{$(\al',\br') \in \trip(G)$.}
\kwset{$\al'=\{k : k \in \al \text{ and } k \not \leq g\}$ and $\br'=\{k : k \in \br \text{ and } k \not \geq g\}$\;}
\lIf{$g \not \in \br$ and $g \not \in \al$}{\Return $(\al,\br)$}
\lElseIf{$g \in \br$}{$\al'=\al'\cup\{g\}$}
\lElseIf{$g \in \al$}{$\br'=\br'\cup\{g\}$}
\For{$k$ in $\ell'$}{
    \lIf{$\left\{\begin{tabular}{l}$k \not \geq g$, $k \not \in \br$ \\$k\to i\not \in G$ for $i \in \br$ \\$i \to k\not \in G$ for $i\in \al$  \end{tabular}\right\}$}{add $k$ to $\al'$}
}
\For{$k$ in $\ell$}{
    \lIf{$\left\{\begin{tabular}{l}$k \not \leq g$, $k \not \in \al$\\ $i\to k \not \in G$ for $i \in \al$\\ $k \to i\not \in G$ for $i\in \br$\end{tabular}\right\}$}{add $k$ to $\br'$}
}
\Return $(\al',\br')$\;
\caption{The definition of a flip of $(\al,\br) \in \trip(G)$ at an element $g \in G$, written $\tog_g(\al,\br)$.  As usual, $\ell$ is a linear extension of $G$-order, while $\ell'$ is a reverse linear extension.}
\label{map:flip}
\end{algorithm}
\end{comment}


\subsection{Tight orthogonal pair recursion}
\label{sec:recursion}
For any $g \in G$, since $\{g\}$ is an independent set of $G$, by~\Cref{thm:trip_ind} there is a unique  tight orthogonal pair $m_g$ of the form $(\al,\{g\})$, and a unique  tight orthogonal pair $j_g$ of the form $(\{g\},\br)$.  Write \begin{equation}\trip_g(G):=[\hat{0},m_g]  \text{ and } \trip^g(G):=[j_g,\hat{1}].\end{equation}  We say that $g \in G$ is \defn{extremal} if it is a minimal or maximal element of $G$-order.

\begin{lemma}
\label{lem:decomposition}
Let $G$ be an acyclic directed graph.  If $g$ is an extremal element of $G$, then $\trip(G) = \trip_g(G) \sqcup \trip^g(G)$ .  Furthermore,
\begin{itemize}
\item If $g$ is minimal, $(\al,\br) \in \trip_g(G)$ if and only if $g \in \br$, and \item If $g$ is maximal, $(\al,\br) \in \trip^g(G)$ if and only if $g \in \al$.
\end{itemize}
In particular, if $x \in \trip^g(G)$ and $y \in \trip_g(G)$, then $x \not \leq y$.
\end{lemma}


\begin{comment}
\begin{proof}
Suppose $g$ is a minimal element of $G$ and let $(\al,\br) \in \trip(G)$.

If $g \in \br$, then by successively flipping in any order all elements not equal to $g$ that only cause us to move up in $\trip(G)$, we must end with the element $m_g$ and so $(\al,\br) \in \trip_g(G)$.  For certainly $g \in \br$ since it started out in $\br$ and flipping at elements of $G$ not equal to $g$ does not remove $g$ from $\br$, since $g$ is minimal.  And $g$ is the only element of $\br$, or we would have flipped more elements out.

If $(\al,\br) \in \trip_g(G)$, then there is a sequence of flips that take us upwards to $m_g$.  This sequence cannot remove $g$ (since it could never be replaced), and so $g \in \br$.

If $g \in \al$, or if $g \not \in \al\cup \br$, then we wish to successively flip in any order all elements not equal to $g$ that only cause us to move down in $\trip(G)$.  We claim that this must end with the element $j_g$ so that $(\al,\br) \in \trip^g(G)$.  Since the poset is finite, the process ends.  Let $(\al',\br')$ be the end of this flip sequence.  Then we claim $g \in \al'$ at this point.  Note that $\al'$ cannot contain any element $h \in G$ adjacent to $g$ (or we would have flipped $h$ out), so that $g$ can be added to $\al'$---unless $g \in \br'$.  But $g$ cannot be in $\br'$, since it was not in $\br$, and only toggling at $g$ could add it in.


The dual argument applies when $g$ is maximal.
\end{proof}
\end{comment}

\begin{lemma}
For any element $g \in G$, if $g \in \al$ then $(\al,\br) \in \trip^g(G)$; and if $g \in \br$ then $(\al,\br)\in \trip_g(G)$.
\label{lem:extremal_needs}
\end{lemma}

\begin{comment}
\begin{proof}
If $g \in \al$, then we construct a path downwards in $\trip(G)$ from $(\al,\br)$ to $j_g$.  First, flip out all elements greater than $g$ in reverse linear extension order. This does not cause $g$ to enter into $\br$ (since all elements in $\br$ less than $h$ are fixed by flips).
Since $g$ can be added to $\al$ at the end of this sequence of flips, it is indeed in $\al$ (though it may not have stayed in it all the time during the sequence).  Now flip out all the remaining elements of $\al$ other than $g$. None of the remaining elements is above $g$, so this will neither remove $g$ nor introduce elements in $\al$ above $g$.
The process necessarily terminates with $j_g$.  Again, the statement for $\br$ follows dually.
\end{proof}
\end{comment}



\begin{lemma}
Let $G$ be a directed acyclic graph.
\begin{itemize}
\item If $g$ is minimal and $(\al,\br) \in \trip_g(G)$, then $\tog_g(\al,\br)=(\al\cup \{g\},\br')$ for some $\br'$.
\item If $g$ is maximal and $(\al,\br) \in \trip^g(G)$, then $\tog_g(\al,\br)=(\al',\br\cup\{g\})$ for some $\al'$.
\end{itemize}
\label{lem:down}
\end{lemma}

\begin{proof}
This follows from the definition of flip; when $g$ is minimal, all of $\al$ is preserved since every element of $\al$ is not less than $g$.  Similarly, when $g$ is maximal, all of $\br$ is preserved, since every element of $\br$ is not greater than $g$.
\end{proof}

\begin{theorem}
\label{thm:decomposition}
Let $g$ be an extremal element of an acyclic directed graph $G$.  Then \begin{align*} (\al,\br)&\mapsto (\al ,\br \setminus \{g\}\} \text{ is a bijection } \begin{cases} \trip_g(G)\simeq\trip(G_g^\circ) & \text{if } g \text{ minimal} \\ \trip_g(G)\simeq\trip(G_g) & \text{if } g \text{ maximal} \end{cases} \\
  (\al,\br) &\mapsto (\al \setminus \{g\},\br\} \text{ is a bijection } \begin{cases} \trip^g(G)\simeq\trip(G_g) & \text{if } g \text{ minimal} \\ \trip^g(G)\simeq\trip(G_g^\circ) & \text{if } g \text{ maximal} \end{cases}\end{align*}
\end{theorem}

\begin{proof}
We only prove the results for $g$ minimal, the case for $g$ maximal being analogous.  We first show $\trip_g(G)\simeq\trip(G_g^\circ)$; by~\Cref{lem:decomposition}, $(\al,\br) \in \trip_g(G)$ if and only if $g \in \br$.  But since $(\al,\br)$ is a tight orthogonal pair, no element of $\al$ or of $\br$ can be adjacent to $g$, from which we conclude the result by definition of $G_g^\circ$.  We now show $\trip^g(G)\simeq\trip(G_g)$; since $\trip(G) = \trip_g(G) \sqcup \trip^g(G)$, by~\Cref{lem:decomposition} elements of $\trip^g(G)$ consist of those  tight orthogonal pairs of $G$ with either $g \in \al$ or $g \not \in \br \cup \al$.  Each tight orthogonal pair of $G_g$ can be uniquely extended to such a tight orthogonal pair.
\end{proof}


\subsection{Examples}
\label{sec:examples}
Let $P$ be a poset with corresponding distributive lattice $J(P)$.  Then the dual of the comparability graph $G$ of $P$---defined by $p_2 \to p_1$ in $G$ if and only if $p_1 \leq p_2$ in $P$---satisfies $\trip(G)\simeq J(P)$.

Following \cite{TW}, a Cambrian lattice may be realized as $\trip(G)$  for $G$ constructed as follows.  An example appears in~\Cref{fig:tamari}; non-experts may ignore the description below---\Cref{fig:tamari} can still be appreciated as an example of an independence poset without knowing where the underlying graph comes from.  For $c=a_1 a_2 \cdots a_n$ a permutation of the simple reflections of a $W$, Reading's \defn{$c$-sorting word} for the long element of $W$ is the leftmost reduced word for $w_\circ$ in the word $c^\infty$: $w_\circ(c) = a_{1}a_2 \cdots a_{N} \text{ with each } a_i \in S.$  $G$ then has vertex set $[N]$ (indexing the reflections of $W$) and a directed edge $j\to i$ iff $j>i$ and $(a_i \cdots a_{j-1}) a_j (a_{j-1} \cdots a_i)$ does not lie in the parabolic subgroup of $W$ generated by all simple reflections except $a_i$.


\begin{figure}[htbp]
\begin{center}
\scalebox{0.8}{
\begin{tikzpicture}[scale=2.1]
\node (a) at (0,-1) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=meet,text=black,fill=white]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=meet,text=black,fill=meet] at (-1,0) {3};
\node (4) [circle,thick,draw,color=meet,text=black,fill=white] at (.5,0) {4};
\node (5) [circle,thick,draw,color=meet,text=black,fill=white] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (b) at (-1,1) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=meet,text=black,fill=white]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=meet,text=black,fill=meet] at (-1,0) {3};
\node (4) [circle,thick,draw,color=white,text=black] at (.5,0) {4};
\node (5) [circle,thick,draw,color=white,text=black] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=join,fill=join,text=white] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (c) at (0,1) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=join,fill=join,text=white] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=meet,text=black,fill=meet]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=meet,text=black,fill=white] at (-1,0) {3};
\node (4) [circle,thick,draw,color=meet,text=black,fill=white] at (.5,0) {4};
\node (5) [circle,thick,draw,color=meet,text=black,fill=white] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (d) at (1,2) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=join,text=black,fill=white] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=join,fill=join,text=white]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=meet,text=black,fill=meet] at (-1,0) {3};
\node (4) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,0) {4};
\node (5) [circle,thick,draw,color=meet,text=black,fill=white] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=meet,text=black,fill=white] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (e) at (3,2) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=white,text=black]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=join,fill=join,text=white] at (-1,0) {3};
\node (4) [circle,thick,draw,color=meet,text=black,fill=white] at (.5,0) {4};
\node (5) [circle,thick,draw,color=meet,text=black,fill=meet] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=meet,text=black,fill=white] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (f) at (-1,2) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=join,fill=join,text=white] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=meet,text=black,fill=meet]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=meet,text=black,fill=white] at (-1,0) {3};
\node (4) [circle,thick,draw,color=white,text=black] at (.5,0) {4};
\node (5) [circle,thick,draw,color=white,text=black] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=join,fill=join,text=white] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (g) at (2,3) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=join,fill=join,text=white] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=join,text=black,fill=white]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=join,fill=join,text=white] at (-1,0) {3};
\node (4) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,0) {4};
\node (5) [circle,thick,draw,color=meet,text=black,fill=white] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=meet,text=black,fill=white] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (h) at (0,3) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=join,text=black,fill=white] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=join,text=black,fill=white]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=meet,text=black,fill=meet] at (-1,0) {3};
\node (4) [circle,thick,draw,color=join,fill=join,text=white] at (.5,0) {4};
\node (5) [circle,thick,draw,color=meet,text=black,fill=white] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (i) at (-1,4) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=join,text=black,fill=white] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=join,fill=join,text=white]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=meet,text=black,fill=meet] at (-1,0) {3};
\node (4) [circle,thick,draw,color=join,text=black,fill=white] at (.5,0) {4};
\node (5) [circle,thick,draw,color=white,text=black] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=join,fill=join,text=white] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (j) at (1,4) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=join,text=black,fill=white] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=join,text=black,fill=white]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=join,fill=join,text=white] at (-1,0) {3};
\node (4) [circle,thick,draw,color=join,fill=join,text=white] at (.5,0) {4};
\node (5) [circle,thick,draw,color=meet,text=black,fill=meet] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=meet,text=black,fill=white] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (k) at (3,4) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=white,text=black]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=join,text=black,fill=white] at (-1,0) {3};
\node (4) [circle,thick,draw,color=white,text=black] at (.5,0) {4};
\node (5) [circle,thick,draw,color=join,fill=join,text=white] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (l) at (2,5) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=join,fill=join,text=white] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=join,text=black,fill=white]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=join,text=black,fill=white] at (-1,0) {3};
\node (4) [circle,thick,draw,color=join,text=black,fill=white] at (.5,0) {4};
\node (5) [circle,thick,draw,color=join,fill=join,text=white] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (m) at (3,5) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=meet,text=black,fill=meet] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=white,text=black]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=join,fill=join,text=white] at (-1,0) {3};
\node (4) [circle,thick,draw,color=white,text=black] at (.5,0) {4};
\node (5) [circle,thick,draw,color=join,text=black,fill=white] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=join,fill=join,text=white] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\node (n) at (2,7) {\scalebox{0.5}{\begin{tikzpicture}[scale=1.4]
\node (1) [circle,thick,draw,color=join,fill=join,text=white] at (.5,-.866) {1};
\node (2) [circle,thick,draw,color=join,fill=white,text=black]  at (-.25,-.433013) {2};
\node (3) [circle,thick,draw,color=join,fill=join,text=white] at (-1,0) {3};
\node (4) [circle,thick,draw,color=join,text=black,fill=white] at (.5,0) {4};
\node (5) [circle,thick,draw,color=join,text=black,fill=white] at (-.25,.433013) {5};
\node (6) [circle,thick,draw,color=join,fill=join,text=white] at (.5,.866) {6};
\draw[->,thick] (5) to (4);
\draw[->,thick] (5) to (2);
\draw[->,thick] (6) to (4);
\draw[->,thick] (4) to (1);
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (2);
\draw[->,thick] (5) to (3);
\draw[->,thick] (6) to (5);
\end{tikzpicture}}};
\draw[-,thick,color=join,line width=2pt] (a) to node[midway, left] {$6$} (b);
\draw[-,thick,color=join,line width=2pt] (a) to node[midway, right] {$1$} (c) to node[midway, left] {$6$} (f);
\draw[-,thick,color=join,line width=2pt] (a) to node[midway, right] {$3$} (e) to node[midway, right] {$5$} (k) to node[midway, right] {$6$} (m);
\draw[-,thick,color=join,line width=2pt] (c) to node[midway, right] {$2$} (d) to node[midway, left] {$4$} (h) to node[midway, left] {$6$} (i);
\draw[-,thick,color=join,line width=2pt] (d) to node[midway, right] {$3$} (g) to node[midway, right] {$4$} (j) to node[midway, left] {$5$} (l) to node[midway, left] {$6$} (n);
\draw[-,thick] (b) to node[midway, left] {$1$} (f) to node[midway, left] {$2$} (i) to node[midway, left] {$3$} (n);
\draw[-,thick] (e) to node[midway, right] {$1$} (g);
\draw[-,thick] (h) to node[midway, left] {$3$} (j);
\draw[-,thick] (k) to node[midway, left] {$1$} (l);
\draw[-,thick] (b) to node[midway, left] {$3$} (m);
%\draw[-,thick] (j) to node[midway, left] {$6$} (l);
\draw[-,thick] (m) to node[midway, right] {$1$} (n);
\end{tikzpicture}}
\end{center}
\caption{The Tamari lattice with 14 elements, realized as an independence poset.  The thick blue edges indicate the tree structure provided by the natural labelling, giving an efficient method to generate all independent sets of the underlying graph.  The filling of the vertices of the graph specify the tight orthogonal pairs, while the color of the boundaries specify the maximal orthogonal pair.}
\label{fig:tamari}
\end{figure}

\section{Trim lattices and Maximal Orthogonal Pairs}


\subsection{Extremal lattices}

A \defn{chain} in a poset is a sequence of elements $\x_0 < \x_1 < \cdots < \x_r,$ of \defn{length} $r$.  The poset $\trip(G)$ has a maximal chain of length $|G|$ obtained by starting at $\hat{0}$ and flipping the elements of $G$ in the order of a linear extension of $G$-order.

\begin{lemma}
\label{lem:max_chain}
For $G$ an acyclic directed graph with $g_1,\ldots,g_{|G|}$ a linear extension of $G$-order, the sequence \[\hat{0} \lessdot \tog_{g_1}(\hat{0}) \lessdot (\tog_{g_2}\circ \tog_{g_1})(\hat{0})\lessdot \ldots \lessdot (\tog_{g_{|G|}}\circ\cdots\circ \tog_{g_1})(\hat{0})=\hat{1}\] is a maximal chain in $\trip(G)$.
\end{lemma}

\begin{proof}
Write $(\al_i,\br_i)$ for the $i$th element of the sequence.  By~\Cref{lem:flip_eq_cov}, this sequence is unrefinable.  By induction, after the $i$th step all elements of $\br_i$ lie above $\{g_1,\ldots,g_i\}$ and all elements of $\al_i$ are contained in $\{g_1,\ldots,g_i\}$.  Furthermore, since each $\br_i$ is computed greedily in linear extension order, $g_{i+1} \in \br_i$.  The sequence must end with $\hat{1}$, because the only way for all elements of $\br_{|G|}$ to lie above $\{g_1,\ldots,g_{|G|}\}$ is for $\br_{|G|}$ to be empty.
\end{proof}

An \defn{extremal lattice} is a lattice whose longest chain is of length equal to the number of its join irreducible elements and to the number of its meet irreducible elements.  As motivation for our main result of this section, we have the following easy statement (we will refine it in~\Cref{thm:lattice_trim}).

\begin{lemma}
If $\trip(G)$ is a lattice, then it is an extremal lattice.
\label{lem:lattice_implies_extremal}
\end{lemma}

\begin{proof}
A lattice with a chain of length $n$ must have at least $n$ join-irreducible elements and at least $n$ meet-irreducible elements (since each element of the chain is the join of the join-irreducibles beneath it and the meet of the meet-irreducibles above it).  Suppose $\trip(G)$ is a lattice; since it only has $|G|$ join-irreducible and $|G|$ meet-irreducible elements, and since it has a chain of length $|G|$ by~\Cref{lem:max_chain}, it is extremal.
\end{proof}


\begin{comment}
\begin{figure}[htbp]
\begin{center}
\raisebox{-0.5\height}{\begin{tikzpicture}[scale=2]
\node (a) [align=center] at (0,0) {\scalebox{0.3}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=meet,text=black] at (0,0) {1};
\node (2) [circle,very thick,draw,color=meet,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=meet,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=meet,text=black] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (b) [align=center] at (-1,1.5) {\scalebox{0.3}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=meet,text=black] at (0,0) {1};
\node (2) [circle,very thick,draw,color=meet,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=white,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=join,text=black] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (c) [align=center] at (0,1) {\scalebox{0.3}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=join,text=black] at (0,0) {1};
\node (2) [circle,very thick,draw,color=meet,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=meet,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=meet,text=black] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (d) [align=center] at (1,1.5) {\scalebox{0.3}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=meet,text=black] at (0,0) {1};
\node (2) [circle,very thick,draw,color=white,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=join,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=meet,text=black] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (e) [align=center] at (-1,2.5) {\scalebox{0.3}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=join,text=black] at (0,0) {1};
\node (2) [circle,very thick,draw,color=meet,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=white,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=join,text=black] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (f) [align=center] at (0,2.25) {\scalebox{0.3}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=join,text=black] at (0,0) {1};
\node (2) [circle,very thick,draw,color=join,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=meet,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=meet,text=black] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (g) [align=center] at (1,2.5) {\scalebox{0.3}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=meet,text=black] at (0,0) {1};
\node (2) [circle,very thick,draw,color=white,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=join,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=join,text=black] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (h) [align=center] at (0,3) {\scalebox{0.3}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=join,text=black] at (0,0) {1};
\node (2) [circle,very thick,draw,color=join,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=join,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=meet,text=black] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\node (i) [align=center] at (0,4) {\scalebox{0.3}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=join,text=black] at (0,0) {1};
\node (2) [circle,very thick,draw,color=join,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=join,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=join,text=black] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}}};
\begin{pgfonlayer}{background}
\draw[-,thick] (a) to  (b) to  (e) to  (i);
\draw[-,thick] (a) to  (c) to  (e);
\draw[-,thick] (b) to (g) to (i);
\draw[-,thick] (a) to (d) to (h);
\draw[-,thick] (c) to (f) to (h) to (i);
\draw[-,thick] (d) to  (g);
\draw[-,thick] (a) to (c) to  (f) to (h) to (i);
\end{pgfonlayer}
\end{tikzpicture}} \hspace{5em}
\raisebox{-0.5\height}{\begin{tikzpicture}[scale=1.4]
\node (a) [align=center] at (0,0) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=meet,text=black,fill=meet] at (0,0) {1};
\node (2) [circle,very thick,draw,color=meet,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=meet,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=meet,text=black,fill=meet] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (b) [align=center] at (-1,1) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=meet,text=black,fill=meet] at (0,0) {1};
\node (2) [circle,very thick,draw,color=meet,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=meet,text=black,fill=meet] at (2,0) {3};
\node (4) [circle,very thick,draw,color=join,text=white,fill=join] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (c) [align=center] at (2,2) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=join,text=black] at (0,0) {1};
\node (2) [circle,very thick,draw,color=join,text=white,fill=join] at (1,0) {2};
\node (3) [circle,very thick,draw,color=meet,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=meet,text=black,fill=meet] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (f) [align=center] at (0,2) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=join,text=white,fill=join] at (0,0) {1};
\node (2) [circle,very thick,draw,color=meet,text=black,fill=meet] at (1,0) {2};
\node (3) [circle,very thick,draw,color=meet,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=join,text=white,fill=join] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (d) [align=center] at (1,1) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=join,text=white,fill=join] at (0,0) {1};
\node (2) [circle,very thick,draw,color=meet,text=black,fill=meet] at (1,0) {2};
\node (3) [circle,very thick,draw,color=meet,text=black] at (2,0) {3};
\node (4) [circle,very thick,draw,color=meet,text=black,fill=meet] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (e) [align=center] at (1,3) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=join,text=black] at (0,0) {1};
\node (2) [circle,very thick,draw,color=join,text=white,fill=join] at (1,0) {2};
\node (3) [circle,very thick,draw,color=meet,text=black,fill=meet] at (2,0) {3};
\node (4) [circle,very thick,draw,color=join,text=white,fill=join] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (g) [align=center] at (-1,3) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=meet,text=black,fill=meet] at (0,0) {1};
\node (2) [circle,very thick,draw,color=white,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=join,text=white,fill=join] at (2,0) {3};
\node (4) [circle,very thick,draw,color=join,text=black] at (3,0) {4};
\draw[->,thick]  (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\node (i) [align=center] at (0,4) {\scalebox{0.4}{\begin{tikzpicture}
\node (1) [circle,very thick,draw,color=join,text=white,fill=join] at (0,0) {1};
\node (2) [circle,very thick,draw,color=join,text=black] at (1,0) {2};
\node (3) [circle,very thick,draw,color=join,text=white,fill=join] at (2,0) {3};
\node (4) [circle,very thick,draw,color=join,text=black] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (3) to (4);
\end{tikzpicture}}};
\draw[-,thick] (a) to  (b);
\draw[-,thick] (f) to (e) to  (i);
\draw[-,thick] (b) to (g);
\draw[-,thick] (b) to (f);
\draw[-,thick] (d) to (f);%to ();
\draw[-,thick] (d) to (c) to (e);%to ();
%\draw[-,thick] (a) to  (c) to  (e);
\draw[-,thick] (g) to (i);
\draw[-,thick] (a) to (d);
%\draw[-,thick] (c) to (f) to (h) to (i);
%\draw[-,thick] (d) to  (g);
%\draw[-,thick,color=join,line width=2pt] (a) to (c) to  (f) to (h) to (i);
\end{tikzpicture}}
\end{center}
\caption{On the left is the extremal lattice of maximal orthogonal sets of a directed path of length 4, ordered by inclusion of first component; the sets $x_\JJ$ are indicated by a blue border, while the sets $x_\MM$ are drawn with a yellow border.  Because it is not trim, this extremal lattice is not isomorphic to the top left example in~\Cref{fig:examples} (which is not even a lattice).  On the right is the (trim) extremal lattice for a second orientation, which does coincide with the top right example in~\Cref{fig:examples} by~\Cref{thm:trim_is_ind}; maximal orthogonal pairs are indicated by the color of the border, while tight orthogonal pairs are indicated by the color of the filling.}
\label{fig:max_orth}
\end{figure}
\end{comment}

%Following Markowsky~\cite{markowsky1975factorization,markowsky1992primes,TW}, a \defn{{\bf m}aximal {\bf o}rthogonal {\bf p}air} (or mop) in an acyclic directed graph $G$ is a pair of sets $(X,Y)$ such that no edges run from $X$ to $Y$, and such that $X$ and $Y$ are both maximal with respect to this condition.  Markowsky's generalization of Birkhoff's fundamental theorem of finite distributive lattices states that any extremal lattice has a representation $\LL(G)$ as the lattice of maximal orthogonal pairs of a unique (up to isomorphism) acyclic directed graph $G$.


%In~\cite{TW}, we represented extremal lattices in the following way, following a construction of Markowsky~\cite{markowsky1975factorization,markowsky1992primes}.
%Clearly, to each $Y\subseteq G$, there is at most one $X$ such that $(X,Y)$ is a maximal orthogonal pair (and dually).  Then t
Any acyclic directed graph $G$ gives rise to an extremal lattice $\LL(G)$, as follows~\cite{TW,markowsky1975factorization,markowsky1992primes}: for $X,Y \subseteq G$ with $X \cap Y = \emptyset$, we say $(X,Y)$ is an \defn{orthogonal pair} if there is no edge from any $i\in X$ to any $k\in Y$, and we say it is a \defn{maximal orthogonal pair} if $X$ and $Y$ are maximal with that property.   We abbreviate {\bf m}aximal {\bf o}rthogonal {\bf p}air by \defn{mop}.

The extremal lattice $\LL(G)$ is equivalently given by \emph{either} of $(X,Y) \leq (X',Y')$ if and only if $X \subseteq X'$, or $(X,Y) \leq (X',Y')$ if and only if $Y' \subseteq Y.$
Furthermore, the join is computed by intersecting the second terms, while meet is given by the intersection of the first terms.  Conversely, we can associate an acyclic directed grath $G(\LL)$ to any extremal lattice called its \defn{Galois graph} with the property that $\LL(G(\LL))\simeq \LL$.


If $\x$ is an element of an extremal lattice $\LL(G)$ with corresponding maximal orthogonal pair $(X,Y)$, we write $x_\JJ=X$ and $x_\MM=Y$---that is, $x_\JJ$ corresponds to the join-irreducible elements below $x$, while $x_\MM$ corresponds to the meet-irreducible elements above $x$.  We refer to \cite{TW} for further details on extremal lattices, including Markowsky's generalization of Birkhoff's fundamental theorem of distributive lattices to extremal lattices.
 


\subsection{Trim lattices}
An element $x$ of a lattice $\LL$ is called \defn{left modular} if for any $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 \defn{trim lattice} is an extremal left-modular lattice.  We have already shown that if an independence poset is a lattice, then it is extremal.  Our goal is to prove that it is actually trim.  We say that a relation $y<z$ in an extremal lattice $\LL(G)$ is \defn{overlapping} if $y_\MM\cap z_\JJ \neq \emptyset.$

\begin{theorem}[{\cite[Theorem 3.4]{TW}}]
\label{thm:overlapping}
An extremal lattice $\LL(G)$ is trim if and only if every relation is overlapping if and only if every cover relation is overlapping.
\end{theorem}

If a cover relation is overlapping, then it overlaps in a unique element.  We may define the \defn{downward} and \defn{upward labels} of $y \in \LL(G)$ as
\begin{align*}   \down(y)&:= \{\text{the unique element of } x_\MM \cap y_\JJ : \text{ all } x \text{ such that } x \lessdot y\} \text{ and}\\
\up(y)&:= \{\text{the unique element of } y_\MM \cap z_\JJ : \text{ all } z \text{ such that } y \lessdot z\}.
\end{align*}

The downward and upward labels actually associate two independent sets to each element of $\LL$ (we show in \Cref{sec:bijections} that they together form a tight orthogonal pair).

\begin{theorem}[{\cite[Corollary 5.6]{TW}}]
For $\LL$ a trim lattice, $\down$ and $\up$ are both bijections from $\LL$ to the set of independent sets of $G(\LL)$.
\label{thm:down_ind}
\end{theorem}

 In a trim lattice $\LL(G)$, there is a unique meet-irreducible element $m_g$ with $\up(m_g)=\{g\}$, and a unique join-irreducible element $j_g$ with $\down(j_g)=\{g\}$. The following analogues for trim lattices of~\Cref{lem:decomposition} and~\Cref{thm:decomposition} were shown in \cite{TW}.
 \begin{theorem}[{\cite[Lemma 3.10, Proposition 3.11, Proposition 3.12]{TW}}]
Let $g$ be minimal in an acyclic directed graph $G$, and write $\LL_g(G) := [\hat{0},m_g]$ and  $\LL^g(G):=[j_g,\hat{1}].$  Then: $\LL(G) = \LL_g(G) \sqcup \LL^g(G)$, $\LL^g(G)\simeq \LL(G_g)$, $\LL_g(G)\simeq \LL(G_g^\circ)$, and $\x \in \LL_g(G)$ if and only if $g \in \up(\x)$.
\label{thm:trim_recurrence}
\end{theorem}

\subsection{Trim Lattices and Independence Posets}
\label{sec:bijections}

We restate our main theorem relating trim lattices and independence posets, referring to~\cite{TW2} for proofs.

\begin{comment}
\begin{proof}
We argue by induction on $|G|$.  Let $g$ be minimal in $G$.  By \Cref{thm:trim_recurrence}, since $\LL(G)$ is trim, $\LL(G)=\LL_g(G)\sqcup \LL^g(G)$.  Similarly, $\trip(G)=\trip_g(G) \sqcup \trip^g(G)$ by \Cref{thm:decomposition}.  By induction, we conclude the isomorphism on each of $G_g^\circ$ and $G_g$: $\LL_g(G)\simeq \LL(G_g^\circ) \simeq \trip(G_g^\circ) \simeq \trip_g(G)$ and $\LL^g(G)\simeq \LL(G_g) \simeq \trip(G_g) \simeq \trip^g(G)$.  Moreover, this induction respects the labelling of cover relations by the overlapping element (for the mops) and the element flipped (for the tops).

We have only to show now that the cover relations between $\LL_g(G)$ and $\LL^g(G)$ are the same as those for $\trip_g(G)$ and $\trip^g(G)$.  But each element in $\LL_g(G)$ and $\trip_g(G)$ has an edge up by~\Cref{thm:trim_recurrence} (4) and \Cref{lem:down} (labelled by $g$).  The element $x \in \LL_g(G)$ is paired with the unique element $x' \in \LL^g(G)$ satisfying $\down(x')=\down(x)\cup \{g\}$ by \cite[Lemma 3.15]{TW}.  It is evident from the definition of flip that the same rule describes how to pair elements in $\trip_g(G)$ with elements of $\trip^g(G)$.
\end{proof}
\end{comment}

{
\renewcommand{\thetheorem}{\ref{thm:lattice_trim}}
\begin{theorem}
If $\trip(G)$ is a lattice, then it is trim.   Every trim lattice can be realized as an independence poset for a unique (up to isomorphism) acyclic directed graph $G$.
\end{theorem}
\addtocounter{theorem}{-1}
}
\begin{comment}
\begin{proof}
For the first statement, suppose that $\trip(G)$ is a lattice.  By~\Cref{lem:lattice_implies_extremal}, it is therefore an extremal lattice.  We wish to show that every cover relation is overlapping, so that $\trip(G)$ is trim by~\Cref{thm:overlapping}.  Consider the representation of $\trip(G)$ as maximal orthogonal sets, which gives the correspondence $(\al,\br)$ with $(X,Y)$, where $X$ is the set of join-irreducible elements below $(\al,\br)$ and $Y$ is the set of meet-irreducible elements above $(\al,\br)$.  By~\Cref{lem:extremal_needs}, we therefore have that $\al \subseteq X$ and $\br \subseteq Y$.  But if $g \in \br$ and $\tog_g(\al,\br) = (\al',\br')$ is a cover with corresponding maximal orthogonal sets $(X,Y)\lessdot (X',Y')$, then $\al' \cap \br = \{g\} \subseteq X' \cap Y$ and hence the cover relation is overlapping.

For the second statement, we first show that if $\LL(G)$ is trim, then $\LL(G) \simeq \trip(G)$.
We argue by induction on $|G|$.  Let $g$ be minimal in $G$.  By \Cref{thm:trim_recurrence}, since $\LL(G)$ is trim, $\LL(G)=\LL_g(G)\sqcup \LL^g(G)$.  Similarly, $\trip(G)=\trip_g(G) \sqcup \trip^g(G)$ by \Cref{thm:decomposition}.  By induction, we conclude the isomorphism on each of $G_g^\circ$ and $G_g$: $\LL_g(G)\simeq \LL(G_g^\circ) \simeq \trip(G_g^\circ) \simeq \trip_g(G)$ and $\LL^g(G)\simeq \LL(G_g) \simeq \trip(G_g) \simeq \trip^g(G)$.  Moreover, this induction respects the labelling of cover relations by the overlapping element (for the mops) and the element flipped (for the tops).

We have only to show now that the cover relations between $\LL_g(G)$ and $\LL^g(G)$ are the same as those for $\trip_g(G)$ and $\trip^g(G)$.  But each element in $\LL_g(G)$ and $\trip_g(G)$ has an edge up by~\Cref{thm:trim_recurrence} (4) and \Cref{lem:down} (labelled by $g$).  The element $x \in \LL_g(G)$ is paired with the unique element $x' \in \LL^g(G)$ satisfying $\down(x')=\down(x)\cup \{g\}$ by \cite[Lemma 3.15]{TW}.  It is evident from the definition of flip that the same rule describes how to pair elements in $\trip_g(G)$ with elements of $\trip^g(G)$.

Assuming that $\trip(G)$ is a lattice, and thus trim by \Cref{thm:lattice_trim}, it is of the form $\LL(H)$ for some $H$.  We refer to~\cite{TW2} for the proof in this case that $G\simeq H$.
\end{proof}
\end{comment}


\begin{comment}
\begin{proof} In a linear extension $\ell$ of $G$-order, greedily add any element to $\br'$ which can be added, subject to the condition that the set remain orthogonal to $\al'$.
Let $\br$ be the resulting set. Define $\al$ to be the independent set given by \Cref{map:zeroG} such that $(\al,\br)$ is tight orthogonal.

All that is necessary to show is that $\al$ contains $\al'$. Suppose that, as we are constructing $\al$ using \Cref{map:zeroG}, that there is some element $x$ of $\al'$ which we do not add. The reason we do not add it must be because there is some $y \to x$ such that we do add $y$ to $\al$. This element $y$ necessarily has no edge to any element of $\br$.
Since, by the hypothesis on the relative order of $\al'$ and $\br'$, there is also no edge from any element of $\br'$ to $y$, we would in fact have added $y$ into $\br$, which is a contradiction. Therefore $\al$ contains $\al'$ as desired.
\end{proof}

Note that without the assumption on the relative order of $\al'$ and $\br'$, the conclusion of this lemma is false, as demonstrated by the case of the linearly oriented path \raisebox{-0.3\height}{\scalebox{0.6}{$\begin{tikzpicture}
\node (1) [circle,thick,draw,fill=white] at (0,0) {1};
\node (2) [circle,thick,draw,fill=white] at (1,0) {2};
\node (3) [circle,thick,draw,fill=white] at (2,0) {3};
\node (4) [circle,thick,draw,fill=white] at (3,0) {4};
\draw[->,thick] (2) to (1);
\draw[->,thick] (3) to (2);
\draw[->,thick] (4) to (3);
\end{tikzpicture}$}} on four vertices: there is no tight orthogonal pair with $\al\supseteq \{2\}$ and $\br\supseteq\{4\}$.
\end{comment}

\begin{comment}
Assuming that $\trip(G)$ is a lattice, and thus trim by \Cref{thm:lattice_trim}, it is of the form $\LL(H)$ for some $H$.  In this case $G\simeq H$.

\begin{theorem}
If $\trip(G) \simeq \LL(H)$, then $G \simeq H$.
\label{thm:galois_eq}
\end{theorem}
\end{comment}

\begin{comment}
\begin{proof}
The join-irreducibles and meet-irreducibles of the extremal lattice $\LL(H)$ are canonically identified, by \cite[Proposition 2.7]{TW}, and are also identified with the vertices of $H$. 
The vertices of $G$ are likewise canonically identified with the join-irreducibles and the meet-irreducibles of 
$\trip(G)$; and the identification of the join-irreducibles and meet-irreducibles defined in this way is the same as the identification coming from $\LL(H)$. The vertices of $G$ and of $H$ are therefore naturally identified.

Recall from~\cite{TW} that the \defn{spine} of an extremal lattice $\LL(H)$ is the collection of elements lying on maximal-length chains; the spine is a distributive sublattice, isomorphic to the distributive lattice $J(P)$ where $P$ is the poset corresponding to $H$-order.   In $\trip(G)$ the maximal chains of the spine correspond to sequences of flips in which every vertex is flipped once. By \Cref{lem:max_chain} this can certainly be done in any linear extension of $G$-order; in principle, other orders could also be possible. This shows that $G$-order is at least as strong as $H$-order. 

If $g_1 \to g_2$ is an edge of $H$, then $g_1$ is above $g_2$ in $H$-order, so $g_1$ is above $g_2$ in $G$-order, and in particular, $g_1$ is not below $g_2$ in $G$-order.
Suppose, seeking a contradiction, that there were no edge $g_1\to g_2$ in $G$. In this case $(\{g_1\},\{g_2\})$ is an orthogonal pair, and, by \Cref{expand}, there is a top $(\al,\br)$ with $g_1 \in \al$ and $g_2 \in \br$, so $j_{g_1} \leq m_{g_2}$, contradicting the fact that there is an edge $g_1 \to g_2$ in $H$.


It follows that the edges of $H$ are a subset of the edges of $G$. Since $\LL(H)$ is trim, by \Cref{thm:trim_eq}, $\LL(H)\simeq \trip(H)$. If the edges of $H$ were a strict subset of the edges of $G$, $G$ would have more independent subsets than $H$, so $\trip(G)$ would have more vertices than $\LL(H)$, which is a contradiction. Thus $G\simeq H$.
\end{proof}
\end{comment}

\begin{comment}
\Cref{thm:lattice_trim} and \Cref{thm:galois_eq} together imply an isomorphism of tops and mops when $\trip(G)$ is a lattice.

\begin{corollary}
If $\trip(G)$ is a lattice, then $\trip(G) \simeq \LL(G)$.
\label{cor:trip_a_lattice}
\end{corollary}

\begin{proof}
Since $\trip(G)$ is a lattice, it is a trim lattice, and hence is $\LL(H)$ for some directed acyclic graph $H$.  But now $H \simeq G$ by~\Cref{thm:galois_eq}.
\end{proof}
\end{comment}


The cover relations in the lattice of order ideals of a finite poset $\mathcal{P}$ are naturally labelled by elements of $\mathcal{P}$; the map that associates an order ideal to the set of labels on its downward covers is a bijection to the set of antichains of $\mathcal{P}$.  Similarly, the cover relations in a Cambrian lattice on the $c$-sortable elements of a finite Coxeter group $W$ are naturally labelled by reflections; the map that associates a $c$-sortable element to the labels on its downward covers gives a bijection to the set of $c$-noncrossing partitions of $W$.  \Cref{thm:lattice_trim} allows us to simultaneously generalize both of these bijections.

\begin{theorem}
If $\LL(G)$ is a trim lattice and $x \in \LL(G)$, then
$\phi(x) = (\down(x),\up(x))$ is a tight orthogonal pair.  Furthermore, if $\LL(G)$ is trim---or, equivalently, if $\trip(G)$ is a lattice---then $\phi$ is an isomorphism $\LL(G) \simeq \trip(G)$.
\end{theorem}

\begin{comment}
\begin{proof}
 For $g \in G$, write $j_g \in \LL(G)$ for the unique join irreducible with $\down(j_g)=\{g\}$ and $m_g \in \LL(G)$ for the unique meet irreducible element with $\up(m_g)=\{g\}$.  Given a collection of join-irreducible elements $J=\{j_{g_1},\ldots,j_{g_r}\}$ and meet-irreducible elements $M=\{m_{g'_1},\ldots,m_{g'_s}\}$, then there is no edge from an element of the set $\{g_1,\ldots,g_r\}$ to an element of the set $\{g'_1,\ldots,g'_s\}$ if and only if every element of $J$ is below every element of $M$ if and only if the join of $J$ is below the meet of $M$. 

By \Cref{thm:down_ind}, every $x \in \LL(G)$ is associated to a pair of independent sets $(\down(x),\up(x))$.  By \cite[Proposition 4.1]{TW}, \[\bigvee_{g \in \down(x)} j_g = x = \bigwedge_{g \in \up(x)} m_g.\]   By the previous paragraph, there are no edges from any element of $\down(x)$ to any element of $\up(x)$, so the pair $(\down(x),\up(x))$ is orthogonal.

We now argue that $(\down(x),\up(x))$ is tight.   If we increased any element of $\down(x)$ while staying independent, this new set would correspond to $\down(x')$ of some $x' \in \LL(G)$ (by \Cref{thm:down_ind}).  This $x'$ would be strictly greater than $x$---in particular, it would no longer be below every $m_g$ for $g \in \up(x)$, and so $(\down(x),\up(x))$ would no longer be orthogonal.
\end{proof}



\begin{theorem}
If $\LL(G)$ is trim---or, equivalently, if $\trip(G)$ is a lattice---then $\phi$ is an isomorphism $\LL(G) \simeq \trip(G)$.
\label{thm:trim_is_ind}
\end{theorem}
\begin{proof}
We show $\phi$ is an isomorphism by induction on $|G|$: to this end, let $g$ be minimal in $G$.  Recall that $\LL(G)=\LL_g(G)\sqcup \LL^g(G)$ and $\trip(G)=\trip_g(G) \sqcup \trip^g(G)$.  Since $\LL_g(G)\simeq \LL(G_g^\circ)$ and $\trip_g(G) \simeq \trip(G_g^\circ)$ and $x\in \LL_g(G)$ if and only if $g \in \up(x)$ and $(\al,\br)\in\trip_g(G)$ if and only if $g \in \br$, we conclude that $\phi$ is an isomorphism from $\LL_g(G) \simeq \trip_g(G)$.  Similarly, we conclude that $\phi$ is an isomorphism from $\LL^g(G) \simeq \trip^g(G)$, since $\LL^g(G)\simeq \LL(G_g)$ and $\trip^g(G)=\trip(G_g)$.

We have only to show now that the cover relations between $\LL_g(G)$ and $\LL^g(G)$ are the same as those for $\trip_g(G)$ and $\trip^g(G)$.  But this now follows from the same argument as in~\Cref{thm:trim_eq}.
\end{proof}

The recurrence used in~\Cref{thm:trim_is_ind} can be used to show that $\phi$ has the following alternative description.  Given $(X,Y) \in \LL(G)$, construct $(\al,\br) \in \trip(G)$ as follows: $\al$ is obtained from $X$ by greedily choosing elements from $X$ in a reverse linear extension order of $G$-order so that $\al$ remains an independent set; $\br$ is obtained from $Y$ by greedily choosing elements from $Y$ in a linear extension order so that $\br$ remains an independent set.
\end{comment}

\begin{comment}
The inverse of the map $\phi$ is constructed in the following theorem.

\begin{theorem}
 Given $(\al,\br) \in \trip(G)$, set $X=\al$, $Y=\br$, and define
 \begin{enumerate}
\item[$\theta_1$:] add to $Y$ all elements of $G \setminus X$ with no arrow \emph{from} an element of $X$.
\item[$\theta_2$:] add to $X$ all elements of $G \setminus Y$ with no arrow \emph{to} an element of $Y$.
\end{enumerate}
Then both $\theta_1 \circ \theta_2$ and $\theta_2 \circ \theta_1$ are injections $\trip(G) \hookrightarrow \LL(G)$.  
Moreover, if $\trip(G)$ is a lattice, then they coincide and are inverses to $\phi$.
\end{theorem}

In particular, the number of tight orthogonal pairs is always less than or equal to the number of maximal orthogonal pairs. 
\end{comment}

\begin{comment}

\begin{proof}
It is clear that both $\theta_1\circ \theta_2$ and $\theta_2 \circ \theta_1$ have images in $\LL(G)$: $\theta_2 \circ \theta_1$, we cannot add anything to $X$, but we also cannot add anything to $Y$ because it was chosen to be maximal with respect to a subset of $X$---and similarly for $\theta_1 \circ \theta_2$.

For $\theta_2 \circ \theta_1$, we first reconstruct $\al$ from $X$ by greedily choosing elements in $X$ in a reverse linear extension order---$Y$ contains those elements that don't have an arrow from an element of $\al$, so as we scan through $X$, if we see an element without an arrow from our reconstruction of $\al$, we must add it to $\al$ since otherwise it would be in $Y$.  The set $\br$ is now determined by~\Cref{thm:trip_ind}.  A similar argument works for $\theta_1 \circ \theta_2$---we first reconstruct $\br$ from $Y$ by greedily choosing elements in $Y$ in a linear extension order, and then $\al$ is determined.

Finally, when $\trip(G)$ is a lattice, these coincide with the alternative description of $\phi$ given after \Cref{thm:trim_is_ind}.
\end{proof}
\end{comment}



\begin{comment}
\subsection{Conditions on independence lattices}
Overlapping relations in a trim lattice allow us to give a graph-theoretic condition on $G$ for when $\trip(G)$ is a lattice.

\begin{theorem}
\label{thm:five_sets}
For $G$ an acyclic directed graph, $\trip(G)$ is a lattice if and only if $G$ has no partition $G=X_1\sqcup X_2\sqcup X_3\sqcup X_4\sqcup Z$ such that
\begin{enumerate}[(i)]
\item all the $X_i$ are non-empty (but $Z$ may be empty)
	\item every element of $X_3$ has an edge from $X_4$ and to $X_2$
    \item every element of $X_2$ has an edge to $X_1$ and from $X_3$
	\item there are no edges from $X_4$ to $X_2$, from $X_4$ to $X_1$, or from $X_3$ to $X_1$
	\item every element of $Z$ has an edge from $X_4$ and an edge to $X_1$.
    \end{enumerate}
\end{theorem}

\begin{proof}
Suppose $\LL(G)$ is not trim, so that we have a cover relation $(X,Y)\lessdot (X',Y')$ with $Y \cap X' = \emptyset$.  Let $X_4 = X$, $X_3 = X' \setminus X$, $X_2 = Y \setminus Y'$, $X_1 = Y'$, and let $Z$ contain the remaining elements of $G$.  Every element of $X_3$ has an edge from some element of $X_4$ (since otherwise $Y$ should be bigger) and an edge to some element of $X_2$ (since otherwise $X$ should be bigger).  Similarly, every element of $X_2$ has an edge to some element of $X_1$ and an edge from some element of $X_3$.  There are no edges from $X_4$ to $X_2$ or to $X_1$ (this would contradict orthogonality of $(X, Y)$) or from $X_3$ to $X_1$ (this would contradict orthogonality of $(X', Y')$). Every element of $Z$, however, has a edge from $X_4$ and a edge to $X_1$.

Conversely, suppose $\LL(G)$ is trim and consider any partition of $G$ into five sets $X_4, X_3, X_2, X_1,Z$ satisfying conditions (i), (ii), (iii) and (iv).  We will show that condition (v) is violated.  Remove all edges from $X_3$ to $X_2$, so that $(X_4 \cup X_3, X_2 \cup X_1)$ is an orthogonal pair, and can be extended to a maximal orthogonal pair $(X,Y)$.  Adding the edges from $X_3$ to $X_2$ back in, we may find maximal orthogonal pairs of the form $(X\setminus X_3,Y')$ and $(X',Y \setminus X_2)$.  These pairs are comparable, and their overlap $X'\cap Y'$ consists only of vertices of $G$ with an edge from $X_3$, an edge to $X_2$, and no edge from $X_4$ or to $X_1$.
\end{proof}

\end{comment}




\begin{comment}
\section{Toggles}
\label{sec:toggles}
By~\Cref{thm:trip_ind}, the number of elements of $\trip(G)$ is equal to the number of independent sets in the \emph{undirected} graph $G$.  For $g$ a minimal or maximal element of $G$, there is a natural \defn{toggle} operation $\mut_g$ (similar to quiver mutation) that  reverses every edge incident to $g$; this operation induces a bijection between $\trip(G)$ and $\trip(\mut_g(G))$ whose effect essentially interchanges the relative order of a decomposition of $\trip(G)$ into two intervals using the element $g$.

By limiting ourselves to only toggling at maximal elements (or at minimal elements) and only keeping track of the sets $\br$ (or $\al$), this bijection can be computed cleanly at the level of independent sets (see~\Cref{eq:mut2} and ~\Cref{thm:mutation_bijection}).
Some examples of toggles on an orientation of the path of length three are given in~\Cref{fig:toggle}.  See also~\cite{striker2012promotion,striker2016rowmotion}.


Fix an undirected graph $G$ and any element $g \in G$.  In~\cite[Section 3.6]{striker2016rowmotion} and in~\cite{joseph2017toggling}, a \defn{toggle} of an independent set $\mathcal{I}$ of graph $G$ is defined by~\Cref{eq:mut2}
\begin{equation}
\mut_g(\mathcal{I}) = \begin{cases} \mathcal{I} \cup \{g\} & \text{if } g \not \in \mathcal{I} \text{ and } \mathcal{I} \cup \{g\} \text{ is an independent set}, \\ \mathcal{I} \setminus \{g\} & \text{if } g \in \mathcal{I}, \\ \mathcal{I} & \text{ otherwise.} \end{cases}
\label{eq:mut2}
\end{equation}

Toggles appear naturally in independence posets through an operation similar to quiver mutation on the underlying directed graph $G$, but are defined in our context only when $g$ is an extremal element of $G$.  For $g$ an extremal element of $G$, the \defn{toggle} of the graph $G$ at $g$ is the acyclic directed graph $\mut_g(G)$ obtained by reversing all edges incident to $g$.

We have chosen the term ``toggle'' for consistency with~\cite{striker2012promotion,striker2016rowmotion}.  Although \cite{striker2016rowmotion,joseph2017toggling} define toggles as bijections on a fixed set of independent sets, our operation comes from changing the orientation of  the underlying directed graph $G$---and hence the underlying set of tops is not fixed.  We show below that we can restrict to one component of the tops to recover their bijections on independent sets.


It is clear that $\mut_g^2(G)=G$.  When $g$ is extremal, by~\Cref{lem:decomposition} no element of $\trip^g(G)$ lies below an element of $\trip_g(G)$ in $\trip(G)$.  The effect of toggling at $g$ is to reverse the roles of $\trip_g(G)$ and $\trip^g(G)$---roughly, transporting $\trip_g(G)$ above $\trip^g(G)$.  This relationship between $\trip(G)$ and $\trip(\mut_g(G))$ is summarized in~\Cref{thm:mutation_bijection}, and is illustrated in~\Cref{fig:toggle}.


\begin{theorem}
Let $g$ be a minimal element of an acyclic directed graph $G$.  Then
 \begin{itemize} \item $(\al,\br)\mapsto (\al \cup \{g\} ,\br \setminus \{g\})$ is a bijection $\trip_g(G) \simeq \trip^g(\mut_g(G))$,
 \item $(\al,\br)\mapsto (\al \setminus \{g\} ,\br')$ is a bijection $\trip^g(G) \simeq \trip_g(\mut_g(G))$.
 \end{itemize}
Let $g$ be a maximal element of an acyclic directed graph $G$.  Then
 \begin{itemize} \item $(\al,\br)\mapsto (\al',\br \setminus \{g\})$ is a bijection $\trip_g(G) \simeq \trip^g(\mut_g(G))$,
 \item $(\al,\br)\mapsto (\al \setminus \{g\} ,\br \cup \{g\})$ is a bijection $\trip^g(G) \simeq \trip_g(\mut_g(G))$.
 \end{itemize}
\label{thm:mutation_bijection}
\end{theorem}

\begin{proof}
This follows immediately from~\Cref{thm:decomposition}.
\end{proof}

For $g\in G$ extremal, we also write $\mut_g$ for the bijection of~\Cref{thm:mutation_bijection} from $\trip(G) \to \trip(\mut_g(G))$, and call it a \defn{toggle}. By~\Cref{thm:mutation_bijection}, we have that $\mut_g^2(\al,\br)=(\al,\br)$.

Thus, if we limit ourselves to toggling only at minimal elements of $G$ and keeping track of the first components $\al$, then~\Cref{eq:mut2} allows us to compute $\mut_g$ on independent sets.  \Cref{eq:mut2} also applies if we choose only maximal elements of $G$ and look at only the second components $\br$ in~\Cref{thm:mutation_bijection}.


\begin{figure}[htbp]
%\scalebox{.65}{

\scalebox{.65}{
\xymatrix{
\raisebox{-0.6\height}{\begin{tikzpicture}[scale=2]
\node (x0) [align=center] at (0,0) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[->,thick] (b) to (c); \end{tikzpicture}}\\$a$};
\node (x1) [align=center]at (-1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=meet] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[->,thick] (b) to (c); \end{tikzpicture}}\\$b$};
\node (j2) [align=center] at (1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$}; \node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$}; \node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[->,thick] (b) to (c); \end{tikzpicture}}\\$d$};
\node (x2) [align=center] at (-1,2) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=join,text=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[->,thick] (b) to (c); \end{tikzpicture}} \\$c$};
\node (x3) [align=center] at (0,3) {$e$ \\\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[->,thick] (b) to (c); \end{tikzpicture}}};
\draw[-,thick] (x0) to (x1) to (x2) to (x3);
\draw[-,thick] (x0) to (j2) to (x3);
\begin{pgfonlayer}{background}
\fill[red,opacity=0.3] \convexpath{x3,j2}{10pt};
\fill[blue,opacity=0.3] \convexpath{x2,x0,x1,x2}{10pt};
\end{pgfonlayer}
\end{tikzpicture}} \ar[r]^{\mut_3} \ar[d]_(.6){\row}%$\qquad\xmapsto{\mut_3}\qquad$
&
\raisebox{-0.6\height}{\begin{tikzpicture}[scale=2]
\node (x0) [align=center] at (0,0) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[<-,thick] (b) to (c); \end{tikzpicture}} \\$d$};
\node (x1) [align=center] at (-1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[<-,thick] (b) to (c); \end{tikzpicture}} \\$e$};
\node (j2) [align=center] at (1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[<-,thick] (b) to (c); \end{tikzpicture}}\\$a$};
\node (x2) [align=center] at (0,2) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=meet] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[<-,thick] (b) to (c); \end{tikzpicture}}\\$b$};
\node (x3) [align=center] at (0,3) {$c$ \\ \scalebox{.5}{\begin{tikzpicture}[scale=.8] \node (a) [draw=black,circle,thick,fill=white] at (0,0) {$1$}; \node (b) [draw=black,circle,thick,fill=white] at (2,0) {$3$}; \node (c) [draw=black,circle,thick,fill=join,text=white] at (1,1) {$2$}; \draw[<-,thick] (a) to (c); \draw[<-,thick] (b) to (c); \end{tikzpicture}}};
\draw[-,thick] (x0) to (x1) to (x2) to (x3);
\draw[-,thick] (x0) to (j2) to (x2);
\begin{pgfonlayer}{background}
\fill[red,opacity=0.3] \convexpath{x1,x0}{10pt};
\fill[blue,opacity=0.3] \convexpath{x3,j2,x2,x3}{10pt};
\end{pgfonlayer}
\end{tikzpicture}} \ar@{=}[r] &
\raisebox{-0.6\height}{\begin{tikzpicture}[scale=2]
\node (x0) [align=center] at (0,0) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[<-,thick] (b) to (c); \end{tikzpicture}} \\$d$};
\node (x1) [align=center] at (-1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[<-,thick] (b) to (c); \end{tikzpicture}} \\$e$};
\node (j2) [align=center] at (1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[<-,thick] (b) to (c); \end{tikzpicture}}\\$a$};
\node (x2) [align=center] at (0,2) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=meet] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[<-,thick] (b) to (c); \end{tikzpicture}}\\$b$};
\node (x3) [align=center] at (0,3) {\scalebox{.5}{\begin{tikzpicture}[scale=.8] \node (a) [draw=black,circle,thick,fill=white] at (0,0) {$1$}; \node (b) [draw=black,circle,thick,fill=white] at (2,0) {$3$}; \node (c) [draw=black,circle,thick,fill=join,text=white] at (1,1) {$2$}; \draw[<-,thick] (a) to (c); \draw[<-,thick] (b) to (c); \end{tikzpicture}}\\$c$};
\draw[-,thick] (x0) to  (x1) to (x2) to (x3);
\draw[-,thick] (x0) to (j2) to (x2);
\node (cd) at (-.1,3) {};
\node (cc) at (.1,3) {};
\begin{pgfonlayer}{background}
\fill[red,opacity=0.3] \convexpath{cd,cc}{10pt};
\fill[blue,opacity=0.3] \convexpath{x0,x1,x2,j2,x0}{10pt};
\end{pgfonlayer}
\end{tikzpicture}} \ar[d]^(.6){\mut_2}
\\%$\qquad\xmapsto{\mut_2}\qquad$
\raisebox{-0.6\height}{\begin{tikzpicture}[scale=2]
\node (x0) [align=center] at (0,0) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[->,thick] (b) to (c); \end{tikzpicture}}\\$e$};
\node (x1) [align=center]at (-1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=meet] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[->,thick] (b) to (c); \end{tikzpicture}}\\$c$};
\node (j2) [align=center] at (1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$}; \node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$}; \node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[->,thick] (b) to (c); \end{tikzpicture}}\\$b$};
\node (x2) [align=center] at (-1,2) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=join,text=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[->,thick] (b) to (c); \end{tikzpicture}}\\$d$ };
\node (x3) [align=center] at (0,3) {$a$\\ \scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (a) to (c); \draw[->,thick] (b) to (c); \end{tikzpicture}}};
\draw[-,thick] (x0) to (x1) to (x2) to (x3);
\draw[-,thick] (x0) to (j2) to (x3);
\begin{pgfonlayer}{background}
\fill[blue,opacity=0.3] \convexpath{x1,x2,x3}{10pt};
\fill[red,opacity=0.3] \convexpath{x0,j2}{10pt};
\end{pgfonlayer}
\end{tikzpicture}}
&
\raisebox{-0.6\height}{\begin{tikzpicture}[scale=2]
\node (x0) [align=center] at (0,0) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=join,text=white] at (1,1) {$2$};
\draw[<-,thick] (c) to (a); \draw[<-,thick] (c) to (b); \end{tikzpicture}}\\$d$};
\node (x1) [align=center] at (-1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (c) to (a); \draw[<-,thick] (c) to (b); \end{tikzpicture}}\\$e$};
\node (j2) [align=center] at (1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (c) to (a); \draw[<-,thick] (c) to (b); \end{tikzpicture}}\\$a$};
\node (x2) [align=center] at (0,2) {$b$ \\ \scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (c) to (a); \draw[<-,thick] (c) to (b); \end{tikzpicture}}};
\node (x3) [align=center] at (0,-1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=meet] at (1,1) {$2$};
\draw[<-,thick] (c) to (a); \draw[<-,thick] (c) to (b); \end{tikzpicture}}\\$c$};
\draw[-,thick] (x0) to (x1) to  (x2);
\draw[-,thick] (x0) to (j2) to (x2);
\draw[-,thick] (x3) to (x0);
\begin{pgfonlayer}{background}
\fill[blue,opacity=0.3] \convexpath{x3,x0,j2}{10pt};
\fill[red,opacity=0.3] \convexpath{x1,x2}{10pt};
\end{pgfonlayer}
\end{tikzpicture}} \ar[l]^{\mut_1} \ar@{=}[r]
& \raisebox{-0.6\height}{\begin{tikzpicture}[scale=2]
\node (x0) [align=center] at (0,0) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=join,text=white] at (1,1) {$2$};
\draw[<-,thick] (c) to (a); \draw[<-,thick] (c) to (b); \end{tikzpicture}}\\$d$};
\node (x1) [align=center] at (-1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=meet] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (c) to (a); \draw[<-,thick] (c) to (b); \end{tikzpicture}}\\$e$};
\node (j2) [align=center] at (1,1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=meet] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (c) to (a); \draw[<-,thick] (c) to (b); \end{tikzpicture}}\\$a$};
\node (x2) [align=center] at (0,2) {$b$ \\ \scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=join,text=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=join,text=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=white] at (1,1) {$2$};
\draw[<-,thick] (c) to (a); \draw[<-,thick] (c) to (b); \end{tikzpicture}}};
\node (x3) [align=center] at (0,-1) {\scalebox{.5}{\begin{tikzpicture}[scale=.8]
\node (a) [draw=black,circle,thick,fill=white] at (0,0) {$1$};
\node (b) [draw=black,circle,thick,fill=white] at (2,0) {$3$};
\node (c) [draw=black,circle,thick,fill=meet] at (1,1) {$2$};
\draw[<-,thick] (c) to (a); \draw[<-,thick] (c) to (b); \end{tikzpicture}}\\$c$};
\draw[-,thick] (x0) to (x1) to  (x2);
\draw[-,thick] (x0) to (j2) to (x2);
\draw[-,thick] (x3) to (x0);
\node (cd) at (-.1,-1) {};
\node (cc) at (.1,-1) {};
\begin{pgfonlayer}{background}
\fill[red,opacity=0.3] \convexpath{cd,cc}{10pt};
\fill[blue,opacity=0.3] \convexpath{x0,x1,x2,j2,x0}{10pt};
\end{pgfonlayer}
\end{tikzpicture}}
}}
\caption{Each poset is an independence poset on an orientation of a path of length $3$.  Taken together, these posets represent a sequence of toggles.  Each toggle induces a bijection between $\trip(G)$ and $\trip(\mut_g(G))$, which we keep track of by assigning letters to the elements of the posets.  Toggling each element of the directed graph underlying the independence poset at the top left (in reverse linear extension order) recovers the same indpendence poset on the bottom left, permuting its elements as $(a,b,c,d,e) \xmapsto{\mut_{321}}(e,d,b,c,a)$.  This coincides with rowmotion.}
\label{fig:toggle}
\end{figure}
\end{comment}


%\section{Examples}


\section{Rowmotion on Independence Posets}
\label{sec:rowmotion}

Since both components of a top are independent sets, and each independent set can be completed to a top in two ways, it is natural to define \defn{rowmotion} by sending one completion to the other:
\begin{equation}\row(\al,\br):=\text{the unique } (\al',\br') \in \trip(G) \text{ with } \al=\br'.\label{eq:global_row}\end{equation}

This definition gives a common generalization of the usual notion of rowmotion for distributive lattices and the Kreweras complement for Cambrian lattices.  It turns out that there are two equally natural (but slower) ways to compute rowmotion~\cite{cameron1995orbits,fon1993orbits,striker2012promotion} as a composition of flips (\defn{rowmotion in slow motion}) and as a composition of toggles (\defn{rowmotion by deformotion}).  Here, for $g$ a minimal or maximal element of $G$, the \defn{toggle} $\mut_g$ reverses every edge incident to $g$; this operation induces a bijection between $\trip(G)$ and $\trip(\mut_g(G))$ whose effect essentially interchanges the relative order of a decomposition of $\trip(G)$ into two intervals using the element $g$.  (Note that by composing a sequence of toggles that involves every vertex of $G$, the orientation of every edge of $G$ is reversed twice, giving back $G$ itself.)   

\begin{theorem}
Let $G$ be a directed acyclic graph.  Then rowmotion can be computed in slow motion and by deformotion---that is, $\row = \prod_{g \in \ell} \tog_{g} = \prod_{g \in \ell'} \mut_{g}$ for any linear extension $\ell$ and reverse linear extension $\ell'$ of $G$-order.%
\label{thm:main_thm}
\end{theorem}

\begin{comment}
By~\Cref{thm:trip_ind}, any independent set $\mathcal{I}$ can be completed to a tight orthogonal pair in exactly two ways---the first as $(\mathcal{I},\br)$ and the second as $(\al,\mathcal{I})$.  \defn{Rowmotion} sends the first of these to the second (see \Cref{eq:global_row}).  The purpose of this section is to give two additional ways to compute it: one using flips, and one using toggles.

\begin{definition}
For $G$ an acyclic directed graph, we say that rowmotion on $\trip(G)$ can be computed
\begin{itemize}
\item \defn{in slow motion} if $\row = \prod\limits_{g \in \ell} \tog_{g}$, and
\item \defn{by deformotion} if $\row = \prod\limits_{g \in \ell'} \mut_{g}$,
\end{itemize}
where $\ell$ is any linear extension of $G$-order and  $\ell'$ is any reverse linear extension of $G$-order.
\end{definition}

{
\renewcommand{\thetheorem}{\ref{thm:main_thm}(i)}
\begin{theorem} For $G$ an acyclic directed graph, rowmotion on $\trip(G)$ can be computed in slow motion.
\end{theorem}
\addtocounter{theorem}{-1}
}

\begin{proof}
We follow the same proof as~\cite[Theorem 1.1]{TW}.  Let $g$ be minimal in $G$.

    \emph{Case I: $(\al,\br) \in \trip_g(G)$.} At the first step when calculating $\prod_{h \in \ell} \tog_{h}$, we walk to $(\al',\br')=\tog_g(\al,\br)$.  So $\al'=\al \cup \{g\}$ by~\Cref{lem:down} and $(\al',\br') \in \trip^g(G)$ by~\Cref{lem:decomposition}.  Applying the rest of the flips to $(\al',\br')$ has the effect of applying $\prod_{\substack{h \in \ell\\ h\neq g}} \tog_{h}$ in $\trip(G_g)$.  (Note that the only flips in $\trip(G)$ leaving $\trip^g(G)$ are those of the form $\tog_g$, so they will never be taken.)  By induction, we obtain an element $(\al'',\br'') \in \trip(G_g)$ such that $\br''=\al'\setminus \{g\}$.  Passing back to $\trip^g(G)$ does not change $\br''$, and we conclude the result.

    \emph{Case II:  $(\al,\br) \in \trip^g(G)$ and $g \in \al$.}   At the first step when calculating $\prod_{h \in \ell} \tog_{h}$, we walk to $(\al',\br')=\tog_g(\al,\br)$.  Since $g \in \br'$, $(\al',\br')\in \trip_g(G)$ by~\Cref{lem:decomposition} and $\al' \cup \{g\}=\al$ by~\Cref{lem:down}.  Applying the rest of the flips to $(\al',\br')$ has the effect of applying  $\prod_{\substack{h \in \ell\\ h\neq g}} \tog_{h}$ in $\trip_g(G)$.  (Note that the only flips in $\trip(G)$ leaving $\trip_g(G)$ are those of the form $\tog_g$, so they will never be taken.)  By induction, we obtain an element $(\al'',\br'') \in \trip_g(G)$ such that $\br''= \al' \cup\{g\}$.  But $\al'\cup\{g\}=\al$.


\emph{Case III: $(\al,\br) \in \trip^g(G)$ and $g \not \in \al$.}
By assumption, flipping at $g$ has no effect.  As in Case I, the rest of the flips have the effect of applying $\prod_{\substack{h \in \ell\\ h\neq g}} \tog_{h}$ in $\trip^g(G)$.  By induction, we obtain an element $(\al',\br') \in \trip^g(G)$ such that $\br'=\al$.
\end{proof}

{
\renewcommand{\thetheorem}{\ref{thm:main_thm}(ii)}
\begin{theorem}
For $G$ an acyclic directed graph, rowmotion on $\trip(G)$ can be computed by deformotion.
\label{thm:row_mutation}
\end{theorem}
\addtocounter{theorem}{-1}
}

\begin{proof}
Since every element of $G$ is toggled, every edge is flipped twice, and so $\prod_{g \in \ell'}\mut_g(G)=G$. By definition, $\mut_g$ takes all elements with $g \in \al$ and converts them to elements with $g \in \br$.  Since we are toggling in $\ell'=g_1,\ldots,g_{|G|}$ order, at any step we have moved all $\{g_1,\ldots,g_i\}\cap \al$ from $\al$ to $\br$.  Although this introduces some new elements into $\al$, these only involve $\{g_1,\ldots,g_i\}$ and so are never moved to $\br$ in a subsequent step.  Thus, each element has its \emph{original} set $\al$ converted to its new $\br$, which is the definition of rowmotion given in~\Cref{eq:global_row}.
\end{proof}

\end{comment}

The full version of this extended abstract appeared in~\cite{TW2}; it contains complete proofs, expanded discussion, as well as connections between independence posets and the representation theory of certain finite-dimensional directed algebras.

\nocite{*}
\printbibliography

\end{document}
