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 .
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 or any element of $\U$ is , 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 $\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 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 .

Theorem 4. If $\mathrm{top}(G)$ is a lattice, then it is a .

Theorem 5. If $\mathrm{top}(G)$ is a graded lattice, then it is a distributive lattice.