Luigi Santocanale

Friedrich Wehrung
email: friedrich.wehrung01@unicaen.fr

Lmno

THE EXTENDED PERMUTOHEDRON ON A TRANSITIVE BINARY RELATION

Keywords: 2010 Mathematics Subject Classification. 06A15, 05A18, 06A07, 06B10, 06B25, 20F55 Poset, lattice, semidistributive, bounded, subdirect product, transitive, relation, join-irreducible, join-dependency, permutohedron, bipartition, Cambrian lattice, orthocomplementation, closed, open, clopen, regular closed, square-free, bipartite, clepsydra

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., meet-irreducible) elements of Reg(e) and the arrow relations between them. In particular, we prove that -Reg(e) is the Dedekind-MacNeille completion of the poset Clop(e); -Every open subset of e is a set-theoretical union of completely join-irreducible clopen subsets of e; -Clop(e) is a lattice iff every regular closed subset of e is clopen, iff e contains no "square" configuration, iff Reg(e) = Clop(e); -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 our results by proving that, for n ≥ 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 n • 2 n-1 atoms. We also determine the factors of the minimal subdirect decomposition of Bip(n), and we prove that if n ≥ 3, then none of them embeds into Bip(n) as a sublattice.

Introduction

The lattice P(n) of all permutations of an n-element chain, also known as the permutohedron, even if widely known and studied in combinatorics, is a relatively young object of study from a pure lattice theoretical perspective. Its elements, the permutations of n elements, are endowed with the weak Bruhat order; this order turns out to be a lattice.

There are many possible generalization of this order, arising from the theory of Coxeter groups (Björner [4]), from graph and order theory (Pouzet et al. [START_REF] Pouzet | A generalized permutahedron[END_REF], Hetyei and Krattenthaler [START_REF] Hetyei | The poset of bipartitions[END_REF]), from language theory (Flath [START_REF] Flath | The order dimension of multinomial lattices[END_REF], Bennett and Birkhoff [START_REF] Bennett | Two families of Newman lattices[END_REF]).

In the present paper, we shall focus on one of the most noteworthy features-at least from the lattice-theoretical viewpoint-of one of the equivalent constructions of the permutohedron, namely that it can be realized as the lattice of all clopen (i.e., both closed and open) subsets of a certain strict ordering relation (viewed as a set of ordered pairs), endowed with the operation of transitive closure.

It turns out that most of the theory can be done for the transitive closure operator on the pairs of a given transitive binary relation e. While, unlike the situation for ordinary permutohedra, the poset Clop(e) of all clopen subsets of e may not be a lattice, it is contained in the larger lattice Reg(e) of all so-called regular closed subsets of e, which we shall call the extended permutohedron on e (cf. Section 3). As Reg(e) is endowed with a natural orthocomplementation x → x ⊥ (cf. Definition 3.2), it becomes, in fact, an ortholattice. The natural question, whether Clop(e) is a lattice, finds a natural answer in Theorem 4. [START_REF] Birkhoff | Lattice theory[END_REF], where we prove that this is equivalent to the preordering associated with e be square-free, thus extending (with completely different proofs) known results for both the case of strict orderings (Pouzet et al. [START_REF] Pouzet | A generalized permutahedron[END_REF]) and the case of full relations (Hetyei and Krattenthaler [20]).

However, while most earlier references deal with clopen subsets, our present paper focuses on the extended permutohedron Reg(e). One of our most noteworthy results is the characterization, obtained in Theorem 7.8, of all finite transitive relations e such that Reg(e) is semidistributive. It turns out that this condition is equivalent to Reg(e) being pseudocomplemented, also to Reg(e) being a bounded homomorphic image of a free lattice, and can also be expressed in terms of forbidden sub-configurations of e. This result is achieved via a precise description, obtained in Section 5, of all completely join-irreducible elements of Reg(e). This is a key technical point of the present paper. This description is further extended to a description of the join-dependency relation (cf. Section 6), thus essentially completing the list of tools for proving one direction of Theorem 7.8. The other directions are achieved via ad hoc constructions, such as the one of Proposition 3.5.

Another noteworthy consequence of our description of completely join-irreducible elements of the lattice Reg(e) is the spatiality of that lattice: every element is a join of completely join-irreducible elements. . . and even more can be said (cf. Lemma 5.5 and Theorem 5.8). As a consequence, Reg(e) is the Dedekind-MacNeille completion of Clop(e) (cf. Corollary 5.6).

We proved in our earlier paper Santocanale and Wehrung [START_REF] Santocanale | Sublattices of associahedra and permutohedra[END_REF] that the factors of the minimal subdirect decomposition of the permutohedron P(n) are exactly Reading's Cambrian lattices of type A, denoted in [START_REF] Santocanale | Sublattices of associahedra and permutohedra[END_REF] by A U (n). As a further application of our methods, we determine here the minimal subdirect decomposition of the lattice Bip(n) of all bipartitions (i.e., those transitive binary relations with transitive complement) of an n-element set, thus solving the "equation" The fractional "equation" (1.1) is a very informal notation suggesting that x stands to bipartition lattices the same way Cambrian lattices of type A stand to permutohedra. The lattices x solving the "equation" (1.1), denoted here in the form S(n, k) (cf. Remark 9.8), offer features quite different from those of the Cambrian lattices; in particular, their cardinality does not depend on n alone (cf. Section 11) and they are never sublattices of the corresponding bipartition lattice Bip(n) for n ≥ 3 (cf. Section 10). In fact, if n ≥ 3, then every nonconstant lattice endomorphism of Bip(n) is an automorphism, and the automorphism group of Bip(n) is isomorphic to S n × S 2 (where S n denotes the symmetric group on n elements), see Theorem 10.1.

We also use our tools to determine the congruence lattice of every finite bipartition lattice (cf. Corollary 8.8), which, for a base set with at least three elements, turns out to be Boolean with a top element added.

Basic concepts and notation

We refer the reader to Grätzer [START_REF] Grätzer | Lattice Theory: Foundation[END_REF] for basic facts, notation, and terminology about lattice theory.

We shall denote by 0 (resp., 1) the least (resp., largest) element of a partially ordered set (from now on poset ) (P, ≤), if they exist. A lower cover of an element p ∈ P is an element x ∈ P such that x < p and there is no y such that x < y < p. If p has a unique lower cover, then we shall denote this element by p * . Upper covers, and the notation p * , are defined dually.

A nonzero element p in a lattice L is join-irreducible if p = x ∨ y implies that p ∈ {x, y}, for all x, y ∈ L. We say that p is completely join-irreducible if it has a unique lower cover p * , and every x < p satisfies x ≤ p * . Completely meet-irreducible elements are defined dually. We denote by Ji L (resp., Mi L) the set of all join-irreducible (resp., meet-irreducible) elements of L.

Every completely join-irreducible element is join-irreducible, and in a finite lattice, the two concepts are equivalent. A lattice L is spatial if every element of L is a (possibly infinite) join of completely join-irreducible elements. Equivalently, for all a, b ∈ L, a b implies that there exists a completely join-irreducible element p of L such that p ≤ a and p b.

For a completely join-irreducible element p and a completely meet-irreducible element u of L, let p ր u hold if p ≤ u * and p u. Symmetrically, let u ց p hold if p * ≤ u and p u. The join-dependency relation D is defined on completely join-irreducible elements by p D q ⇐⇒ def. p = q and (∃x)(p ≤ q ∨ x and p q * ∨ x) .

It is well-known (cf. Freese, Ježek, and Nation [START_REF] Freese | Free Lattices[END_REF]Lemma 11.10]) that the joindependency relation D on a finite lattice L can be conveniently expressed in terms of the arrow relations ր and ց between Ji L and Mi L.

Lemma 2.1. Let p, q be distinct join-irreducible elements in a finite lattice L. Then p D L q iff there exists u ∈ Mi L such that p ր u ց q.

We shall denote by D n (resp., D * ) the nth relational power (resp., the reflexive and transitive closure) of the relation D, so, for example, p D 2 q iff there exists r ∈ Ji L such that p D r and r D q.

It is well-known that the congruence lattice Con L of a finite lattice L can be conveniently described via the relation D on L, as follows (cf. Freese, Ježek, and Nation [START_REF] Freese | Free Lattices[END_REF]§ II.3]). Denote by con(p) the least congruence of L containing (p * , p) as an element, for each p ∈ Ji L. Then con(p) ⊆ con(q) iff p D * q, for all p, q ∈ Ji L. Furthermore, Con L is a distributive lattice and its join-irreducible elements are exactly the con(p), for p ∈ Ji L. A subset S ⊆ Ji L is a D-upper subset if p ∈ S and p D q implies that q ∈ S, for all p, q ∈ Ji L.

Set S ↓ x = {s ∈ S | s ≤ x}, for each x ∈ L. Lemma 2.2. The binary relation θ S = {(x, y) ∈ L × L | S ↓ x = S ↓
y} is a congruence of L, for every finite lattice L and every D-upper subset S of Ji L, and the assignment x → x/θ S defines an isomorphism from the (∨, 0)-subsemilattice S ∨ of L generated by S onto the quotient lattice L/θ S . Furthermore, the assignment S → θ S defines a dual isomorphism from the lattice of all D-upper subsets of Ji L onto Con L. The inverse of that isomorphism is given by

θ → {p ∈ Ji L | (p, p * ) / ∈ θ} , for each θ ∈ Con L .
For each p ∈ Ji L, denote by Ψ(p) the largest congruence θ of L such that p ≡ p * (mod θ). Then Ψ(p) = θ Sp where we set S p = {q ∈ Ji L | p D * q}. Equivalently, Ψ(p) is generated by all pairs (q, q * ) such that p D * q does not hold. Say that p ∈ Ji L is D * -minimal if p D * q implies q D * p, for each q ∈ Ji L. The set ∆(L) of all D * -minimal join-irreducible elements of L defines, via Ψ, a subdirect product decomposition of L,

L ֒→ p∈∆(L) L/Ψ(p) , x → x/Ψ(p) | p ∈ ∆(L) , (2.1)
that we shall call the minimal subdirect product decomposition of L.

A lattice L is join-semidistributive if x∨z = y∨z implies that x∨z = (x∧y)∨z, for all x, y, z ∈ L. Meet-semidistributivity is defined dually. A lattice is semidistributive if it is both join-and meet-semidistributive.

A lattice L is a bounded homomorphic image of a free lattice if there are a free lattice F and a surjective lattice homomorphism f : F ։ L such that f -1 {x} has both a least and a largest element, for each x ∈ L. These lattices, introduced by McKenzie [START_REF] Mckenzie | Equational bases and non-modular lattice varieties[END_REF], form a quite important class within the theory of lattice varieties, and are often called "bounded lattices" (not to be confused with lattices with both a least and a largest element). A finite lattice is bounded iff the join-dependency relations on L and on its dual lattice are both cycle-free (cf. Freese, Ježek, and Nation [START_REF] Freese | Free Lattices[END_REF]Corollary 2.39]). Every bounded lattice is semidistributive (cf. Freese, Ježek, and Nation [START_REF] Freese | Free Lattices[END_REF]Theorem 2.20]), but the converse fails, even for finite lattices (cf. Freese, Ježek, and Nation [START_REF] Freese | Free Lattices[END_REF]Figure 5.5]).

An orthocomplementation on a poset P with least and largest element is a map x → x ⊥ of P to itself such that (O1) x ≤ y implies that y ⊥ ≤ x ⊥ , (O2) x ⊥⊥ = x, (O3) x ∧ x ⊥ = 0 (in view of (O1) and (O2), this is equivalent to x ∨ x ⊥ = 1), for all x, y ∈ P . Elements x, y ∈ P are orthogonal if x ≤ y ⊥ , equivalently y ≤ x ⊥ .

An orthocomplemented poset is a poset with an orthocomplementation. Although an orthocomplemented poset P always has a least element 0, a largest element 1, and the elements x ∧ x ⊥ and x ∨ x ⊥ exist for all x ∈ P (with respective values 0 and 1), the poset P may not be a lattice.

Of course, any orthocomplementation of P is a dual automorphism of (P, ≤). In particular, if P is a lattice, then de Morgan's rules

(x ∨ y) ⊥ = x ⊥ ∧ y ⊥ , (x ∧ y) ⊥ = x ⊥ ∨ y ⊥
hold for all x, y ∈ P . An ortholattice is a lattice endowed with an orthocomplementation.

A lattice L with a least element 0 is pseudocomplemented if {y ∈ L | x ∧ y = 0} has a greatest element, for each x ∈ P .

We shall denote by Pow X the powerset of a set X, and we shall set Pow * X = (Pow X) \ {∅, X}. We shall also set [n] = {1, 2, . . . , n}, for every positive integer n. (either 1 x ⊳ e y or x = y) ,

Regular closed subsets of a transitive relation

x ≡ e y ⇐⇒ def.

(x e y and y e x) , for all x, y ∈ E. We say that e is a strict ordering if it is irreflexive (i.e., (x, x) / ∈ e for every x) and transitive. In the general case, we set Denote by cl(a) the transitive closure of any relation a. We say that a is closed if it is transitive. We say that a is bipartite if there are no x, y, z such that (x, y) ∈ a and (y, z) ∈ a. It is trivial that every bipartite relation is closed.

Let e be a transitive relation on a set E. A subset a ⊆ e is open (relatively to e) if e \ a is closed; equivalently,

x ⊳ e y ⊳ e z and (x, z) ∈ a ⇒ either (x, y) ∈ a or (y, z) ∈ a , for all x, y, z ∈ E .

The largest open subset of a ⊆ e, called the interior of a and denoted by int(a), is exactly the set of all pairs (x, y) ∈ e such that for every subdivision x = z 0 ⊳ e z 1 ⊳ e • • • ⊳ e z n = y, with n > 0, there exists i < n such that (z i , z i+1 ) ∈ a.

A The terminology "open", "closed", "clopen", widely spread among lattice theorists, originates from topology, and the corresponding concepts bear some similarity with the topological ones. For example, any union of open sets is open, and any intersection of closed sets is closed. Nevertheless, an important difference between the present context and the topological one is that the union of finitely many 1 Here and elsewhere in the paper, "either A or B" will stand for inclusive disjunction of A and B, see for example Barwise and Etchenmendy [1,page 75].

closed sets may not be closed. This means that the closure operator cl (see, for example, Birkhoff [3, § V.1]) is not necessarily topological, that is, one may have cl(x ∪ y) = cl(x) ∪ cl(y) with x, y ⊆ e.

The following lemma gathers a few basic facts about the concepts defined above. Proof. (i). Observe that int ≤ id ≤ cl, that is, int(x) ⊆ x ⊆ cl(x) for every x ⊆ e.

Since the operators cl and int are both order-preserving and idempotent, we get

(cl • int) 2 = cl • int • cl • int ≤ cl • id • cl • int = cl • int , (cl • int) 2 = cl • int • cl • int ≥ cl • int • id • int = cl • int , hence (cl • int) 2 = cl • int. Likewise, (int • cl) 2 = int • cl. (ii). If x = cl(u) with u open, then, by (i), x = (cl • int)(u) = (cl • int) 2 (u) = (cl • int)(x) is regular closed. Conversely, if x is regular closed, then x = cl(u) for the open set u = int(x).
(iii). The open set u = i∈I int(a i ) is contained in a = i∈I a i . Furthermore, a i = cl(int(a i )) ⊆ cl(u) for each i, thus a ⊆ cl(u), whence cl(a) = cl(u) is regular closed. It follows easily that cl(a) is the least upper bound of {a i | i ∈ I} in Reg(e).

Setting b = i∈I a i , it follows from (i) that cl int(b) is regular closed. It follows easily that this set is the greatest lower bound of {a i | i ∈ I} in Reg(e).

The complement of a regular closed set may not be closed. Nevertheless, we shall now see that there is an obvious "complementation-like" map from the regular closed sets to the regular closed sets. Definition 3.2. We define the orthogonal of x as x ⊥ = cl(e \ x), for any x ⊆ e. Lemma 3.3.

(i) x ⊥ is regular closed, for any closed x ⊆ e.

(ii) The assignment ⊥ : x → x ⊥ defines an orthocomplementation of Reg(e).

Proof. (i) follows immediately from Lemma 3.1(ii).

(ii) follows from the equations int(x) = e \ cl(e \ x) = e \ x ⊥ , together with the idempotence of the operator cl • int (cf. Lemma 3.1(i)). We shall call Clop(e) the permutohedron on e and Reg(e) the extended permutohedron on e. For example, if e is the strict ordering associated to a poset (E, ≤), then Clop(e) is the poset denoted by N(E) in Pouzet et al. [START_REF] Pouzet | A generalized permutahedron[END_REF]. On the other hand, if e = [n] × [n] for a positive integer n, then Clop(e) is the poset of all bipartitions of [n] introduced in Foata and Zeilberger [START_REF] Foata | Graphical major indices[END_REF] and Han [START_REF] Han | Ordres bipartitionnaires et statistiques sur les mots[END_REF], see also Hetyei and Krattenthaler [START_REF] Hetyei | The poset of bipartitions[END_REF] where this poset is denoted by Bip(n).

While the lattice Reg(e) is always orthocomplemented (cf. Lemma 3.3), the following result shows that Reg(e) is not always pseudocomplemented. Proposition 3.5. Let e be a transitive relation on a (possibly infinite) set E with pairwise distinct elements a 0 , a 1 , b ∈ E such that a 0 ≡ e a 1 and either b ⊳ e a 0 or a 0 ⊳ e b. Then there are clopen subsets a 0 , a 1 , c of e such that a 0 ∧ c = a 1 ∧ c = ∅ while ∅ = c ⊆ a 0 ∨ a 1 . In particular, the lattice Reg(e) is neither meet-semidistributive, nor pseudocomplemented.

Proof. We show the proof in the case where a 0 ⊳ e b. By applying the result to e op = {(x, y) | (y, x) ∈ e}, the result for the case b ⊳ e a 0 will follow. We set

I = [a 0 , b] e = [a 1 , b] e and a i = {a i } × (I \ {a i }) (for each i ∈ {0, 1}) , c = {a 0 , a 1 } × (I \ {a 0 , a 1 }) .
It is straightforward to verify that a 0 , a 1 , c are all clopen subsets of e. Furthermore, (a 0 , b) ∈ c thus c = ∅, and c ⊆ a 0 ∪ a 1 ⊆ a 0 ∨ a 1 . Now let (a 0 , x) be an element of a 0 ∩ c = {a 0 } × (I \ {a 0 , a 1 }). Observing that a 0 ⊳ e a 1 ⊳ e x while (a 0 , a 1 ) / ∈ a 0 ∩ c and (a 1 , x) / ∈ a 0 ∩ c, we obtain that (a 0 , x) / ∈ int a 0 ∩ c ; whence Since e is square-free, either s l+1 e y or y ⊳ e s l+1 . In the first case, it follows from the definition of l that l = n -1, thus, using (4.2) together with (y, z) ∈ a, we get s n-1 = s l ⊳ a y ⊳ a z = s n , whence (s n-1 , s n ) ∈ a, which contradicts (4.1). Hence y ⊳ e s l+1 . From y ⊳ e s l+1 ⊳ e s l+2 ⊳ e • • • ⊳ e s n = z, (y, z) ∈ int(a), and (4.1) it follows that (y, s l+1 ) ∈ a, thus, by (4.2), (s l , s l+1 ) ∈ a, in contradiction with (4.1).

a 0 ∧ c = ∅. Likewise, a 1 ∧ c = ∅.
In the particular case of strict orderings, most of the following result is contained (with a completely different argument) in Pouzet et al. [START_REF] Pouzet | A generalized permutahedron[END_REF]Lemma 12]. No finiteness assumption on e is needed.

Theorem 4.3. The following are equivalent, for any transitive relation e:

(i) e is square-free;

(ii) Clop(e) = Reg(e); (iii) Clop(e) is a lattice;

(iv) Clop(e) has the interpolation property, that is, for all x 0 , x 1 , y 0 , y 1 ∈ Clop(e) such that x i ⊆ y j for all i, j < 2, there exists z ∈ Clop(e) such that x i ⊆ z and z ⊆ y i for all i < 2.

Proof. (i)⇒(ii) follows immediately from Lemma 4.2.

(ii)⇒(iii) and (iii)⇒(iv) are both trivial. (iv)⇒(i). We prove that if e is not square-free, then Clop(e) does not satisfy the interpolation property. By assumption, there are (a, b) ∈ e and u, v ∈ [a, b] e such that u e v and v e u. It is easy to verify that the subsets

x 0 = {a} × ]a, u] e , x 1 = [u, b[ e × {b} ,
y 0 = ({a} × ]a, b] e ) ∪ x 1 , y 1 = ([a, b[ e × {b}) ∪ x 0
are all clopen, and that x i ⊆ y j for all i, j < 2. Suppose that there exists z ∈ Clop(e) such that x i ⊆ z ⊆ y i for each i <

a 0 = {(0, a)} , a 1 = {(a, 1)} , b 0 = {(0, b)} , b 1 = {(b, 1)} , c 00 = {(0, a), (0, b), (0, 1)} , c 01 = {(0, a), (b, 1), (0, 1)} , c 10 = {(a, 1), (0, b), (0, 1)} , c 11 = {(a, 1), (b, 1), (0, 1)} . a 0 a 1 b 0 c 00 c 01 c 10 c 11 u u ⊥ a ⊥ 0 a ⊥ 1 b ⊥ 0 b ⊥ 1 c ⊥ 00 c ⊥ 01 c ⊥ 10 c ⊥ 11 b 1 0 1 a b R(B 2 ) B 2 Figure 4.1. The lattice R(B 2 )
The two elements of R(B 2 ) \ P(B 2 ) are u = {(0, a), (a, 1), (0, 1)} together with its orthogonal, u ⊥ = {(0, b), (b, 1), (0, 1)}. Those elements are marked by doubled circles on the right hand side diagram of Figure 4.1.

Example 4.6. It follows from Proposition 3.5 that the lattice Bip(3) of all bipartitions of [START_REF] Birkhoff | Lattice theory[END_REF] is not pseudocomplemented. We can say more: Bip(3) contains a copy of the five element lattice M 3 of length two, namely {∅, a, b, c, e}, where

a = {(1, 2), (3, 1), (3, 2)} , b = {(2, 1), (2, 3), (3, 1)} , c = {(1, 2), (1, 3), (2, 3)} , e = [3] × [3] .
It is also observed in Hetyei and Krattenthaler [START_REF] Hetyei | The poset of bipartitions[END_REF]Example 7.7] that Bip(3) contains a copy of the five element nonmodular lattice N 5 ; hence it is not modular.

Completely join-irreducible clopen sets

Throughout this section we shall fix a transitive relation e on a (possibly infinite) set E.

∈ U } , if a = b , e ∩ ({a} ∪ U c ) × ({a} ∪ U ) , if a = b , for each (a, b, U ) ∈ F(e). Equivalently, a, b; U = e ∩ ({a} ∪ U c ) × ({b} ∪ U ) . Observe that a, b; U is always a subset of e. Observe that a, b; U is bipartite iff a = b. If a = b, we shall say that a, b; U is a clepsydra. 2
The proof of the following lemma is a straightforward exercise. 2 Although the word "clepsydra" has Greek origins and denotes a water clock, we borrow the meaning from the Italian word "clessidra", standing for "hourglass", the latter describing the pattern of the associated transitive relation: the elements of U c below; a in the middle; the elements of U above.

p * = p \ ([a] e × [b] e ) , if a = b , p \ {(a, a)} , if a = b (5.1)
is clopen, and every open proper subset of p is contained in p * .

Note. The notation p * will be validated shortly, in Corollary 5.4, by proving that p * is, indeed, the unique lower cover of p in the lattice Reg(e). From now on suppose that a = b. It is trivial that p is closed (although it is no longer bipartite). The proof that p is open is similar to the one for the case where a = b.

Let x ⊳ e y ⊳ e z with (x, y) ∈ p * and (y, z) ∈ p * . From p * ⊆ p it follows that y ∈ {a} ∪ U c and y ∈ {a} ∪ U , thus y = a, and thus (as (x, a) = (x, y) ∈ p * ) x = a, and so (x, z) = (a, a). This proves that p * is closed.

Let x ⊳ e y ⊳ e z with (x, z) ∈ p * , and suppose by way of contradiction that (x, y) / ∈ p * and (y, z) / ∈ p * . As p is open, either (x, y) ∈ p or (y, z) ∈ p, thus either (x, y) = (a, a) or (y, z) = (a, a). In the first case (y, z) = (x, z) ∈ p * , and in the second case (x, y) = (x, z) ∈ p * , a contradiction in both cases. This proves that p * is open.

Finally let u ⊆ p be open not contained in p * , so (a, a) ∈ u. Let (x, y) ∈ p, we must prove that (x, y) ∈ u. If (x, y) = (a, a) this is trivial. Suppose that x = a and y ∈ U \ {a}. Then a ⊳ e y ⊳ e a, but (y, a) / ∈ u (because (y, a) / ∈ p), (a, a) ∈ u, and u is open, thus (x, y) = (a, y) ∈ u, as desired. This completes the case x = a. The case where y = a and x ∈ U c \ {a} is dealt with similarly. Now suppose that x ∈ U c \ {a} and y ∈ U \ {a}. As above, we prove that (y, a) / ∈ u and thus (a, y) ∈ u. Now (a, x) / ∈ u (because (a, x) / ∈ p), thus, as a ⊳ e x ⊳ e y, (a, y) ∈ u, and u is open, we get (x, y) ∈ u, as desired. Suppose first that a = b and set

U = {x ∈ [a, b] e | x = a and (a, x) ∈ u} .
It is trivial that a / ∈ U and b ∈ U . Let (x, y) ∈ a, b; U (so x / ∈ U and y ∈ U ), we must prove that (x, y) ∈ u. If x = a then this is obvious (because y ∈ U ). Now suppose that x = a. In that case, from x / ∈ U it follows that (a, x) / ∈ u. As (a, y) ∈ u (because y ∈ U ), a ⊳ e x ⊳ e y, and u is open, we get (x, y) ∈ u, as desired.

From now on suppose that a = b. We set

U = {x ∈ [a] e | (a, x) ∈ u} .
Observe that a ∈ U , so {a} ∪ U = U . Let (x, y) ∈ a, a; U , we must prove that (x, y) ∈ u. If x = a, then, as y ∈ U , we get (x, y) = (a, y) ∈ u. Hence we may suppose from now on that x = a; it follows that x ∈ U c (as (x, y) ∈ a, a; U ) and therefore (a, x) / ∈ u. As y ∈ U , we get (a, y) ∈ u. As a ⊳ e x ⊳ e y and u is open, it follows again that (x, y) ∈ u, as desired. Suppose next that a is a completely join-irreducible element of Reg(e); since Reg(e) is join-generated by Clop(e), we can write a as join of clopen sets, a = i∈I c i . As a is completely join-irreducible, it follows that a = c i for some i ∈ I, thus a is clopen. Notice that Corollary 5.7 can also be derived from Corollary 5.6: if the inclusion of Clop(e) into Reg(e) is, up to isomorphism, the Dedekind-MacNeille completion of Clop(e), then this inclusion preserves existing joins and meets. Thus, for example, suppose that w = Clop(e) i∈I a i exists; then w = Reg(e) i∈I a i , and we get

w = Reg(e) i∈I a i = cl int i∈I a i ⊇ int i∈I a i .
As w ⊆ int i∈I a i follows from the openness of w together with w ⊆ a i for each i ∈ I, we get w = int i∈I a i , showing that int i∈I a i is closed. In particular, if a is completely join-irreducible, then it must be one of the a i , b i ; U i . Conversely, by Corollary 5.4, every element of the form a, b; U is completely joinirreducible in Reg(e).

The arrow relations between clopen sets

Lemma 2.1 makes it possible to express the join-dependency relation on a finite lattice in terms of the arrow relations ր and ց. Throughout this section, let e be a transitive relation on a set E. We shall not necessarily assume finiteness of e, except in Corollary 6.4 where we are dealing with the relation D (for Lemma 2.1 assumes finiteness). By using the dual automorphism x → x ⊥ (cf. Lemma 3.3), x ⊥ ց y iff x ր y ⊥ , for all x, y ∈ Reg(e); hence statements involving ց can always be expressed in terms of ր. Furthermore, the completely meet-irreducible elements of Reg(e) are exactly the elements of the form p ⊥ , where p is a completely join-irreducible element of Reg(e). As every such p is clopen (cf. Theorem 5.8), we get p ⊥ = e \ p. Therefore, we obtain the following lemma. Lemma 6.1. p ր q ⊥ iff p ∩ q = ∅ and p ∩ q * = ∅, for all join-irreducible clopen sets p and q. Furthermore, if q = c, d; V , where (c, d, V ) ∈ F(e), then p ր q ⊥ implies that

∅ = p ∩ q ⊆ [c] e × [d] e .
Proof. Only the second part of Lemma 6.1 requires a proof. From p ր q ⊥ and the first part of Lemma 6.1 it follows that p ∩ q = ∅ and further, using equation (5.1),

p ⊆ (q * ) c ⊆ q \ ([c] e × [d] e ) c = q c ∪ ([c] e × [d] e ) , so p ∩ q ⊆ [c] e × [d] e .
From Lemma 6.2 to Lemma 6.6, we shall fix (a, b, U ), (c, d, V ) ∈ F(e). Further, we shall set p = a, b; U , q = c, d; V , U c = [a, b] e \ U , and

V c = [c, d] e \ V . Lemma 6.2. p ր q ⊥ implies that [c, d] e ⊆ [a, b] e .
Proof. By Lemma 6.1 we can pick (x, y) ∈ p ∩ q ⊆ [c] e × [d] e , thus x ≡ e c and y ≡ e d; furthermore, as (x, y) ∈ p, we get a e x ⊳ e y e b. The desired conclusion follows from the transitivity of e .

Lemma 6.3. Suppose that c = d. Then p ր q ⊥ iff a = b = c = d, U ∩ V ⊆ {a}, and U c ∩ V c ⊆ {a}.
Proof. Suppose first that p ր q ⊥ . From q * = q \ {(c, c)} (cf. (5.1)) it follows that

p ∩ q = {(c, c)} , ( 6
∪ U c ) ∩ ({a} ∪ U ) = {a}, so a = c. Now let x ∈ U c ∩ V c .
Then (x, a) belongs to p ∩ q, thus, by (6.1), x = a. The proof of the containment

U ∩ V ⊆ {a} is similar. Conversely, suppose that a = b = c = d, U ∩ V ⊆ {a}, and U c ∩ V c ⊆ {a}. Then any (x, y) ∈ p ∩ q satisfies x ∈ U c ∩ V c , thus x = a.
Likewise, y = a, so p ∩ q = {(a, a)}. By Lemma 6.1, it follows that p ր q ⊥ . As a noteworthy consequence, we obtain that if e is finite and q is a clepsydra, then there is no p such that p D q. Corollary 6.4. Let e be finite. If c = d, then the relation p D q does not hold.

Proof. Suppose that p D q, so there exists a join-irreducible element r such that p ր r ⊥ and r ր q ⊥ . By Lemma 6.3, a = b = c = d and there exists W ⊆ [a] e such that r = a, a; W and the sets U ∩ W , U c ∩ W c , V ∩ W , and V c ∩ W c are all contained in {a}. Since all these subsets are contained in [a] e , this means that each pair

(U \ {a}, W \ {a}) and (V \ {a}, W \ {a}) is complementary within [a] e \ {a}, hence U \ {a} = V \ {a}, equivalently U ∪ {a} = V ∪ {a}. Therefore, p = q, contradicting the definition of the relation D. Lemma 6.5. Suppose that a = b and c = d. Then p ր q ⊥ iff a ≡ e c ≡ e d, ({a} ∪ U ) ∩ V = ∅, and ({a} ∪ U c ) ∩ V c = ∅.
Proof. Suppose first that p ր q ⊥ . It follows from Lemma 6.2 that a ≡ e c ≡ e d.

Any element (u, v) ∈ p ∩ q satisfies that u ∈ ({a} ∪ U c ) ∩ V c and v ∈ ({a} ∪ U ) ∩ V . Conversely, if a ≡ e c ≡ e d, u ∈ ({a} ∪ U c ) ∩ V c , and v ∈ ({a} ∪ U ) ∩ V , then (u, v) ∈ p ∩ q. From c = d, c ≡ e d, and q ⊆ [c, d] e × [c, d] e it follows that q * = q \ ([c] e × [d] e ) = ∅; whence p ∩ q * = ∅. Lemma 6.6. Suppose that a = b and c = d. Then p ր q ⊥ iff [c, d] e ⊆ [a, b] e and ∅ = e ∩ (U c ∩ V c ) × (U ∩ V ) ⊆ [c] e × [d] e .
Proof. Suppose first that p ր q ⊥ . It follows from Lemma 6.2 that [c, d] e ⊆ [a, b] e . Any element (u, v) ∈ p ∩ q belongs to e ∩ (U c ∩ V c ) × (U ∩ V ) , thus this set is nonempty. Moreover, any element (u, v) of this set belongs to q \ q * , thus u ≡ e c and v ≡ e d. Conversely, suppose that

[c, d] e ⊆ [a, b] e and ∅ = e ∩ (U c ∩ V c ) × (U ∩ V ) ⊆ [c] e × [d] e . Observing that p ∩ q = e ∩ (U c ∩ V c ) × (U ∩ V ) ,
it follows that p ∩ q is both nonempty and contained in [c] e × [d] e ; the latter condition implies that p ∩ q * = ∅. We get therefore the relation p ր q ⊥ . Corollary 6.7. Suppose that e is antisymmetric, a = b, and c = d. Then p ր q ⊥ iff (c, d) ∈ p and V = (]c, d] e \ U ) ∪ {d}.

Bounded lattices of regular closed sets

Let e be a transitive relation on a (possibly infinite) set E. Suppose, until the statement of Proposition 7.2, that e is antisymmetric (i.e., the preordering e is an ordering), then some information can be added to the results of Section 6. First of all, the clepsydras (cf. Definition This yields, in the finite case, a characterization of the join-dependency relation on the join-irreducible clopen sets. Proposition 7.2. Suppose that E is finite, e is antisymmetric, and let (a 0 , b 0 , U 0 ), (a 1 , b 1 , U 1 ) ∈ F(e) with a 0 = b 0 and a

1 = b 1 . Set p i = a i , b i ; U i for i < 2. Then p 0 D p 1 in the lattice Reg(e) iff [a 1 , b 1 ] e [a 0 , b 0 ] e and U 1 = U 0 ↾ a1,b1 .
Proof. Suppose first that p 0 D p 1 . By Theorem 5.8, Lemma 2.1, and the observations at the beginning of Section 6, there exists (c, d, V ) ∈ F(e) such that, setting q = c, d; V , the relations p 0 ր q ⊥ and q ր p ⊥ 1 both hold. It follows from Corollary 6.

4 that c = d. By Lemma 7.1, [a 1 , b 1 ] e ⊆ [c, d] e ⊆ [a 0 , b 0 ] e and, setting U 0 = (E \ U 0 )↾ a0,b0 and V = (E \ V )↾ c,d , V = U 0 ↾ c,d and U 1 = V ↾ a1,b1 ; clearly V = U 0 ↾ c,d , whence U 1 = U 0 ↾ a1,b1 . Since p 0 = p 1 , it follows that [a 1 , b 1 ] e [a 0 , b 0 ] e . Conversely, suppose that [a 1 , b 1 ] e [a 0 , b 0 ] e and U 1 = U 0 ↾ a1,b1 . In particular, p 0 = p 1 . Set U c 0 = [a 0 , b 0 ] e \ U 0 .
We shall separate cases, according to whether or not a 1 , b 1 belong to U 0 . In each of those cases, we shall define a certain join-irreducible element q = c, d; V of Reg(e), with a 0 e c ⊳ e d e a 1 and V = U c 0 ↾ c,d , hence only c and d will need to be specified. Each of the desired arrow relations will be inferred with the help of Corollary 6.7.

Case 1. a 1 ∈ {a 0 } ∪ U c 0 and b 1 ∈ {b 0 } ∪ U 0 . We set c = a 1 and d = b 1 . Then p 0 ր q ⊥ (because (a 1 , b 1 ) ∈ p 0 ) and q ր p ⊥ 1 (because (a 1 , b 1 ) ∈ q). Case 2. a 1 ∈ {a 0 } ∪ U 0 and b 1 ∈ {b 0 } ∪ U 0 . We set c = a 0 and d = b 1 . Then p 0 ր q ⊥ (because (a 0 , b 1 ) ∈ p 0 ) and

q ր p ⊥ 1 (because (a 1 , b 1 ) ∈ q). Case 3. a 1 ∈ {a 0 } ∪ U c 0 and b 1 ∈ {b 0 } ∪ U c 0 . We set c = a 1 and d = b 0 . Then p 0 ր q ⊥ (because (a 1 , b 0 ) ∈ p 0 ) and q ր p ⊥ 1 (because (a 1 , b 1 ) ∈ q). Case 4. a 1 ∈ {a 0 } ∪ U 0 and b 1 ∈ {b 0 } ∪ U c 0 .
We set c = a 0 and d = b 0 . Then p 0 ր q ⊥ (because (a 0 , b 0 ) ∈ p 0 ) and q ր p ⊥ 1 (because (a 1 , b 1 ) ∈ q). In each of those cases, p 0 ր q ⊥ and q ր p ⊥ 1 , hence, as p 0 = p 1 and by Lemma 2.1, p 0 D p 1 .

By using the standard description of the congruence lattice of a finite lattice via the join-dependency relation (cf. Freese, Ježek, and Nation [16, § II.3]), Proposition 7.2 makes it possible to give a complete description of the congruence lattice of Reg(e) in case e is antisymmetric. Congruence lattices of permutohedra were originally described in Duquenne and Cherfouh [11, § 4]. An implicit description of congruences of permutohedra via the join-dependency relation appears in Santocanale [START_REF] Santocanale | On the join dependency relation in multinomial lattices[END_REF]; in that paper, similar results were established for multinomial lattices.

By Lemma 6.5 together with the antisymmetry of e, if p ր q ⊥ and p is a clepsydra, then so is q. Hence, by Corollary 6.4, p D q implies (in the finite, antisymmetric case) that neither p nor q is a clepsydra. By Proposition 7.2, we thus obtain the following result. The lattice L 9 is not orthocomplemented, but its parallel sum with its dual lattice L 10 , denoted there by L 9 L 10 , is orthocomplemented. As L 9 , the parallel sum is bounded and has non-transitive relation D.

In the non-bounded case, the reflexive closure of the relation D on Reg(e) may not be transitive. This is witnessed by the lattice Bip(3) = Reg([3] × [3]), see Lemmas 8.5 and 8.6. Definition 7.5. A family (e i | i ∈ I) of pairwise disjoint transitive relations is orthogonal if there are no distinct i, j ∈ I and no p, q, r such that p = q, q = r, (p, q) ∈ e i , and (q, r) ∈ e j .

In particular, if (e i | i ∈ I) is orthogonal, then i∈I e i is itself a transitive relation. Proof. The proof of (i) is a straightforward exercise. For (ii), we define ϕ(x) = (x ∩ e i | i ∈ I) whenever x ⊆ e, and ψ(x i | i ∈ I) = i∈I x i whenever all x i ⊆ e i . By using (i), it is straightforward (although somewhat tedious) to verify that ϕ and ψ restrict to mutually inverse isomorphisms between Reg(e) and i∈I Reg(e i ), and also between Clop(e) and i∈I Clop(e i ).

Set ∆ A = {(x, x) | x ∈ A}, for every set A. By applying Proposition 7.6 to the 2-element family (e, ∆ A ), we obtain the following result, which shows that Reg(e ∪ ∆ A ) is the product of Reg(e) by a powerset lattice. Duquenne and Cherfouh [11, Theorem 3] and Le Conte de Poly-Barbut [22, Lemme 9] proved that every permutohedron is semidistributive (in the latter paper the result was extended to all Coxeter lattices). This result was improved by Caspard [START_REF] Caspard | The lattice of permutations is bounded[END_REF], who proved that every permutohedron is a bounded homomorphic image of a free lattice; and later, by Caspard, Le Conte de Poly-Barbut, and Morvan [START_REF] Caspard | Cayley lattices of finite Coxeter groups are bounded[END_REF], who extended this result to all finite Coxeter groups. Our next result shows exactly to which transitive (not necessarily antisymmetric) relations those results can be extended. (iv)⇒(i). Denote by {E i | i < n} the set of all connected components of e and set e i = e ∩ (E i × E i ) for each i < n. By Proposition 7.6, it suffices to consider the case where e = e i for some i, that is, e is connected. It suffices to prove that the join-dependency relation on Reg(e) has no cycle (cf. Freese, Ježek, and Nation [16, Corollary 2.39] together with the self-duality of Reg(e)). In the antisymmetric case, this follows from Corollary 7.

a 0 = {(1, 2)} , a 1 = {(1, 1), (1, 2)} , a 2 = {(2, 2), (1, 2)} , b 0 = {(2, 1)} , b 1 = {(1, 1), (2, 1)} , b 2 = {(2, 2), (2, 1)} .
In order to allay the confusion that might arise from the ordering of the lattice and its relation D being incompatible (e.g., pD q implies that p q), we mark the edges of the relation D with arrows, so for example a 0 < a 1 , a 1 D a 0 , and ¬(a 0 D a 1 ).

Corollary 7.9. Let e be a finite transitive relation. If Reg(e) is semidistributive, then the join-dependency relation defines a strict ordering on the join-irreducible elements of Reg(e).

Proof. By using Proposition 7.6, together with the characterization (iv) of semidistributivity of Reg(e) given in Theorem 7.8, it is easy to reduce the problem to the case where e is either antisymmetric or a loop a ⊳ e b ⊳ e a with a = b. In the first case, the conclusion follows from Corollary 7.3. In the second case, the join-dependency relation is bipartite (see the right hand side of Figure 7.2), thus transitive.

The lattices Bip(3) and Bip(4) are represented on Figure 7.3; they have 74 and 730 elements, respectively.

a 0 a 0 a 1 a 1 a 2 a 2 b 0 b 0 b 1 b 1 b 2 b 2 Bip(2)
The relation D on Ji(Bip(2)) Therefore, the lattice P(ω+1) is neither pseudocomplemented, nor semidistributive. The result that every (finite) permutohedron P(n) is pseudocomplemented originates in Chameni-Nembua and Monjardet [START_REF] Chameni-Nembua | Les treillis pseudocomplémentés finis[END_REF].

Join-dependency and congruences of bipartition lattices

In this paper we are using "bipartition" as a short naming for a transitive and cotransitive relation on [n], that is, for an element of Clop([n] × [n]). These objects are more properly called "ordres bipartitionnaires" (Han [START_REF] Han | Ordres bipartitionnaires et statistiques sur les mots[END_REF]) or "bipartitional relations" in (Hetyei and Krattenthaler [START_REF] Hetyei | The poset of bipartitions[END_REF]). The usual representation of these objects as "ordered bipartitions", on which the naming relies, will be recalled at the beginning of Section 9.

The Proof. Suppose first that (U, V ) forms a partition of [n]. It follows from Lemma 6.3 that a, U ր a, V ⊥ ; moreover, considering that both V and V c are nonempty, the relation a, V ր V ⊥ follows from Lemma 6.5. Hence a, U D V . Suppose from now on that (U, V ) does not form a partition of [n]. We shall find

W ∈ Pow[n] such that ({a} ∪ U c ) ∩ W c = ∅ , (8.1)
V c ∩ W c = ∅ , (8.2)
({a} ∪ U ) ∩ W = ∅ , (8.3)
V ∩ W = ∅ . (8.4) By Lemmas 6.5 and 6.6, this will ensure that a, U ր W ⊥ and W ր V ⊥ , hence that a, U D V .

If U ∩ V = ∅, set W = U ∩ V . Then (8.3) and (8.4) are trivial, while V ∪ W = V = [n] and U ∪ W = U = [n], so (8.1) and (8.2) are satisfied as well. If U ∩ V = ∅, then, as (U, V ) is not a partition of [n], we get U c ∩ V c = ∅; we set in this case W = U ∪ V . Again, it is easy to verify that (8.1)-(8.4) are satisfied. Definition 8.4. We say that a partition (U, U c ) of [n] is extremal if either U or U c is a singleton. The atom U will be called an extremal atom.

The description of the relation D on Bip(n) is completed by the following result.

Lemma 8.5. Let U, V ∈ Pow * [n]. Then U D V iff (U, V ) is not an extremal partition of [n].
Proof. The relation U D V holds iff there exists a join-irreducible p ∈ Bip(n) such that U ր p ⊥ and p ր V ⊥ . By Lemma 6.3, p cannot be a clepsydra. Hence, by Lemma 6.6, U D V iff there exists W ∈ Pow[n] such that

U ∩ W = ∅ , V ∩ W = ∅ , U c ∩ W c = ∅ , V c ∩ W c = ∅ . (8.5)
Suppose first that (U, V ) is an extremal partition of [n], so that either U = {a} or V = {a}, for some a ∈ [n]. In the first case,

U ∩ W = ∅ implies that a ∈ W , hence V ∪ W = [n]
, in contradiction with (8.5). Likewise, in the second case, a ∈ W and U ∪ W = [n], in contradiction with (8.5). In any case, the relation U D V does not hold. Conversely, suppose from now on that either (U, V ) is not a partition of [n], or it is not extremal. Suppose first that (U, V ) is a partition of [n] and pick (u, v) ∈ U × V . Then the set W = {u, v} meets both U and V . Furthermore,

U ∪ W = U ∪ {v} is distinct from [n] as V is not a singleton. Likewise V ∪ W = V ∪ {u} = [n]. Finally, suppose that (U, V ) is not a partition of [n]. If U ∩ V = ∅, then W = U ∩ V solves our problem. If U c ∩ V c = ∅, then W = U ∪ V solves our problem.
In any case, (8.5) holds for our choice of W . By using the end of Section 2 (in particular Lemma 2.2), the congruence lattice of Bip(n) can be entirely described by the relation D * on Ji(Bip(n)). Hence it can be obtained from the following easy consequence of Corollary 6.4 together with Lemmas 8.3 and 8.6.

Corollary 8.7. Suppose that n ≥ 3 and let p, q be join-irreducible elements of Bip(n). Then con(p) ⊆ con(q) iff either q is bipartite or p is a clepsydra and p = q.

In particular, the congruences con(p), for p a clepsydra, are pairwise incomparable, so they are the atoms of Con Bip(n). Each such congruence is thus determined by the corresponding clepsydra p, and those clepsydras are in one-to-one correspondence with the associated ordered pairs (a, U \ {a}). Hence there are n • 2 n-1 clepsydras, and we get the following result.

Minimal subdirect product decompositions of bipartition lattices

Here and in the next sections we shall use the following useful description of bipartitions introduced in Han [START_REF] Han | Ordres bipartitionnaires et statistiques sur les mots[END_REF] and studied further in Hetyei and Krattenthaler [20, § 2].

To every bipartition x of [n], we associate the relation ∼ x on [n] defined by p ∼ x q if either {(p, q), (q, p)} ⊆ x or {(p, q), (q, p)} ∩ x = ∅ , for all p, q ∈ [n] .

Then ∼ x is an equivalence relation, the equivalence classes of which can be enumerated as X 1 , . . . , X m in a unique way such that i < j ⇔ (p, q) ∈ x , whenever i = j in [m] , p ∈ X i , and q ∈ X j .

The sets X i , for i ∈ [m], will be called the blocks of x. For each i ∈ [m], either X i ×X i ⊆ x, in which case we set ε i = +1 and say that X i is an underlined block, or (X i ×X i )∩x = ∅, in which case we set ε i = -1 and say that X i is a non-underlined block.

The bipartition x can be recovered from the X i and the ε i , by

(p, q) ∈ x ⇔ (∃i, j ∈ [m]) p ∈ X i , q ∈ X j ,
and either i < j or (i = j and ε i = +1) .

We shall call (X ε1 1 , . . . , X εm m ) the ordered bipartition representation of x, and write

x = X ε1 1 ⊕ • • • ⊕ X εm m .
We shall also, occasionally, write X i instead of X -1 i (nonunderlined blocks) and X i instead of X +1 i (underlined blocks). In particular,

U = U c ⊕ U and a, V = (V c \ {a}) ⊕ {a} ⊕ (V \ {a}) whenever U ∈ Pow * [n], a ∈ [n], and V ∈ Pow[n].
As in Hetyei and Krattenthaler [20, § 6], we say that a permutation ρ of [n] is compatible with a bipartition x if (p, q) ∈ x and (q, p) / ∈ x ⇒ ρ -1 (p) < ρ -1 (q) , for all p, q ∈ [n] .

Notation 9.1. For any positive integer n, we define • G(n), the set of all bipartite join-irreducible elements of Bip(n) (i.e., those of the form

U c × U , where U ∈ Pow * [n]); • K(n), the (∨, 0)-subsemilattice of Bip(n) generated by G(n); • θ n , the congruence of Bip(n) generated by all Ψ(p), for p ∈ G(n); • S(n, p), the (∨, 0)-subsemilattice of Bip(n) generated by G(n) ∪ {p}, for each p ∈ Ji(Bip(n)).
By the results of Section 8, the D * -minimal join-irreducible of Bip(n) are exactly the clepsydras a, U , where a ∈ [n] and U ⊆ [n] (note that the clopen set a, U is uniquely determined by the ordered pair (a, U \ {a})). This is proved in Section 8 for n ≥ 3, but it is also trivially valid for n ∈ {1, 2} (cf. Figure 7.2). Hence the minimal subdirect product decomposition of Bip(n), given by (2.1), is the subdirect product Bip(n) ֒→

a∈[n] , U⊆[n]\{a} Bip(n)/Ψ( a, U ) . (9.1)
By Lemma 2.2, the factors of the decomposition (9.1) are exactly the lattices Bip(n)/Ψ( a, U ) ∼ = S(n, a, U ). Likewise, we can also observe that Bip(n)/θ n ∼ = K(n). We shall now identify, within Bip(n), the elements of S(n, a, U ).

Definition 9.2. An element a ∈ [n] is an isolated point of a bipartition x if (a, i) ∈ x and (i, a) ∈ x iff i = a, for each i ∈ [n]. We denote by isol(x) the set of all isolated points of x.

Lemma 9.3. Let x = i∈I x i in Bip(n). Then any isolated point a of x is an isolated point of some x i .

Proof. It suffices to prove that (a, a) ∈ x i for some i. As x is the transitive closure of the union of the x i , there are a positive integer ℓ and a = a 0 , a 1 , . . . , a ℓ-1 ∈ [n] such that, setting a ℓ = a, the pair (a k , a k+1 ) belongs to i∈I x i for each k < ℓ. As x is transitive, (a 0 , a 1 ), (a 1 , a 0 ) ∈ x, and a = a 0 is an isolated point of x, we get a 0 = a 1 , so (a, a) belongs to i∈I x i .

Proposition 9.4. The elements of K(n) are exactly the bipartitions without isolated points.

Proof. No bipartite join-irreducible element of Bip(n) has any isolated point, hence, by Lemma 9.3, no element of K(n) has any isolated point. Conversely, let x ∈ Bip(n) with no isolated point and let (i, j) ∈ x. If i = j, then, by Lemma 5.5, there exists U ∈ Pow * [n] such that (i, j) ∈ U ⊆ x.

If i = j, then, as x has no isolated point, there exists k = i such that (i, k) ∈ x and (k, i) ∈ x. By the paragraph above, there are Proof. Every join-irreducible element of Bip(n) which is either bipartite or equal to a, U satisfies both (i) and (ii) above, hence, by Lemma 9.3, so do all elements of S(n, a, U ). Conversely, let x ∈ Bip(n) satisfy both (i) and (ii) above. If isol(x) = ∅, then, by Proposition 9.4, x ∈ K(n), hence, a fortiori, x ∈ S(n, a, U ). Now suppose that isol(x) = {a}. It follows from (ii) together with the transitivity of x that a, U ⊆ x. For each (i, j) ∈ x \ {(a, a)}, it follows from the argument of the proof of Proposition 9.4 that there are

U, V ∈ Pow * [n] such that (i, k) ∈ U ⊆ x and (k, i) ∈ V ⊆ x. Hence (i, i) ∈ U ∨ V ⊆ x.
U, V ∈ Pow * [n] such that (i, j) ∈ U ∨ V ⊆ x. Hence x ∈ S(n, a, U ).
We are indebted to the first referee for the statement of the following result, which identifies the ordered bipartition representations (cf. Han [START_REF] Han | Ordres bipartitionnaires et statistiques sur les mots[END_REF], Hetyei and Krattenthaler [20, § 2]) of the elements of K(n) and S(n, a, U ), respectively. The proof of Lemma 9.6 is a straightforward exercise.

For a positive integer n, a ∈ [n], and U ⊆ [n], a bipartition x ∈ Bip(n) is (a, U )aligned if both sets (U c \ {a}) × {a} and {a} × (U \ {a}) are contained in x (observe that this does not imply that (a, a) ∈ x as a rule).

Lemma 9.6. The following statements hold:

(i) x ∈ K(n) iff no underlined block of x is a singleton. (ii) x ∈ S(n, a, U ) iff either x ∈ K(n)
or {a} is the only underlined singleton block of x and x is (a, U )-aligned.

Proposition 9.5 makes it possible to identify the factors of the minimal subdirect product decomposition (9.1) of the bipartition lattice Bip(n). Observe that a similar result is established, in Santocanale and Wehrung [START_REF] Santocanale | Sublattices of associahedra and permutohedra[END_REF], for the permutohedron P(n). In that paper, it is proved, in particular, that the corresponding subdirect factors are exactly the Cambrian lattices of type A (cf. Reading [START_REF] Reading | Cambrian lattices[END_REF]), denoted there by

A U (n), for U ⊆ [n].
Hence the lattices S(n, a, U ) can be viewed as the analogues, for bipartition lattices, of the Cambrian lattices of type A (i.e., the A U (n)). For either U = ∅ or U = [n] (the corresponding lattices are isomorphic, via x → x op ), we get the bipartition analogue of the Tamari lattice Santocanale and Wehrung [START_REF] Santocanale | Sublattices of associahedra and permutohedra[END_REF]), namely S(n, a, ∅ ) (whose isomorphism class does not depend on a). Proposition 9.7. Every lattice S(n, a, U ) is both isomorphic and dually isomorphic to S(n, a, U c ). In particular, S(n, a, U ) is self-dual.

A(n) = A [n] (n) (cf.
We shall present two proofs of Proposition 9.7, the first one relying on the lattice structure of Bip(n), the other one on the ordered bipartition representations that we recalled at the beginning of Section 9.

First proof of Proposition 9.7. Writing p = a, U , the clopen set p = a, U c depends only on p. An isomorphism from S(n, p) onto S(n, p) is induced by the mapping sending a relation x to its opposite x op .

We argue next that S(n, p) is dually isomorphic to S(n, p). To this goal, denote by M(p) the (∧, 1)-subsemilattice of Bip(n) generated by the set

{u ∈ Mi Bip(n) | (u, u * ) / ∈ Ψ(p)} .
It follows from Lemma 2.2, applied to the dual lattice of Bip(n), that Bip(n) op /Ψ(p) is isomorphic to M(p) endowed with the dual ordering of L; hence,

M(p) ∼ = S(n, p) ∼ = Bip(n)/Ψ(p) .
On the other hand, M(p) is dually isomorphic, via the operation x → x ⊥ of complementation on Bip(n), to the (∨, 0)-subsemilattice S ′ (p) of Bip(n) generated by the subset

G ′ (p) = {r ∈ Ji(Bip(n)) | (r ⊥ , (r * ) ⊥ ) / ∈ Ψ(p)} . Now for each r ∈ Ji(Bip(n)), (r ⊥ , (r * ) ⊥ ) / ∈ Ψ(p) ⇔ (G(n) ∪ {p}) ↓ r ⊥ = (G(n) ∪ {p}) ↓ (r * ) ⊥ (by Lemma 2.2) ⇔ (∃q ∈ G(n) ∪ {p})(q ≤ (r * ) ⊥ and q r ⊥ ) ⇔ (∃q ∈ G(n) ∪ {p})(q ր r ⊥ ) .
If r is bipartite, then, by Lemma 6.6, there is always q ∈ G(n) such that q ր r ⊥ (for example q = r). Now suppose that r = b, W is a clepsydra. By Lemma 6.3, q ր r ⊥ can occur only in case q = b, W c ; furthermore, this element belongs to

G(n) ∪ {p} iff a = b and U \ {a} = W c \ {a} (cf. Lemma 5.2). Therefore, G ′ (p) = G(n) ∪ {p} ,
and therefore S ′ (p) = S(n, p) is dually isomorphic to S(n, p).

Second proof of Proposition 9.7. We are indebted to the first referee of our paper for pointing to us the dual automorphism τ defined below. Observe that this proof yields the immediate observation that τ is involutive.

First, writing bipartition representations in reverse order, and keeping the underlinings, defines the automorphism

κ : Bip(n) → Bip(n) , x → x op . (9.2)
It follows immediately from Lemma 9.6 that this automorphism maps S(n, a, U ) onto S(n, a, U c ).

We shall now define an involutive dual automorphism τ of S(n, a, U ). For every x ∈ S(n, a, U ) with ordered bipartition representation (X ε1 1 , . . . , X εp p ), we denote by τ (x) = τ a,U (x) the ordered bipartition with ordered bipartition representation

(X ε ′ 1 1 , . . . , X ε ′ p p ), where for every i ∈ [p], we set (i) ε ′ i = -ε i if either card X i ≥ 2 or X i = {a} and x is (a, U )-aligned. (ii) ε ′ i = ε i if X i = {b}
where either b = a or x is not (a, U )-aligned. (Necessarily, ε i = -1; see Lemma 9.6.) It is obvious that τ is an involutive bijection of S(n, a, U ) onto itself. Hence we only need to prove that τ is order-reversing. Let x, y ∈ S(n, a, U ), with respective ordered bipartition representations (X ξ1 1 , . . . , X ξp p ) and (Y η1 1 , . . . , Y ηq q ), such that x ⊆ y. We shall prove that τ (y) ⊆ τ (x). By Hetyei and Krattenthaler [20, Proposition 6.4], there exists a permutation ρ of [n] which is compatible with both x and y, thus also with both τ (x) and τ (y); and furthermore, Every underlined X i is contained in some underlined Y j , (

Every non-underlined Y j is contained in some non-underlined X i (

(recall that the underlined blocks of x are the X i such that ξ i = 1). We must verify (ii) and (iii) of [START_REF] Hetyei | The poset of bipartitions[END_REF]Proposition 6.4] for the pair (τ (y), τ (x)).

First statement. Let j ∈ [q] such that η ′ j = 1, we prove that there exists i ∈ [p] such that ξ ′ i = 1 and Y j ⊆ X i . If Y j is not a singleton, then η j = -1, thus, by (9.4), there exists i ∈ [p] such that ξ i = -1 and Y j ⊆ X i . In particular, X i is not a singleton, thus ξ ′ i = 1 and we are done. Now suppose that Y j = {b}. From η ′ j = 1 it follows that b = a, η j = -1, and y is (a, U )-aligned. By (9.4), there exists i ∈ [p] such that a ∈ X i and ξ i = -1. If X i is not a singleton, then ξ ′ i = 1 and we are done. The remaining case is where X i = {a}. Since ρ is compatible with both x and y, X i = Y j = {a}, and y is (a, U )-aligned, x is also (a, U )-aligned, thus ξ ′ i = -ξ i = 1 and we are done.

Second statement. Let i ∈ [p] such that ξ ′ i = -1, we prove that there exists j ∈ [q] such that η ′ j = -1 and X i ⊆ Y j . Suppose first that X i is not a singleton. Hence ξ i = 1, thus, by (9.3), there exists j ∈ [q] such that X i ⊆ Y j and η j = 1. Since Y j cannot be a singleton, η ′ j = -1 and we are done. Suppose from now on that X i = {b}. There exists a unique j ∈ [q] such that b ∈ Y j , and we must prove that η ′ j = -1. Suppose, to the contrary, that η ′ j = 1. Necessarily, η j = -1. By (9.4), there exists ı ∈ [p] such that ξ ı = -1 and Y j ⊆ X ı . From {b} = X i ⊆ Y j ⊆ X ı it follows that ı = i and X i = Y j = {b}. Since η ′ j = 1, it follows that b = a and y is (a, U )-aligned. Since X i = Y j = {a} and ρ is compatible with both x and y, it follows that x is also (a, U )-aligned, thus In particular, the lattices A(n) and A U (n) are lattice-theoretical retracts of P(n) (this originates in Björner and Wachs [START_REF] Björner | Shellable nonpure complexes and posets. II[END_REF] and is stated formally in Santocanale and Wehrung [START_REF] Santocanale | Sublattices of associahedra and permutohedra[END_REF]).

-1 = ξ ı = ξ i = -ξ ′ i = 1, a contradiction.
In this section, we shall show that the behavior of the "bipartition-Cambrian lattices" S(n, k) (cf. Remark 9.8) is quite opposite to the one of Cambrian lattices of type A. In particular, for n ≥ 3, S(n, k) is never a lattice retract of Bip(n) (Corollary 10.16). This result will be achieved by proving that Bip(n) has no other lattice endomorphism than the "obvious" ones (Theorem 10.1).

Throughout this section we shall fix an integer n ≥ 3. Further, we shall denote by 1 the unit element of Bip(n), that is,

1 = [n] × [n].
Denote by S n the permutation group of [n]. For every σ ∈ S n , the assignment

f σ : a → {(σ(x), σ(y)) | (x, y) ∈ a} (10.1)
defines an automorphism of the lattice Bip(n), which commutes with the transposition automorphism κ defined in (9.2). Define the standard automorphisms of Bip(n) as those of the form either f σ or κ • f σ . The standard automorphisms of Bip(n) form a subgroup of the automorphism group of Bip(n), isomorphic to S n × S 2 . It will follow from Theorem 10.1 that every automorphism of Bip(n), for n ≥ 3, is standard. Theorem 10.1 does not extend to n = 2: there are 570 nonconstant lattice endomorphisms of Bip(2), 514 lattice endomorphisms preserving the bounds, while the group of automorphisms of Bip(2) is the 8-element dihedral group (cf. Figure 7.2).

Theorem 10.1. Let n be an integer, n ≥ 3. Then every nonconstant lattice endomorphism of Bip(n) is a standard automorphism.

The proof of Theorem 10.1 will be organized as follows. We will first prove, in Lemma 10.3, that the zero element in Bip(n) has more upper covers than any other element of Bip(n). This, together with the observation that the atoms of Bip(n) all generate the same congruence (Corollary 8.7) and join to 1 (Lemma 10.4) will show (Lemma 10.10) that any nonconstant lattice endomorphism f of Bip(n) must preserve the zero, and, dually, the unit. This will yield, for every U ∈ Pow * [n], a unique atom g(U ) below f ( U ) (Lemma 10.12), with g a permutation of Pow * [n] (Lemma 10.11) preserving complementary pairs (Lemma 10.13). A preliminary study of join-covering relations among join-irreducible elements of Bip(n) (Lemma 10.8), will enable us to prove that g preserves unordered extremal partitions (Lemma 10.15), which will yield a standard automorphism g ≤ f (i.e., g(x) ⊆ f (x) for every x ∈ Bip(n)). By applying that result to the dual endomorphism x → f (x c ) c , we will obtain a standard automorphism g ′ with f ≤ g ′ , and then our conclusion will be a consequence of the following well-known result.

Lemma 10.2 (folklore). Let f and g be automorphisms of a finite poset P , and let x ∈ P . If f (x) ≤ g(x), then f (x) = g(x). In particular, distinct automorphisms are incomparable with respect to the pointwise ordering.

Proof. If f (x) < g(x), then x < f -1 (g(x)), hence, setting h = f -1 g, we get an infinite ascending sequence

x < h(x) < h 2 (x) < • • • < h n (x) < • • • in P , a contradiction.
Lemma 10.3. If n ≥ 3, then the degree (i.e., the number of upper covers plus the number of lower covers) of every x ∈ Bip(n) is at most 2 n -2. In particular, if x = ∅, then x has less than 2 n -2 upper covers.

Note that Lemma 10. Suppose from now on that x = ∅ and x = 1; that is, m ≥ 2. By Hetyei and Krattenthaler [START_REF] Hetyei | The poset of bipartitions[END_REF]Theorem 5.1], the upper and lower covers of x can be evaluated according to the following rules:

(1) Merge two adjacent blocks

X εi i , X εi+1 i+1 with ε i = ε i+1 into a new block (X i ∪ X i+1 ) εi .
(2) Split a block X εi i into two new adjacent blocks Y εi , Z εi . (3) Exchange the polarity ε i of a singleton block X εi i . Let N i , for i ∈ {1, 2, 3}, be the number of upper and lower covers of x obtained according to rules (1), [START_REF] Bennett | Two families of Newman lattices[END_REF], and (3), respectively. Let N be the degree of x. It is immediate that N 1 ≤ m -1 and

N 2 + N 3 ≤ ni≥2 (2 ni -2) + card{i | n i = 1} ≤ m i=1 (2 ni -1) = m i=1 2 ni -m , whence N = N 1 + N 2 + N 3 ≤ m i=1 2 ni -1 . (10.2)
We claim that

m i=1 2 ni ≤ 2 n -1. Pick b i ∈ X i , for i ∈ [m]. Since m ≥ 2 and n ≥ 3, the sets X = m i=1 Pow(X i ) \ {∅} and B = {{b i , b j } | i = j} are both contained in Pow * [n]. Since m ≥ 2 and B ∩ X = ∅, it follows that m i=1 2 ni -1 = m i=1 2 ni -1 + m -1 ≤ m i=1 2 ni -1 + m 2 = card(X ∪ B) ≤ 2 n -2 ,
which proves our claim. The desired conclusion follows from (10.2).

Lemma 10.4. The following statements hold.

(i) J × I ∈ Bip(n) iff [n] = I ∪ J, for all I, J ⊆ [n]. (ii) U ∨ V = 1 iff V = U c , for all U, V ∈ Pow * [n]. Proof. (i) is obvious. (ii) It follows from (i) that a = (U c ∪ V c ) × (U ∪ V ) belongs to Bip(n). Since U ∨ V is contained in a, it follows that U ∨ V = 1 implies that a = 1, that is, V = U c .
Assume, conversely, that V = U c , and pick (u, v) ∈ U × U c . Let x, y ∈ [n], we prove that (x, y) ∈ U ∨ U c . Since this holds whenever (x, y) ∈ U ∪ U c , it remains to check the case where {x, y} ⊆ U and the case where {x, y} ⊆ U c . In the first case, the desired conclusion follows from (x, v) ∈ U c and (v, y) ∈ U . In the second case, it follows from (x, u) ∈ U and (u, y) ∈ U c .

From now on we shall denote by P the set of all atoms of Bip(n) (that is, the set of all U , for U ∈ Pow *

Q = P ∪ {ã x | x ∈ [n]} ∪ { bx | x ∈ [n]}.
Proof. Let p = x, U , with U ⊆ {x} c , be a clepsydra. The distinct bipartitions u = U c × U and v = (U c \ {x}) × (U ∪ {x}) are properly contained in p, thus, if p ∈ Q, then either u or v is not an atom, that is, either u = ∅ or v = ∅, which easily implies that either p = ãx or p = bx . Now let c ∈ Q \ P . By Lemmas 8.1 and 8.2, c is the join of the atoms and of the clepsydras below it. Since c ∈ Q \ P , there is at least a clepsydra below c. Every such clepsydra belongs to Q, thus it has the form either ãx or bx . Since the lower covers of those clepsydras, that is, all the a x and b x , are pairwise distinct, it follows that there is exactly one clepsydra below c, which, by symmetry, may be assumed to be ãx . Since c ∈ Q, the only atom below c is a x . Therefore, c = ãx ∨ a x = ãx . . Furthermore, if card I ≥ 2, then the equality holds everywhere. Proof. A simple application of the dual automorphism x → x op reduces the statement about the b i to the one about the a i . Then the only nontrivial statement to establish is that if card I ≥ 2, then [n] × I is contained in a = i∈I a i . We must prove that any (x, i) ∈ [n] × I belongs to a. If x = i, then (x, i) ∈ a i ⊆ a. Suppose now that x = i. Since card I ≥ 2, there exists j ∈ I \ {i}. From (i, j) ∈ a j and (j, i) ∈ a i it follows again that (i, i) ∈ a.

Lemma 10.7. The set {a

i | i ∈ [n]}∪{b i | i ∈ [n]} generates Bip(n) as a sublattice.
Proof. It follows immediately from Lemma 10.6 that ãi = (a i ∨ a j ) ∩ (a i ∨ a k ), thus, a fortiori, ãi = (a i ∨ a j ) ∧ (a i ∨ a k ) whenever i, j, k are distinct. A similar formula holds for bi . Finally, if card I, card J ≥ 2 we get J

× I = i∈I a i ∩ j∈J b j ; if I ∪ J = [n], then J × I ∈ Bip(n), thus, a fortiori, J × I = i∈I a i ∧ j∈J b j .
Since all join-irreducible elements of Bip(n) have one of the forms a i , b i , ãi , bi , or J × I above (with card I, card J ≥ 2), and since the join-irreducible elements generate Bip(n) as a sublattice, the conclusion follows.

a k ⊆ {k} c × [n] ⊆ j∈J b j ⊆ i∈I a i ∨ j∈J b j . Further, it is trivial k ∈ I implies a k ⊆ i∈I a i ∨ j∈J b j .
Conversely, suppose that a k ⊆ i∈I ãi ∨ j∈J bj . By Lemma 10.6, it follows that {k}

c × {k} = a k is contained in ([n] × I) ∨ (J × [n]) = ([n] × I) ∪ (J × [n]
) (we use here the disjointness of I and J). It follows easily that either ∈ I or {k} c ⊆ J. Remark 10.9. Lemma 10.8 shows that {b j | j = i} is the unique nontrivial minimal join-cover of a i made of extremal atoms (cf. Definition 8.4). However, by Lemma 8.5, a i has many other minimal join-covers.

From now on we shall fix a nonconstant lattice endomorphism f of Bip(n). We shall prove that f is a standard automorphism. The main part of the argument consists of proving that there exists a standard automorphism g such that g ≤ f . Lemma 10.10. f -1 {∅} = ∅ and f -1 {1} = {1}.

Proof. We claim that f (p) = f (∅), for every atom p of Bip(n). Suppose, to the contrary, that f (p) = f (∅). This means that con(p) is contained in the kernel of f , hence, by Corollary 8.7, con(q) is also contained in the kernel of f , that is, f (q) = f (∅), for every atom q. By Lemma 10.4(ii), it follows that (1) = f (∅), a contradiction since f is nonconstant. Now suppose that f (∅) = ∅. It follows from Lemma 10.3 that f (∅) has less than 2 n -2 upper covers in Bip(n). For every atom p of Bip(n), it follows from our claim that there exists an upper cover a p of f (∅) such that a p ⊆ f (p). Since Bip(n) has 2 n -2 atoms, there are distinct atoms p and q of Bip(n) such that a p = a q ; denote by a the common value. It follows that a ⊆ f (p) ∧ f (q) = f (p ∧ q) = f (∅), a contradiction. This proves that f (∅) = ∅. If f (a) = ∅ for some a = ∅, then f (p) = ∅ for some atom p, in contradiction with the claim. Hence f -1 {∅} = {∅}.

By applying the above result to the endomorphism x → f (x c ) c , we obtain that f -1 {1} = {1}. Proof. It suffices to prove that g is one-to-one. Suppose that g(U 0 ) = g(U 1 ) = V , for V ∈ Pow * [n] and distinct U 0 , U 1 ∈ Pow * [n]. By using Lemma 10.10, we get

V ⊆ f ( U 0 ) ∧ f ( U 1 ) = f ( U 0 ∧ U 1 ) = f (∅) = ∅ , a contradiction.
Our next lemma shows that the elements f (p), for an atom p, all belong to Q. Lemma 10.12.

Let U ∈ Pow * [n]. Then g(U ) is the unique V ∈ Pow * [n] such that V ⊆ f ( U ). In particular, f ( U ) belongs to Q. Proof. Let V ∈ Pow * [n] such that V ⊆ f ( U ) and suppose that V = g(U ). By Lemma 10.11, there exists U ′ ∈ Pow * [n] such that V = g(U ′ ). Necessarily, U ′ = U , hence V ⊆ f ( U ) ∧ f ( U ′ ) = f ( U ∧ U ′ ) = f (∅) = , a contradiction. Lemma 10.13. g(U c ) = g(U ) c , for every U ∈ Pow * [n]. Proof. Set V = g(U ). By Lemma 10.11, V c = g(U ′ ) for some U ′ ∈ Pow * [n]. From Lemma 10.4 it follows that 1 = V ∨ V c , thus 1 = f ( U ) ∨ f ( U ′ ) = f ( U ∨ U ′ ),
∈ Bip(n), let U ∈ Pow * [n], and let U 1 , . . . , U m ∈ Pow * [n]. Then U ⊆ m i=1 U i ∨ x implies that g(U ) ⊆ m i=1 g(U i ) ∨ f (x).
Proof. We may assume that U = U i for each i ∈ [m]. By Lemmas 10.5 and 10.12, for every i, the element p i = f ( U i ) is either equal to g(U i ) or to a clepsydra with lower cover g(U i ) . Since f is a join-homomorphism and by the definition of g, we get g

(U ) ⊆ f ( U ) ⊆ m i=1 p i ∨ f (x). Let I be a minimal subset of [m] such that g(U ) ⊆ i∈I p i ∨ i∈[m]\I g(U i ) ∨ f (x) ,
and suppose that I is nonempty. Pick j ∈ I. By the minimality assumption on I, p j is a clepsydra with lower cover (p j ) * = g(U j ) and we obtain

g(U ) ⊆ i∈I\{j} p i ∨ i∈[m]\I g(U i ) ∨ (p j ) * ∨ f (x) ,
hence g(U ) D p j , which is impossible since p j is a clepsydra and by Lemma 6.4. Hence I = ∅, which proves the desired containment. Proof. Suppose otherwise. It follows from Lemma 8.5 that U D U c , so there exists x ∈ Bip(n) such that U ⊆ U c ∨ x and U ⊆ x. A direct application of Lemma 10.14, for m = 1, yields that

g(U ) ≤ g(U c ) ∨ f (x) . (10.3) Since U ⊆ x and U is an atom, f ( U ) ∧ f (x) = f ( U ∧ x) = f (∅) = ∅, thus, a fortiori, g(U ) ∧ f (x) = ∅,
and thus g(U ) ⊆ f (x). By (10.3) and since g(U c ) is an atom, it follows that g(U ) D g(U c ) .

Now by Lemma 10.13, g(U c ) = g(U ) c . By Lemma 8.5, it follows that neither g(U ) nor g(U ) c is a singleton, which contradicts our assumption.

End of the proof of Theorem 10.1. Lemma 10.15 shows that the necessarily bijective correspondence sending {U, U c } to {g(U ), g(U ) c } preserves extremal (unordered) partitions, see Definition 8.4. As n ≥ 3, an extremal unordered partition is uniquely identified by its singleton; thus, there exists a permutation γ ∈ S n such that {g({i}), g({i} c )} = {{γ(i)}, {γ(i)} c } for all i ∈ [m]; so g({i}) is either equal to {γ(i)} or to {γ(i)} c . Say that g is positive at i, in the first case, and negative at i, in the second case.

We want to prove that there exists a standard automorphism g ≤ f . By possibly precomposing f with κ, we reduce the problem to the case where g is positive at 1. From {1} ⊆ j =1 {j} c together with Lemma 10.14 we get a γ(1) = {γ(1)} = g({1}) ⊆ j =1 g({j} c ) , with each g({j} c ) ∈ {a γ(j) , b γ(j) }. By Lemma 10.8, it follows that g({j} c ) = b γ(j) for all j = 1, thus, by Lemma 10.13, g({j}) = a γ(j) , and thus g is positive at every element of [n]. Hence, for every i ∈ [n],

f γ (a i ) = a γ(i) = g({i}) ⊆ f ( {i} ) = f (a i ) ,
and, similarly (using Lemma 10.13), f γ (b i ) ⊆ f (b i ). Since {x | f γ (x) ⊆ f (x)} is a sublattice of Bip(n), it follows from Lemma 10.7 that f γ ≤ f . By applying this result to the endomorphism x → f (x c ) c , it follows that there exists γ ′ ∈ S n such that f ≤ f γ ′ . Since f γ ≤ f ≤ f γ ′ and by Lemma 10.2, it follows that f = f γ = f γ ′ . Corollary 10.16. Let n ≥ 3. Then no nontrivial lattice quotient of Bip(n) can be embedded into Bip(n) as a sublattice. In particular, neither K(n) nor S(n, k), where 0 ≤ 2k < n, can be embedded into Bip(n) as a sublattice.

Proof. Let L be a lattice and let f : Bip(n) ։ L be a surjective lattice homomorphism. If g : L ֒→ Bip(n) is a lattice embedding, then g•f is a lattice endomorphism of Bip(n), thus, by Theorem 10.1, either g • f is constant (in which case f is constant) or g • f is an isomorphism (in which case f is an isomorphism).

Remark 10.17. For any sets E and F and any surjective map f : F ։ E, we can define a lattice embedding f [-1] : Bip(E) ֒→ Bip(F ), preserving the bounds, by setting

f [-1] (a) = {(x, y) ∈ F × F | (f (x), f (y)) ∈ a} ,
for all a ∈ Bip(E) .

For an infinite set E, there is a surjective, non-injective map f : E ։ E, and then f [-1] is not surjective (for if x = y and f (x) = f (y), then {x} c × {x} does not belong to the range of f [-1] ). This shows that Theorem 10.1 does not extend to the infinite case, even for lattice embeddings preserving the bounds.

On the other hand, an easy modification of the proof of Theorem 10.1, with joins and meets no longer necessarily finite, makes it possible to prove that Every automorphism of the poset Bip(E) is standard (with the obvious extension of the definition of "standard" to arbitrary sets), for any (possibly infinite) set E with at least three elements. The proof of this result is, actually, noticeably easier than the one of Theorem 10.1, as atoms are automatically sent to atoms, so the proof yields directly f γ = f (instead of only f γ ≤ f ).

Cardinalities of the bipartition-Cambrian lattices

It is known since Reading [START_REF] Reading | Cambrian lattices[END_REF]Theorem 1.3] that all Cambrian lattices of type A, associated with the permutohedron of index n (i.e., the lattices A U (n)), have cardinality 1 n+1 2n n , which is independent of U (i.e., of the orientation). This result actually extends to all finite Coxeter groups, as it can be seen by combining Reading [START_REF] Reading | Clusters, Coxeter-sortable elements and noncrossing partitions[END_REF]Theorem 9.1] with Reading [29, Theorem 1.1]: the former gives the enumeration of all sortable elements, while the latter says that the sortable elements are exactly the minimal elements of the Cambrian congruence classes. Hohlweg and Lange give in [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF] a geometric interpretation of the undirected covering graphs of Cambrian lattices of type either A or B as oriented vertex-edge graphs of the corresponding associahedra; see Section 1 of that paper.

The following computations emphasize that the situation is quite different for the subdirectly irreducible factors S(n, k) of Bip(n), whose size depends on k.

We shall set M (n) = card Bip(n), K(n) = card K(n), and S(n, k) = card S(n, k) (cf. Remark 9.8), for all possible values of n and k. It is established in Wagner [33] that the M (n) are characterized by the induction formula The sequence of numbers M (n) is A004123 of Sloane's Encyclopedia of Integer Sequences [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF].

M (0) = 1 ; M (n) = 2 • n k=1 n k M (n -k) if n > 0 . ( 11
We are indebted to the first referee for suggesting us the following formulas (11.2) and (11.3) for calculating K(n) and S(n, k), for all possible values of n and k. We shall use the characterizations of the elements of K(n) and S(n, k) given by Lemma 9.6. Let x ∈ Bip(n) with ordered bipartition representation (X ε1 1 , . . . , X εp p ). We first count all the possibilities where x ∈ K(n). Set l = card X p . If 2 ≤ l ≤ n, then both underlinings of X p are possible, and there are K(n -l) possiblities for (X ε1 1 , . . . , X εp-1 p-1 ), which gives 2 n l K(n -l) possibilities. If l = 1, then only the underlining ε p = -1 is possible, which gives n • K(n -1) possibilities. Hence the K(n) are given by the induction formula

K(0) = 1; K(n) = n • K(n -1) + 2 n l=2 n l K(n -l) if n > 0 . (11.2)
For small values of n, these numbers are the following: 12. Open problems

Our first problem asks for a converse to Theorem 7.8.

Problem 1. Can every finite ortholattice, which is also a bounded homomorphic image of a free lattice, be embedded into Reg(e), for some finite strict ordering e?

A variant of Problem 1, for arbitrary finite ortholattices, is the following.

Problem 2. Can every finite ortholattice be embedded into Bip(n), for some positive integer n?

On the opposite side of Problems 1 and 2, it is natural to state the following problems. Problem 3. Is there a nontrivial lattice (resp., ortholattice) identity that holds in Reg(e) for every finite strict ordering e? Problem 4. Is there a nontrivial lattice (resp., ortholattice) identity that holds in Bip(n) for every positive integer n?

Bruns observes in [6, §(4.2)] that the variety of all ortholattices is generated by its finite members (actually, the argument presented there shows that "variety" can even be replaced by "quasivariety"). This shows, for example, that Problems 2 and 4 cannot simultaneously have a positive answer.

  Throughout the paper, by "relation" (on a possibly infinite set) we shall always mean a binary relation. For a relation e on a set E, we will often writex ⊳ e y ⇐⇒ def.(x, y) ∈ e , x e y ⇐⇒ def.

  [a, b] e = {x | a e x and x e b} , [a, b[ e = {x | a e x and x ⊳ e b} , ]a, b] e = {x | a ⊳ e x and x e b} , [a] e = [a, a] e , for all a, b ∈ E. As a ⊳ e a may occur, a may belong to ]a, b] e .

  subset a ⊆ e is clopen if a = cl(a) = int(a). We denote by Clop(e) the poset of all clopen subsets of e. A subset a ⊆ e is regular closed (resp., regular open) if a = cl int(a) (resp., a = int cl(a)). We denote by Reg(e) (resp., Reg op (e)) the poset of all regular closed (resp., regular open) subsets under set inclusion. As a set x is open iff its complement x c = e\ x is closed (by definition), similarly a set x is closed (regular closed, regular open, clopen, respectively) iff x c is open (regular open, regular closed, clopen, respectively).

Lemma 3 . 1 .

 31 The following statements hold, for any transitive binary relation e (on a possibly infinite set ): (i) The operators cl • int and int • cl are both idempotent. (ii) A subset x of e is regular closed iff x = cl(u) for some open set u. (iii) The poset Reg(e) is a complete lattice, with meet and join given by i∈I a i = cl i∈I a i , i∈I a i = cl int i∈I a i , for any family (a i | i ∈ I) of regular closed sets.

Corollary 3 . 4 .

 34 The lattices Reg(e) and Reg op (e) are pairwise isomorphic, and also self-dual, for any transitive relation e. The isomorphisms are given by Reg(e) → Reg op (e), x → int cl(x) and Reg op (e) → Reg(e), x → cl int(x).

4 .Lemma 4 . 2 .

 442 Lattices of clopen subsets of square-free transitive relations Definition 4.1. A transitive relation e is square-free if for all (a, b) ∈ e, any two elements of [a, b] e are comparable with respect to e . That is, (∀a, b, x, y) a e x and a e y and x e b and y e b =⇒ (either x e y or y e x) . For the particular case of the natural strict ordering 1 < 2 < • • • < n, the following result originates in Guilbaud and Rosenstiehl [18, § VI.A]. The case of the full relation [n] × [n] is covered by the proof of Hetyei and Krattenthaler [20, Proposition 4.2]. Let e be a square-free transitive relation. Then the set int(a) is closed, for each closed a ⊆ e. Dually, the set cl(a) is open, for each open a ⊆ e. Proof. It suffices to prove the first statement. Let x ⊳ e y ⊳ e z with (x, y) ∈ int(a) and (y, z) ∈ int(a), we must prove that (x, z) ∈ int(a). Consider a subdivision x = s 0 ⊳ e s 1 ⊳ e • • • ⊳ e s n = z and suppose that (s i , s i+1 ) / ∈ a for each i < n (4.1) (we say that the subdivision fails witnessing (x, z) ∈ int(a)). Denote by l the largest integer such that l < n and s l e y. If s l = y, then the subdivision x = s 0 ⊳ e s 1 ⊳ e • • • ⊳ e s l = y fails witnessing (x, y) ∈ int(a), a contradiction; so s l = y and s l ⊳ e y. From x = s 0 ⊳ e s 1 ⊳ e • • • ⊳ e s l ⊳ e y, (x, y) ∈ int(a), and (4.1) it follows that (s l , y) ∈ a . (4.2)

2 .

 2 From (a, u) ∈ x 0 ⊆ z and (u, b) ∈ x 1 ⊆ z and the transitivity of z it follows that (a, b) ∈ z, thus, as a ⊳ e v ⊳ e b and z is open, either (a, v) ∈ z or (v, b) ∈ z. In the first case, (a, v) ∈ y 1 , thus v e u, a contradiction. In the second case, (v, b) ∈ y 0 , thus u e v, a contradiction. By applying Theorem 4.3 to the full relation [n] × [n], which is trivially squarefree (cf. Definition 4.1; here, x e y always holds), we obtain the following result, first proved in Hetyei and Krattenthaler [20, Theorem 4.1]. Corollary 4.4 (Hetyei and Krattenthaler). The poset Bip(n) of all bipartitions of [n] is a lattice, for every positive integer n.

Example 4 . 5 .

 45 We set δ E = {(x, y) ∈ E × E | x < y}, for any poset E, and we set P(E) = Clop(δ E ) and R(E) = Reg(δ E ). By Theorem 4.3 (see alsoPouzet et al. [26, Lemma 12]), P(E) is a lattice iff E contains no copy of the four-element Boolean lattice B 2 = {0, a, b, 1} (represented on the left hand side diagram of Figure4.1)that is, by using the above terminology, δ E is square-free.The lattice R(B 2 ) has 20 elements, while its subset P(B 2 ) has 18 elements. The lattice R(B 2 ) is represented on the right hand side of Figure4.1. Its join-irreducible elements, all clopen (see a general explanation in Theorem 5.8), are

Definition 5 . 1 .

 51 We denote by F(e) the set of all triples (a, b, U ), where (a, b) ∈ e, U ⊆ [a, b] e , and a = b implies that a / ∈ U and b ∈ U . We set U c = [a, b] e \ U , and a, b; U = {(x, y) | a e x ⊳ e y e b , x / ∈ U , and y

Lemma 5 . 2 .

 52 Let (a, b, U ), (c, d, V ) ∈ F(e). Then a, b; U = c, d; V iff one of the following statements occurs:

Lemma 5 . 3 .

 53 (i) a = b, c = d, a ≡ e c, b ≡ e d, and U = V ; (ii) a = b = c = d and U \ {a} = V \ {a}. The set p = a, b; U is clopen and (a, b) ∈ p, for each (a, b, U ) ∈ F(e). Furthermore, the set p * defined by

Proof.

  In both cases (i.e., either a = b or a = b) it is trivial that (a, b) ∈ p. Consider first the case where a = b. In that case, p is bipartite, thus closed. Let x ⊳ e y ⊳ e z with (x, z) ∈ p. If y ∈ U , then (x, y) ∈ p, and if y / ∈ U , then (y, z) ∈ p. Hence p is clopen. As p * ⊆ p and p is bipartite, p * is bipartite as well, thus p * is closed. Let x ⊳ e y ⊳ e z with (x, z) ∈ p * , and suppose by way of contradiction that (x, y) / ∈ p * and (y, z) / ∈ p * . As p is open, either (x, y) ∈ p or (y, z) ∈ p, hence either (x, y) or (y, z) belongs to p ∩ ([a] e × [b] e ). In the first case, x ≡ e a and x / ∈ U . Furthermore, b ≡ e y ⊳ e z, but z e b (because (x, z) ∈ p * ⊆ p), so z ≡ e b, and so we get (x, z) ∈ p ∩ ([a] e × [b] e ) = p \ p * , a contradiction. The second case is dealt with similarly. Therefore, p * is open. Let u ⊆ p be open and suppose that u is not contained in p * . This means that there exists (a ′ , b ′ ) ∈ u such that a ≡ e a ′ and b ≡ e b ′ . We must prove that p ⊆ u. Let (x, y) ∈ p; in particular, x / ∈ U and y ∈ U . From x / ∈ U it follows that (a ′ , x) / ∈ p, thus (a ′ , x) / ∈ u; whence, from a ′ e x ⊳ e b ′ , (a ′ , b ′ ) ∈ u, and the openness of u, we get (x, b ′ ) ∈ u. Now y ∈ U , thus (y, b ′ ) / ∈ p, and thus (y, b ′ ) / ∈ u, hence, as x ⊳ e y e b ′ , (x, b ′ ) ∈ u, and u is open, we get (x, y) ∈ u, as required.

Corollary 5 . 4 .

 54 Let (a, b, U ) ∈ F(e). The clopen set p = a, b; U is completely joinirreducible in the lattice Reg(e), and the element p * constructed in the statement of Lemma 5.3 is the lower cover of p in that lattice. Proof. Let a p be a regular closed set. As int(a) is open and properly contained in p, it follows from Lemma 5.3 that int(a) ⊆ p * . Hence, since a is regular closed and p * is clopen, we get a = cl int(a) ⊆ cl(p * ) = p * . Lemma 5.5. Every open subset u of e is the set-theoretical union of all its subsets of the form a, b; U , where (a, b, U ) ∈ F(e). In particular, every open subset of e is a union of clopen sets. Proof. Let (a, b) ∈ u, we must find U such that (a, b, U ) ∈ F(e) and a, b; U ⊆ u.

Corollary 5 . 6 .

 56 The lattice Reg(e) is, up to isomorphism, the Dedekind-MacNeille completion of the poset Clop(e). In particular, every completely join-irreducible element of Reg(e) is clopen. Proof. Let a be regular closed; in particular, a = cl(b), with b open. Write b as a union of clopen sets, b = i∈I c i . Applying the closure operator cl to both sides of the equation, we obtain the equality a = i∈I c i in Reg(e). Thus every element of Reg(e) is a join of elements from Clop(e); by duality, every element of Reg(e) is a meet of elements from Clop(e). It immediately follows, see Davey and Priestley [10, Theorem 7.41], that Reg(e) is the Dedekind-MacNeille completion of the poset Clop(e).

Lemma 5 .

 5 5 makes it possible to extend Pouzet et al.[START_REF] Pouzet | A generalized permutahedron[END_REF] Lemma 11], from permutohedra on posets, to lattices of regular closed subsets of transitive relations. This result also refines the equivalence (ii)⇔(iii) of Theorem 4.3. Corollary 5.7. The following statements hold, for any (possibly infinite) family (a i | i ∈ I) of clopen subsets of e: (i) The set {a i | i ∈ I} has a meet in Clop(e) iff int i∈I a i is clopen, and then the two sets are equal. (ii) The set {a i | i ∈ I} has a join in Clop(e) iff cl i∈I a i is clopen, and then the two sets are equal. Proof. A simple application of the involution x → e \ x reduces (ii) to (i). On the way to proving (i), we define the open set u = int i∈I a i . It is trivial that if u is clopen, then it is the meet of {a i | i ∈ I} in Clop(e). Conversely, suppose that {a i | i ∈ I} has a meet a in Clop(e). It is obvious that a ⊆ u. Let (x, y) ∈ u. By Lemma 5.5, there exists b ⊆ u clopen such that (x, y) ∈ b. It follows from the definition of a that b ⊆ a, thus (x, y) ∈ a. Therefore, u = a is clopen.

Theorem 5 . 8 .

 58 The completely join-irreducible elements of Reg(e) are exactly the elements a, b; U , where (a, b, U ) ∈ F(e). Furthermore, the lattice Reg(e) is spatial. Proof. Let a ∈ Reg(e). As int(a) is open, it follows from Lemma 5.5 that we can write int(a) = i∈I a i , b i ; U i , for a family ((a i , b i , U i ) | i ∈ I) of elements of F(e). As the elements a i , b i ; U i are all clopen (thus regular closed) and a is regular closed, it follows that a = cl int(a) = i∈I a i , b i ; U i in Reg(e) .

  .1) and thus (c, c) ∈ a, b; U , which rules out a = b (cf. Definition 5.1). Hence a = b and c belongs to ({a}

  5.1) are exactly the singletons {(a, a)}, where a ⊳ e a. On the other hand, if a = b, then a, b; U determines both the ordered pair (a, b) and the set U . (Recall that a clepsydra is never bipartite, so it cannot have the form a, b; U with a = b.) Let us focus for a while on arrow relations involving bipartite join-irreducible clopen sets. We set U ↾ c,d = (U ∩ ]c, d] e ) ∪ {d} , for all (c, d) ∈ e and all U ⊆ E . Observe that (c, d, U ↾ c,d ) ∈ F(e). The following lemma is a restated variant of Corollary 6.7. Lemma 7.1. Let (a, b, U ), (c, d, V ) ∈ F(e) with a = b and c = d, and set U = (E \ U )↾ a,b . Then a, b; U ր c, d; V ⊥ iff [c, d] e ⊆ [a, b] e and V = U ↾ c,d .

Corollary 7 . 3 .Example 7 . 4 .

 7374 Let e be an antisymmetric, transitive relation on a finite set. Then the join-dependency relation on the join-irreducible elements of Reg(e) is a strict ordering. The transitivity of the relation D, holding on the join-irreducible elements of Reg(e) for any antisymmetric transitive relation e, is quite a special property. It does not hold in all finite bounded homomorphic images of free lattices, as shows the lattice L 9 (following the notation of Jipsen and Rose[START_REF] Jipsen | Varieties of Lattices[END_REF]) represented on the left hand side of Figure7.1. The join-irreducible elements marked there by doubled circles satisfy p D q and q D r but not p D r.

Figure 7 . 1 .

 71 Figure 7.1. Bounded lattices with non-transitive join-dependency relation

Proposition 7 . 6 .

 76 The following statements hold, for any orthogonal family (e i | i ∈ I) of transitive relations: (i) A subset x of e is closed (resp., open in e) iff x ∩ e i is closed (resp., open in e i ) for each i ∈ I. (ii) Reg(e) ∼ = i∈I Reg(e i ), via an isomorphism that carries Clop(e) onto i∈I Clop(e i ).

Corollary 7 . 7 .

 77 Let e be a transitive relation and let A be a set with e ∩ ∆ A = ∅. Then Reg(e ∪ ∆ A ) ∼ = Reg(e) × (Pow A) and Clop(e ∪ ∆ A ) ∼ = Clop(e) × (Pow A).

Theorem 7 . 8 .

 78 The following are equivalent, for any transitive relation e on a finite set E: (i) The lattice Reg(e) is a bounded homomorphic image of a free lattice. (ii) The lattice Reg(e) is semidistributive. (iii) The lattice Reg(e) is pseudocomplemented. (iv) Every connected component of the preordering e either is antisymmetric or has the form {a, b} with a = b while (a, b) ∈ e and (b, a) ∈ e. Proof. (i)⇒(ii) is well-known, see for example Freese, Ježek, and Nation [16, Theorem 2.20]. (ii)⇒(iii) is trivial. (iii)⇒(iv) follows immediately from Proposition 3.5.

3 .

 3 If E = {a, b} with a = b while (a, b) ∈ e and (b, a) ∈ e, then Reg(e) is isomorphic to the lattice Bip(2) of all bipartitions of a two-element set (cf. Section 3). The relation D on the join-irreducible elements of Bip(2), represented on the right hand side of Figure 7.2, has no cycle. The Hasse diagram of the lattice Bip(2) is represented on the left hand side of Figure 7.2. On the right hand side of Figure 7.2 we represent (the digraph of) the relation D on the join-irreducible elements of Bip(2). The join-irreducible elements of Bip(2) are denoted there by

Figure 7 . 2 .Example 7 . 10 .

 72710 Figure 7.2. The lattice Bip(2) of all bipartitions of {1, 2} and its relation D

Figure 7 . 3 .

 73 Figure 7.3. The lattices Bip(3) and Bip(4)

Lemma 8 . 1 . 4 : 8 . 2 .

 81482 full relation [n] × [n] is transitive, for any positive integer n, and Reg([n] × [n]) = Clop([n] × [n]) = Bip(n) (cf. Section 3), the bipartition lattice of n. Due to the existence of exactly one ≡ [n]×[n] -class (namely the full set [n]), the description of the join-irreducible elements of Bip(n) obtained from Theorem 5.8 takes a particularly simple form. The join-irreducible elements of Bip(n) consist of the sets U = U c ×U for U ∈ Pow * [n] (those are the bipartite ones) together with the sets a, U = ({a} ∪ U c ) × ({a} ∪ U ) for a ∈ [n] and U ∈ Pow[n] (those are the clepsydras). The associated lower covers are immediately obtained from Corollary 5.Lemma The bipartite U (with U ∈ Pow * [n]) are the atoms of Bip(n) while, for clepsydras a, U (with a ∈ [n] and U ∈ Pow[n]), a, U * = a, U \ {(a, a)}. Lemma 8.3. Let (a, U ) ∈ [n] × Pow[n] and let V ∈ Pow * [n]. Then a, U D V always holds (within Bip(n)).

Lemma 8 . 6 .

 86 Suppose that n ≥ 3 and let U, V ∈ Pow * [n]. Then either U D V or U D 2 V . Proof. By Lemma 8.5, if the relation U D V fails, then there exists a ∈ [n] such that {U, V } = {{a}, [n] \ {a}}. Pick any b ∈ [n] \ {a} and set W = {a, b}. As n ≥ 3, neither (U, W ) nor (W, V ) is a partition of [n]. By Lemma 8.5, it follows that U D W and W D V .

Corollary 8 . 8 .

 88 The congruence lattice of the bipartition lattice Bip(n) is obtained from a Boolean lattice with n • 2 n-1 atoms by adding a new top element, for every integer n ≥ 3. Corollary 8.8 does not extend to the case where n = 2: the congruence lattice of Bip(2) is isomorphic to the lattice of all lower subsets of the poset represented on the right hand side of Figure 7.2.

  Therefore, x is a join of clopen sets of the form U . Proposition 9.5. Let a ∈ [n] and let U ⊆ [n]. The elements of S(n, a, U ) are exactly the bipartitions x such that (i) isol(x) ⊆ {a}, (ii) if isol(x) = {a}, then U c × {a} and {a} × U are both contained in x.

Remark 9 . 8 .

 98 Set S(n, k) = S(n, 1, {2, 3, . . . , k + 1} ), for all integers n and k with 0 ≤ k < n. Observe that S(n, a, U ) ∼ = S(n, card U ), for each a ∈ [n] and each U ⊆ [n] \ {a}. Furthermore, it follows from roposition 9.7 that S(n, a, U ) ∼ = S(n, a, [n] \ (U ∪ {a}) ), hence S(n, k) ∼ = S(n, n -1 -k), and hence the factors of the minimal subdirect product decomposition (9.1) of Bip(n) are exactly the lattices S(n, k) where n > 0 and 0 ≤ 2k < n. The lattices S(3, 0) and S(3, 1) are represented on the left hand side and the right hand side of Figure 9.1, respectively.

Figure 9 . 1 .

 91 Figure 9.1. The bipartition-Cambrian lattices S(3, 0) and S(3, 1)

  3 does not not extend to the case n = 2, as it can easily be seen from the Hasse diagram of Bip(2) in Figure 7.2. Proof of Lemma 10.3. Let x = X ε1 1 ⊕• • •⊕X εm m (cf. Section 9) and set n i = card X i , for each i ∈ [m]. If x = ∅, then the upper covers of x are the U , for U ∈ Pow * [n] (cf. Lemma 8.2) and we are done. The case where x = 1 follows from applying the dual automorphism x → x c .

  [n]) and by Q the set of all nonzero elements of Bip(n) containing exactly one atom. The clepsydras ãx and bx defined by ãx = [n] × {x} = {x} c ⊕ {x} = x, ∅ and bx = {x} × [n] = {x} ⊕ {x} c = x, [n] , for x ∈ [n], all belong to Q, with respective lower covers a x = {x} c ×{x} = {x} c ⊕{x} = {x} and b x = {x}×{x} c = {x}⊕{x} c = {x} c . Lemma 10.5.

Lemma 10 . 6 .

 106 Let I ⊆ [n]. Then i∈I a i ⊆ i∈I ãi = [n] × I and i∈I b i ⊆ i∈I bi = I × [n]

Lemma 10 . 8 .

 108 Let k ∈ [n] and let I and J be disjoint subsets of[n]. Then a k ⊆ i∈I a i ∨ j∈J b j iff a k ⊆ i∈I ãi ∨ j∈J bj , iff either k ∈ I or {k} c ⊆ J.Proof. If {k} c ⊆ J, then, since n ≥ 3 and byLemma 10.6,

  It follows from Lemma 10.10 that for every U ∈ Pow * [n], there exists g(U ) ∈ Pow * [n] such that g(U ) ⊆ f ( U ). Lemma 10.11. The map g is a permutation of Pow * [n].

  and thus, by Lemma 10.10, 1 = U ∨ U ′ . By Lemma 10.4 again, it follows that U ′ = U c . Lemma 10.14. Let m be a positive integer, let x

Lemma 10 . 15 .

 1015 Let U ∈ Pow * [n]. If either g(U ) or g(U ) c is a singleton, then either U or U c is a singleton.

. 1 )

 1 The first entries of the sequence of numbers M (n) are M (1) = 2; M (2) = 10; M (3) = 74 ; M (4) = 730 ; M (5) = 9,002 ; M (6) = 133,210 .

K( 1 )

 1 = 1 ; K(2) = 4 ; K(3) = 20 ; K(4) = 138 ; K(5) = 1,182 ; K(6) = 12,166 .Finally, we can compute the cardinalities of the lattices S(n, k) as follows:S(n, k) = K(n) + K(n -1 -k) • K(k) .(11.3) Indeed, recalling that S(n, k) = S(n, 1, {2, 3, . . . , k + 1} , if a bipartition x ∈ S(n, k) has an underlined singleton block, then this block is {1}, and furthermore, both {1} × [2, k + 1] and [k + 2, n] × {1} are contained in x; thus, besides all the bipartitions with no underlined singleton block (i.e., the elements of K(n)), we must count the bipartitions whose ordered bipartition representation has the form (π 1 , {1} +1 , π 2 ), where π 1 represents a bipartition on [k + 2, n], π 2 represents a bipartition on [2, k + 1], and neither π 1 nor π 2 have any underlined singleton block. For small values of n, the orders of the lattices S(n, k) are the following: S(1, 0) = 2 . S(2, 0) = 5 . S(3, 0) = 24 ; S(3, 1) = 21 . S(4, 0) = 158 ; S(4, 1) = 142 . S(5, 0) = 1,320 ; S(5, 1) = 1,202 ; S(5, 2) = 1,198 . S(6, 0) = 13,348 ; S(6, 1) = 12,304 ; S(6, 2) = 12,246 .

Acknowledgment

The authors are grateful to the referees of the paper for their careful reading and comments. Special thanks are due to the first referee, who went much beyond the call of duty, suggesting various improvements to the paper, most notably to Lemma 9.6, Proposition 9.7, and Section 11. The authors are grateful to William McCune for his amazing Prover9-Mace4 program [23], to Ralph Freese for his lattice drawing program [15], and to the authors of the Graphviz framework, available online at http://www.graphviz.org/. Part of this work was completed while the second author was visiting the CIRM in March 2012. Excellent conditions provided by the host institution are greatly appreciated.


Matthieu Denoual

Sylvain Lebargy

Gilles Allègre

Digital implementation of the capacitively coupled electrical substitution for resistive bolometers