Fitxers
Tipus de document
ArticleVersió
Versió publicadaData de publicació
Llicència de publicació
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/224188
Acyclic reorientation lattices and their lattice quotients
Títol de la revista
Autors
Director/Tutor
ISSN de la revista
Títol del volum
Recurs relacionat
Resum
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.
Matèries
Matèries (anglès)
Citació
Citació
PILAUD, Vincent. Acyclic reorientation lattices and their lattice quotients. Annals of Combinatorics. 2024. Vol. 28, num. 1035-1092. ISSN 0218-0006. [consulted: 11 of August of 2026]. Available at: https://hdl.handle.net/2445/224188