Journal of Combinatorics

Volume 10 (2019)

Number 3

Special Issue in Memory of Jeff Remmel, Part 1 of 2

Guest Editor: Nicholas A. Loehr

Independence posets

Pages: 545 – 578



Hugh Thomas (LaCIM, Université du Québec à Montréal, Canada)

Nathan Williams (University of Texas, Dallas, Tx., U.S.A.)


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 flips, and use them to define a new partial order on independent sets of $G$.

Trim lattices generalize distributive lattices by removing the graded hypothesis: a graded trim lattice is a distributive lattice, and every distributive lattice is trim. Our independence posets are a further generalization of distributive lattices, eliminating also the lattice requirement: an independence poset that is a lattice is always a trim lattice, and every trim lattice is the independence poset for a unique (up to isomorphism) acyclic directed graph $G$. We characterize when an independence poset is a lattice with a graph-theoretic condition on $G$.

We generalize the definition of rowmotion from distributive lattices to independence posets, and we show it can be computed in three different ways. We also relate our constructions to torsion classes, semibricks, and $2$-simpleminded collections arising in the representation theory of certain finite-dimensional directed algebras.

H.T. was partially supported by the Canada Research Chairs program and an NSERC Discovery Grant.

W.M. was partially supported by a Simons Foundation Collaboration Grant.

Received 21 April 2018

Published 23 May 2019