Acyclic reorientation lattices and their lattice quotients

Abstract

We prove that the acyclic reorientation poset of a directed acyclic graph D is a lattice if and only if the transitive reduction of any induced subgraph of D is a forest. We then show that the acyclic reorientation lattice is always congruence normal, semidistributive (thus congruence uniform) if and only if D is filled, and distributive if and only if D is a forest. When the acyclic reorientation lattice is semidis- tributive, we introduce the ropes of D that encode the join irreducible acyclic reorientations and exploit this combinatorial model in three direc- tions. First, we describe the canonical join and meet representations of acyclic reorientations in terms of non-crossing rope diagrams. Second, we describe the congruences of the acyclic reorientation lattice in terms of lower ideals of a natural subrope order. Third, we use Minkowski sums of shard polytopes of ropes to construct a quotientope for any congruence of the acyclic reorientation lattice.