The extended permutohedron on a transitive binary relation.

DOI10.1016/J.EJC.2014.06.004zbMATH Open1341.06007arXiv1211.2301OpenAlexW1999949318MaRDI QIDQ404457FDOQ404457

Authors: Luigi Santocanale, Friedrich Wehrung 

Publication date: 4 September 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: For a given transitive binary relation e on a set E, the transitive closures of open (i.e., co-transitive in e) sets, called the regular closed subsets, form an ortholattice Reg(e), the extended permutohedron on e. This construction, which contains the poset Clop(e) of all clopen sets, is a common generalization of known notions such as the generalized permutohedron on a partially ordered set on the one hand, and the bipartition lattice on a set on the other hand. We obtain a precise description of the completely join-irreducible (resp., completely meet-irreducible) elements of Reg(e) and the arrow relations between them. In particular, we prove that (1) Reg(e) is the Dedekind-MacNeille completion of the poset Clop(e); (2) Every open subset of e is a set-theoretic union of completely join-irreducible clopen subsets of e; (3) Clop(e) is a lattice iiff every regular closed subset of e is clopen, iff e contains no "square" configuration, iff Reg(e)=Clop(e); (4) If e is finite, then Reg(e) is pseudocomplemented iff it is semidistributive, iff it is a bounded homomorphic image of a free lattice, iff e is a disjoint sum of antisymmetric transitive relations and two-element full relations. We illustrate the strength of our results by proving that, for n greater than or equal to 3, the congruence lattice of the lattice Bip(n) of all bipartitions of an n-element set is obtained by adding a new top element to a Boolean lattice with n2^{n-1} atoms. We also determine the factors of the minimal subdirect decomposition of Bip(n).

Full work available at URL: https://arxiv.org/abs/1211.2301

Recommendations

• Generalizations of the permutohedron
• Lattices of regular closed subsets of closure spaces
• On permutation lattices
• A generalized permutahedron
• scientific article; zbMATH DE number 908169

zbMATH Keywords

congruence latticesmeet-irreducible elementspartially ordered setsbipartition latticescompletely join-irreducible elementsDedekind-MacNeille completionsextended permutohedraortholatticesregular closed subsetstransitive binary relations

Mathematics Subject Classification ID

Partitions of sets (05A18) Combinatorics of partially ordered sets (06A07) Structure theory of lattices (06B05) Structure theory of algebraic structures (08A05)

Cites Work

• Title not available (Why is that?)
• Lattice Theory: Foundation
• Shellable nonpure complexes and posets. II
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cambrian lattices.
• Clusters, Coxeter-sortable elements and noncrossing partitions
• Title not available (Why is that?)
• Sortable elements and Cambrian lattices.
• Equational Bases and Nonmodular Lattice Varieties
• Realizations of the associahedron and cyclohedron
• Title not available (Why is that?)
• Two families of Newman lattices
• On permutation lattices
• Cayley lattices of finite Coxeter groups are bounded
• On the join dependency relation in multinomial lattices
• Sublattices of associahedra and permutohedra
• Title not available (Why is that?)
• THE LATTICE OF PERMUTATIONS IS BOUNDED
• Enumeration of generalized weak orders
• Les treillis pseudocomplémentés finis. (The finite pseudocomplemented lattices)
• Varieties of lattices
• The order dimension of multinomial lattices
• A generalized permutahedron
• Bipartition orders and statistics on words
• Graphical major indices
• Free Ortholattices
• The poset of bipartitions

Cited In (1)

• Lattices of regular closed subsets of closure spaces

Uses Software

• Prover9
• Mace4
• OEIS

This page was built for publication: The extended permutohedron on a transitive binary relation.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404457)