Files
Document type
ArticleVersion
Published versionPublication date
Publication license
Please use this identifier to cite or link to this item: https://hdl.handle.net/2445/224188
Acyclic reorientation lattices and their lattice quotients
Journal Title
Authors
Director/Tutor
Journal ISSN
Volume Title
Related resource
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.
Subject (English)
Citation
Citation
PILAUD, Vincent. Acyclic reorientation lattices and their lattice quotients. Annals of Combinatorics. 2024. Vol. 28, num. 1035-1092. ISSN 0218-0006. [consulted: 14 of August of 2026]. Available at: https://hdl.handle.net/2445/224188