Meet decompositions in complete lattices

In the present paper we shall study infinite meet decompositions of an element of a complete lattice. We give here a generalization of some results of papers [2] and [3].     

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.     

Bigeneration in complete lattices and principal separation in ordered sets

By a recent observation of Monjardet and Wille, a finite distributive lattice is generated by its doubly irreducible elements iff the poset of all join-irreducible elements has a distributive MacNeille completion. This fact is generalized in several directions, by dropping the finiteness condition and considering various types of bigeneration via arbitrary meets and certain distinguished joins. This leads to a deeper investigation of so-called L-generators resp. C-subbases, translating well-known notions of topology to order theory. A strong relationship is established between bigeneration by (minimal) L-generators and so-called principal separation, which is defined in order-theoretical terms but may be regarded as a strong topological separation axiom. For suitable L, the complete lattices with a smallest join-dense L-subbasis consisting of L-primes are the L-completions of principally separated posets.     

On the nonexistence of free complete distributive lattices

We prove that there is no free object over a countable set in the category of complete distributive lattices with homomorphisms preserving binary meets and arbitrary joins.     

Cancellative residuated lattices

Cancellative residuated lattices are natural generalizations of lattice-ordered groups ( -groups). Although cancellative monoids are defined by quasi-equations, the class of cancellative residuated lattices is a variety. We prove that there are only two commutative subvarieties of that cover the trivial variety, namely the varieties generated by the integers and the negative integers (with zero). We also construct examples showing that in contrast to -groups, the lattice reducts of cancellative residuated lattices need not be distributive. In fact we prove that every lattice can be embedded in the lattice reduct of a cancellative residuated lattice. Moreover, we show that there exists an order-preserving injection of the lattice of all lattice varieties into the subvariety lattice of .We define generalized MV-algebras and generalized BL-algebras and prove that the cancellative integral members of these varieties are precisely the negative cones of -groups, hence the latter form a variety, denoted by . Furthermore we prove that the map that sends a subvariety of -groups to the corresponding class of negative cones is a lattice isomorphism from the lattice of subvarieties of to the lattice of subvarieties of . Finally, we show how to translate equational bases between corresponding subvarieties, and briefly discuss these results in the context of R. McKenzies characterization of categorically equivalent varieties.     

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.     

Orthomodular lattices and permutable congruences

If a variety of ortholattices is congruence-permutable, then we prove that it is a variety of orthomodular lattices.Dedicated to the memory of Ivan RivalReceived October 7, 2003; accepted in final form July 12, 2004.This revised version was published online in August 2005 with a corrected cover date.     

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.     

On context patterns associated with concept lattices

In this paper, we consider the following reconstruction problem: Given two ordered sets (G, ) and (M, ) representing join- and meet-irreducible elements, respectively together with three relationsJ,, onG×M modelling comparability (gm) and maximal noncomparability with respect tog (gm, butgm*) and with respect tom (gm, butgm*). We determine necessary and sufficient conditions for the existence of a finite latticeL and injections :GJ(L) and :MM(L) such that the given order relations and the abstract relations coincide with the one induced by the latticeL.     

Sublattices of product spaces: Hulls, representations and counting

The Cartesian product of lattices is a lattice, called a product space, with componentwise meet and join operations. A sublattice of a lattice L is a subset closed for the join and meet operations of L. The sublattice hullLQ of a subset Q of a lattice is the smallest sublattice containing Q. We consider two types of representations of sublattices and sublattice hulls in product spaces: representation by projections and representation with proper boundary epigraphs. We give sufficient conditions, on the dimension of the product space and/or on the sublattice hull of a subset Q, for LQ to be entirely defined by the sublattice hulls of the two-dimensional projections of Q. This extends results of Topkis (1978) and of Veinott [Representation of general and polyhedral subsemilattices and sublattices of product spaces, Linear Algebra Appl. 114/115 (1989) 681-704]. We give similar sufficient conditions for the sublattice hull LQ to be representable using the epigraphs of certain isotone (i.e., nondecreasing) functions defined on the one-dimensional projections of Q. This also extends results of Topkis and Veinott. Using this representation we show that LQ is convex when Q is a convex subset in a vector lattice (Riesz space), and is a polyhedron when Q is a polyhedron in Rⁿ.We consider in greater detail the case of a finite product of finite chains (i.e., totally ordered sets). We use the representation with proper boundary epigraphs and provide upper and lower bounds on the number of sublattices, giving a partial answer to a problem posed by Birkhoff in 1937. These bounds are close to each other in a logarithmic sense. We define a corner representation of isotone functions and use it in conjunction with the representation with proper boundary epigraphs to define an encoding of sublattices. We show that this encoding is optimal (up to a constant factor) in terms of memory space. We also consider the sublattice hull membership problem of deciding whether a given point is in the sublattice hull LQ of a given subset Q. We present a good characterization and a polynomial time algorithm for this sublattice hull membership problem. We construct in polynomial time a data structure for the representation with proper boundary epigraphs, such that sublattice hull membership queries may be answered in time logarithmic in the size |Q| of the given subset.     

Self-dual bases for varieties of orthomodular lattices

For any finitely based variety of orthomodular lattices, we determine the sizes of all equational bases that are both irredundant and self-dual.     

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.     

The complexity of cover graph recognition for some varieties of finite lattices

We address the following decision problem: Instance: an undirected graphG. Problem: IsG a cover graph of a lattice? We prove that this problem is NP-complete. This extends results of Brightwell [5] and Ne?et?il and Rödl [12]. On the other hand, it follows from Alvarez theorem [2] that recognizing cover graphs of modular or distributive lattices is in P. An important tool in the proof of the first result is the following statement which may be of independent interest: Given an integerl, l?3, there exists an algorithm which for a graphG withn vertices yields, in time polynomial inn, a graphH with the number of vertices polynomial inn, and satisfying girth(H)?l and χ(H)=χ(G).     

Counting formulas for glued lattices

A tolerance relation of a lattice L, i.e., a reflexive and symmetric relation of L which is compatible with join and meet, is called glued if covering blocks of have nonempty intersection. For a lattice L with a glued tolerance relation we prove a formula counting the number of elements of L with exactly k lower (upper) covers. Moreover, we prove similar formulas for incidence structures and graphs and we give a new proof of Dilworth's covering theorem.     

Lattices of algebraic subsets

This survey article tackles different aspects of lattices of algebraic subsets, with the emphasis on the following: the theory of quasivarieties, general lattice theory and the theory of closure spaces with the anti-exchange axiom.In Celebration of the Sixtieth Birthday of Ralph N. McKenzieReceived August 24, 2002; accepted in final form October 2, 2003.     

Tensorial decomposition of concept lattices

A tensor product for complete lattices is studied via concept lattices. A characterization as a universal solution and an ideal representation of the tensor products are given. In a large class of concept lattices which contains all finite ones, the subdirect decompositions of a tensor product can be determined by the subdirect decompositions of its factors. As a consequence, one obtains that the tensor product of completely subdirectly irreducible concept lattices of this class is again completely subdirectly irreducible. Finally, applications to conceptual measurement are discussed.Dedicated to Ernst-August Behrens on the occasion of his seventieth birthday.     

Orthmodular lattices whose MacNeille completions are not orthomodular

The only known example of an orthomodular lattice (abbreviated: OML) whose MacNeille completion is not an OML has been noted independently by several authors, see Adams [1], and is based on a theorem of Ameniya and Araki [2]. This theorem states that for an inner product space V, if we consider the ortholattice ?(V,⊥) = {A \( \subseteq \) V: A = A ^⊥⊥} where A ^⊥ is the set of elements orthogonal to A, then ?(V,⊥) is an OML if and only if V is complete. Taking the orthomodular lattice L of finite or confinite dimensional subspaces of an incomplete inner product space V, the ortholattice ?(V,⊥) is a MacNeille completion of L which is not orthomodular. This does not answer the longstanding question Can every OML be embedded into a complete OML? as L can be embedded into the complete OML ?(V,⊥), where V is the completion of the inner product space V. Although the power of the Ameniya-Araki theorem makes the preceding example elegant to present, the ability to picture the situation is lost. In this paper, I present a simpler method to construct OMLs whose Macneille completions are not orthomodular. No use is made of the Ameniya-Araki theorem. Instead, this method is based on a construction introduced by Kalmbach [7] in which the Boolean algebras generated by the chains of a lattice are glued together to form an OML. A simple method to complete these OMLs is also given. The final section of this paper briefly covers some elementary properties of the Kalmbach construction. I have included this section because I feel that this construction may be quite useful for many purposes and virtually no literature has been written on it.     

When do abstract bases generate continuous lattices and L-domains

In this note, the new concepts of C-bases (resp., BC-bases, L-bases) which are special kinds of abstract bases are introduced. It is proved that the round ideal completion of a C-basis (resp., BC-basis, L-basis) is a continuous lattice (resp., bc-domain, L-domain). Furthermore, representation theorems of continuous lattices (resp., bc-domains, L-domains) by means of the round ideal completions of C-bases (resp., BC-bases, L-bases) are obtained. Supported by the NSF of China (10371106, 60774073) and by the Fund (S0667-082) from Nanjing University of Aeronautics and Astronautics.