Paper detail

The extended permutohedron on a transitive binary relation

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