Independence Posets
Hugh Thomas (UQAM) and Nathan Williams (UTD)
"What if a distributive lattice weren't a lattice?"
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.
Rowmotion Rowmotion was introduced by Duchet; studied for the Boolean lattice and products of chains by Brouwer and Schrijver; and related to matroid theory by Deza and Fukuda. Cameron and Fon-der-Flaass considered rowmotion on the product of two and then three chains. Because the orbit structure of rowmotion on Boolean lattices is so wild, much of the effort in the references above is dedicated to understanding which orbit sizes are realizable. Its study then apparently lay dormant for over a decade until Panyushev resurrected it in the form of a series of conjectures of the orbit structure of rowmotion on the root posets of Lie algebras. The focus then shifted to finding equivariant bijections to natural combinatorial objects, and Stanley completely characterized the orbit structure of rowmotion on the product of two chains combinatorially. Armstrong, Stump, and Thomas then went on to resolve Panyushev's conjectures using noncrossing partitions, while Striker and Williams unified and extended various results by relating rowmotion to jeu-de-taquin and made linguistic contributions to the theory. Interest in rowmotion has blossomed as part of a new research direction which Jim Propp has dubbed "dynamical algebraic combinatorics."
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.


George Markowsky, The factorization and representation of lattices, Transactions of the American Mathematical Society 203 (1975), 185-200.
Jessica Striker and Nathan Williams, Promotion and rowmotion, European Journal of Combinatorics 33 (2012), no. 8, 1919-1942.
Hugh Thomas, An analogue of distributivity for ungraded lattices, Order 23 (2006), no. 2, 249-269.
Hugh Thomas and Nathan Williams, Rowmotion in slow motion, Proceedings of the London Mathematical Society, 119 (2019), 1149-1178.
Hugh Thomas and Nathan Williams, Independence Posets, Journal of Combinatorics 10.3 (2019): 545-578.