Carregant...
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, núm. 1035-1092. [consulta: 1 de gener de 2026]. ISSN: 0218-0006. [Disponible a: https://hdl.handle.net/2445/224188]