The extended permutohedron on a transitive binary relation.

DOI10.1016/J.EJC.2014.06.004MaRDI QIDQ404457zbMATH OpenOpenAlexFDO

Authors Luigi Santocanale, Friedrich Wehrung

Publication date 4 September 2014

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

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

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)

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).

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

Cites work

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

Cited in

(1)

• Lattices of regular closed subsets of closure spaces

Describes a project that uses

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)