Let $G$ be a finite acylic directed graph. The transitive closure of $G$ defines a
posetWhich we call $G$-order
.
An
independent set $\mathcal{I} \subseteq G$ is a set of pairwise non-adjacent vertices of $G$.
\(
\def\D{{\color{#004db2}{\mathcal{D}}}}
\def\U{{\color{#ffcd6f}{\mathcal{U}}}}
\def\IU{{\color{#ffcd6f}{\mathcal{I}}}}
\def\ID{{\color{#004db2}{\mathcal{I}}}}
\)
Definition 1.
A pair $(\D,\U)$ of independent sets of $G$ is called
orthogonal if there is no edge in $G$ from an element of $\D$ to an element of $\U$. An orthogonal pair of independent sets $(\D,\U)$ is called
tight if whenever any element of $\D$ is
increasedremoved and replaced by a larger element with respect to $G$-order
or any element of $\U$ is
decreasedremoved and replaced by a smaller element with respect to $G$-order
, or a new element is added to either $\D$ or $\U$, then the result is no longer an orthogonal pair of independent sets.
Write top for tight orthogonal pair, and $\mathrm{top}(G)$ for the set of all tops of $G$.
Figure 1. Click vertices to add or remove elements from $\D$ or $\U$.The other set automatically completes to the unique top of Theorem 1.
Theorem 1. Let $\mathcal{I}$ be an independent set of a directed acyclic graph $G$. Then there exists a unique $(\ID,\U) \in \mathrm{top}(G)$ and a unique $(\D,\IU)\in \mathrm{top}(G)$.
Definition 2.
sends one completion to the other:
\[\mathrm{row}(\ID,\U):=(\D,\IU).\]
Definition 3.
The
flip of $(\D,\U) \in \mathrm{top}(G)$ at an element $g \in G$ is the tight orthogonal pair $\mathrm{flip}_g(\D,\U)$ defined as follows: if $g \not \in \D$ and $g \not \in \U$, the flip does nothing. Otherwise, preserve all elements of $\D$ that are not less than $g$ and all elements of $\U$ that are not greater than $g$ (and delete all other elements); after switching the set to which $g$ belongs, then
greedily completeIn reverse linear extension order for $\D$ and linear extension order for $\U$.
$\D$ and $\U$ to a tight orthogonal pair.
Figure 2. Click vertices in $\D$ or $\U$ to perform the flip of Definition 3.
Definition/Theorem 2. We
defineThis really does define a poset, and these relations are exactly its covers.
the
independence poset on $\mathrm{top}(G)$ as the reflexive and transitive closure of the relations $(\D,\U) \lessdot (\D',\U')$ if there is some $g \in \U$ such that \[\mathrm{flip}_g(\D,\U)=(\D',\U').\]
Example 1. Let $G$ be the compatibility graph of a poset, so that independent sets of $G$ are antichains. For $(\D,\U) \in \mathrm{top}(G)$, both $\D$ and $\U$ are antichains and $\U$ consists of the minimum elements of $G\setminus \D$. The independence poset on $\mathrm{top}(G)$ recovers the distributive lattice of antichains, and flips are toggles.
Theorem 3. Rowmotion can be computed in
slow motionThat is, $\mathrm{row} = \displaystyle\prod\limits_{g \in \ell} \mathrm{flip}_{g}$, where $\ell$ is a linear extension of $G$-order.
.
Theorem 4. If $\mathrm{top}(G)$ is a lattice, then it is a
trim latticeTrim lattices are extremal left-modular lattices. They are analogues of distributive lattices without the graded hypothesis: a graded trim lattice is a distributive lattice, and every distributive lattice is trim.
.
Theorem 5. If $\mathrm{top}(G)$ is a graded lattice, then it is a distributive lattice.
Example 2.
Click here to build your own examples in CoCalc.