Join-semidistributive lattices and convex geometries

We introduce the notion of a convex geometry extending the notion of a finite closure system with the anti-exchange property known in combinatorics. This notion becomes essential for the different embedding results in the class of join-semidistributive lattices. In particular, we prove that every finite join-semidistributive lattice can be embedded into a lattice S_P(A) of algebraic subsets of a suitable algebraic lattice A. This latter construction, S_P(A), is a key example of a convex geometry that plays an analogous role in hierarchy of join-semidistributive lattices as a lattice of equivalence relations does in the class of modular lattices. We give numerous examples of convex geometries that emerge in different branches of mathematics from geometry to graph theory. We also discuss the introduced notion of a strong convex geometry that might promise the development of rich structural theory of convex geometries.     

Embedding Finite Lattices into Finite Biatomic Lattices

For a class C of finite lattices, the question arises whether any lattice in C can be embedded into some atomistic, biatomic lattice in C. We provide answers to the question above for C being, respectively,– the class of all finite lattices;– the class of all finite lower bounded lattices (solved by the first author's earlier work);– the class of all finite join-semidistributive lattices (this problem was, until now, open).We solve the latter problem by finding a quasi-identity valid in all finite, atomistic, biatomic, join-semidistributive lattices but not in all finite join-semidistributive lattices.     

Primes,irreducibles and extremal lattices

This paper studies certain types of join and meet-irreducibles called coprimes and primes. These elements can be used to characterize certain types of lattices. For example, a lattice is distributive if and only if every join-irreducible is coprime. Similarly, a lattice is meet-pseudocomplemented if and only if each atom is coprime. Furthermore, these elements naturally decompose lattices into sublattices so that often properties of the original lattice can be deduced from properties of the sublattice. Not every lattice has primes and coprimes. This paper shows that lattices which are long enough must have primes and coprimes and that these elements and the resulting decompositions can be used to study such lattices.The length of every finite lattice is bounded above by the minimum of the number of meet-irreducibles (meet-rank) and the number of join-irreducibles (join-rank) that it has. This paper studies lattices for which length=join-rank or length=meet-rank. These are called p-extremal lattices and they have interesting decompositions and properties. For example, ranked, p-extremal lattices are either lower locally distributive (join-rank=length), upper locally distributive (meet-rank=length) or distributive (join-rank=meet-rank=length). In the absence of the Jordan-Dedekind chain condition, p-extremal lattices still have many interesting properties. Of special interest are the lattices that satisfy both equalities. Such lattices are called extremal; this class includes distributive lattices and the associativity lattices of Tamari. Even though they have interesting decompositions, extremal lattices cannot be characterized algebraically since any finite lattice can be embedded as a subinterval into an extremal lattice. This paper shows how prime and coprime elements, and the poset of irreducibles can be used to analyze p-extremal and other types of lattices.The results presented in this paper are used to deduce many key properties of the Tamari lattices. These lattices behave much like distributive lattices even though they violate the Jordan-Dedekind chain condition very strongly having maximal chains that vary in length from N-1 to N(N-1)/2 where N is a parameter used in the construction of these lattices.     

Reflections on lower bounded lattices

Lattices in the variety of lower bounded lattices of rank k are characterized. A sufficient condition for a lattice to be lower bounded is given, and used to produce a new example of a non-finitely-generated lower bounded lattice. Lattices that are subdirect products of finite lower bounded lattices are characterized.In memory of Ivan RivalReceived September 18, 2003; accepted in final form October 5, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Matchings and radon transforms in lattices. I. Consistent lattices

An element in a lattice is join-irreducible if x=ab implies x=a or x=b. A meet-irreducible is a join-irreducible in the order dual. A lattice is consistent if for every element x and every join-irreducible j, the element xj is a join-irreducible in the upper interval [x, î]. We prove that in a finite consistent lattice, the incidence matrix of meet-irreducibles versus join-irreducibles has rank the number of join-irreducibles. Since modular lattices and their order duals are consistent, this settles a conjecture of Rival on matchings in modular lattices.     

Comparability graphs of lattices

A theorem of N. Terai and T. Hibi for finite distributive lattices and a theorem of Hibi for finite modular lattices (suggested by R.P. Stanley) are equivalent to the following: if a finite distributive or modular lattice of rank d contains a complemented rank 3 interval, then the lattice is (d+1)-connected.In this paper, the following generalization is proved: Let L be a (finite or infinite) semimodular lattice of rank d that is not a chain (d∈N₀). Then the comparability graph of L is (d+1)-connected if and only if L has no simplicial elements, where z∈L is simplicial if the elements comparable to z form a chain.     

Many varieties of lattices with nonsurjective epimorphisms

We use dominions to show that many varieties of lattices have nonsurjective epimorphisms. The variety D of distributive lattices is treated in detail. We show that the dominion in D of a sublattice is the closure of M under relative complementation in L. This dominion is also the largest sublattice of L in which M is epimorphically embedded. In any variety of lattices larger than D, the dominion of M in L is just M. Received May 1, 2001; accepted in final form October 4, 2005.     

Priestley duality for order-preserving maps into distributive lattices

The category of bounded distributive lattices with order-preserving maps is shown to be dually equivalent to the category of Priestley spaces with Priestley multirelations. The Priestley dual space of the ideal lattice L of a bounded distributive lattice L is described in terms of the dual space of L. A variant of the Nachbin-Stone-ech compactification is developed for bitopological and ordered spaces. Let X be a poset and Y an ordered space; X ^Y denotes the poset of continuous order-preserving maps from Y to X with the discrete topology. The Priestley dual of L ^P is determined, where P is a poset and L a bounded distributive lattice.     

Reducible classes of finite lattices

In this paper we study a notion of reducibility in finite lattices. An element x of a (finite) lattice L satisfying certain properties is deletable if L-x is a lattice satisfying the same properties. A class of lattices is reducible if each lattice of this class admits (at least) one deletable element (equivalently if one can go from any lattice in this class to the trivial lattice by a sequence of lattices of the class obtained by deleting one element in each step). First we characterize the deletable elements in a pseudocomplemented lattice what allows to prove that the class of pseudocomplemented lattices is reducible. Then we characterize the deletable elements in semimodular, modular and distributive lattices what allows to prove that the classes of semimodular and locally distributive lattices are reducible. In conclusion the notion of reducibility for a class of lattices is compared with some other notions like the notion of order variety.     

Lifting retracted diagrams with respect to projectable functors

We prove a general categorical theorem that enables us to state that under certain conditions, the range of a functor is large. As an application, we prove various results of which the following is a prototype: If every diagram, indexed by a lattice, of finite Boolean 〈∨ ,0 〉-semilattices with 〈∨ ,0 〉-embeddings, can be lifted, with respect to the Con_c functor, by a diagram of lattices, then so can every diagram, indexed by a lattice, of finite distributive 〈∨ ,0 〉-semilattices with 〈∨ ,0 〉-embeddings. If the premise of this statement held, this would solve in turn the (still open) problem whether every distributive algebraic lattice is isomorphic to the congruence lattice of a lattice. We also outline potential applications of our method to other functors, such as the functor on von Neumann regular rings. Received August 12, 2004; accepted in final form June 6, 2005.     

Largest extension of a finite convex geometry

We present a new embedding of a finite join-semidistributive lattice into a finite atomistic join-semidistributive lattice. This embedding turns out to be the largest extension, when applied to a finite convex geometry.In Celebration of the Sixtieth Birthday of Ralph N. McKenzieReceived September 18, 2002; accepted in final form September 29, 2003.     

Remarks on Priestley duality for distributive lattices

The notion of a Priestley relation between Priestley spaces is introduced, and it is shown that there is a duality between the category of bounded distributive lattices and 0-preserving join-homomorphisms and the category of Priestley spaces and Priestley relations. When restricted to the category of bounded distributive lattices and 0-1-preserving homomorphisms, this duality yields essentially Priestley duality, and when restricted to the subcategory of Boolean algebras and 0-preserving join-homomorphisms, it coincides with the Halmos-Wright duality. It is also established a duality between 0-1-sublattices of a bounded distributive lattice and certain preorder relations on its Priestley space, which are called lattice preorders. This duality is a natural generalization of the Boolean case, and is strongly related to one considered by M. E. Adams. Connections between both kinds of dualities are studied, obtaining dualities for closure operators and quantifiers. Some results on the existence of homomorphisms lying between meet and join homomorphisms are given in the Appendix.     

Varieties generated by lattices of breadth two

Some relations between the classB of lattices of breadth at most two and its subclassD of dismantlable lattices, as well as the lattice varietiesV (B) andV (D) generated byV (D) andV (D), respectively, are studied in this paper. For finite join-semidistributive lattices, the two concepts of dismantlability and breadth at most two coincide. There are infinitely many lattice varieties between the varietiesV (D) andV (B), none of them is finitely based.     

Varieties of Lattices with Geometric Descriptions

A lattice L is spatial if every element of L is a join of completely join-irreducible elements of L (points), and strongly spatial if it is spatial and the minimal coverings of completely join-irreducible elements are well-behaved. Herrmann et al. proved in 1994 that every modular lattice can be embedded, within its variety, into an algebraic and spatial lattice. We extend this result to n-distributive lattices, for fixed n. We deduce that the variety of all n-distributive lattices is generated by its finite members, thus it has a decidable word problem for free lattices. This solves two problems stated by Huhn in 1985. We prove that every modular (resp., n-distributive) lattice embeds within its variety into some strongly spatial lattice. Every lattice which is either algebraic modular spatial or bi-algebraic is strongly spatial. We also construct a lattice that cannot be embedded, within its variety, into any algebraic and spatial lattice. This lattice has a least and a largest element, and it generates a locally finite variety of join-semidistributive lattices.     

Generalizations of Boolean products for lattice-ordered algebras

It is shown that the Boolean center of complemented elements in a bounded integral residuated lattice characterizes direct decompositions. Generalizing both Boolean products and poset sums of residuated lattices, the concepts of poset product, Priestley product and Esakia product of algebras are defined and used to prove decomposition theorems for various ordered algebras. In particular, we show that FL_w-algebras decompose as a poset product over any finite set of join irreducible strongly central elements, and that bounded n-potent GBL-algebras are represented as Esakia products of simple n-potent MV-algebras.     

Lattices isomorphic with their free powers

For any N3 there exists a lattice L isomorphic with NL (the free product of its own N copies) but not isomorphic with kL for any k–2,...,N-1.     

Intervals in lattices of quasiorders

We investigate the structure of intervals in the lattice of all closed quasiorders on a compact or discrete space. As a first step, we show that if the intervalI has no infinite chains then the underlying space may be assumed to be finite, and in particular,I must be finite, too. We compute several upper bounds for its size in terms of its heighth, which in turn can be computed easily by means of the least and the greatest element ofI. The cover degreec of the interval (i.e. the maximal number of atoms in a subinterval) is less than 4h. Moreover, ifc4(n–1) thenI contains a Boolean subinterval of size 2 ⁿ , and ifI is geometric then it is already a finite Boolean lattice. While every finite distributive lattice is isomorphic to some interval of quasiorders, we show that a nondistributive finite interval of quasiorders is neither a vertical sum nor a horizontal sum of two lattices, with exception of the pentagon. Many further lattices are excluded from the class of intervals of quasiorders by the fact that no join-irreducible element of such an interval can have two incomparable join-irreducible complements. Up to isomorphism, we determine all quasiorder intervals with less than 9 elements and all quasiorder intervals with two complementary atoms or coatoms.     

Non-representable distributive semilattices

We present two examples of distributive algebraic lattices which are not isomorphic to the congruence lattice of any lattice. The first such example was discovered by F. Wehrung in 2005. One of our examples is defined topologically, the other one involves majority algebras. In particular, we prove that the congruence lattice of the free majority algebra on (at least) ℵ₂ generators is not isomorphic to the congruence lattice of any lattice. Our method is a generalization of Wehrung’s approach, so that we are able to apply it to a larger class of distributive semilattices.     

Finite modular congruence lattices

We consider the variety of modular lattices generated by all finite lattices obtained by gluing together some M₃’s. We prove that every finite lattice in this variety is the congruence lattice of a suitable finite algebra (in fact, of an operator group). Received February 26, 2004; accepted in final form December 16, 2004.     

On lattices of convex sets in {\mathbb{R}}^{n}

Properties of several sorts of lattices of convex subsets of are examined. The lattice of convex sets containing the origin turns out, for n > 1, to satisfy a set of identities strictly between those of the lattice of all convex subsets of and the lattice of all convex subsets of The lattices of arbitrary, of open bounded, and of compact convex sets in all satisfy the same identities, but the last of these is join-semidistributive, while for n > 1 the first two are not. The lattice of relatively convex subsets of a fixed set satisfies some, but in general not all of the identities of the lattice of “genuine” convex subsets of To the memory of Ivan RivalReceived April 22, 2003; accepted in final form February 16, 2005.This revised version was published online in August 2005 with a corrected cover date.