Séminaire Lotharingien de Combinatoire, 86B.67 (2022), 12 pp.
Vincent Pilaud
Acyclic Reorientation Lattices and Their Lattice Quotients
Abstract.
We consider acyclic reorientation posets of directed acyclic graphs.
We characterize those which are lattices and provide formulas to compute meets and joins in these lattices.
We next characterize those which are distributive, semidistributive, congruence normal, or congruence uniform lattices.
In the latter case, we introduce a combinatorial gadget to encode the join irreducibles acyclic reorientations and exploit it to describe the canonical representations, the congruence lattices, and the polytopal realizations of the quotients of these acyclic reorientation lattices.
Received: November 25, 2021.
Accepted: March 4, 2022.
Final version: April 1, 2022.
The following versions are available: