Über Morphismen halbmodularer Verbände

Morphisms and weak morphisms extend the concept of strong maps and maps of combinatorial geometry to the class of finite dimensional semimodular lattices. Each lattice which is the image of a semimodular lattice under a morphism is semimodular. In particular, each finite lattice is semimodular if and only if it is the image of a finite distributive lattice under a morphism. Regular and non-singular weak morphisms may be used to characterize modular and distributive lattices. Each morphism gives rise to a geometric closure operator which in turn determines a quotient of a semimodular lattice. A special quotient, the Higgs lift, is constructed and used to show that each morphism decomposes into elementary morphisms, and that each morphism may be factored into an injection and a contraction.

     

Reducibility number

Let P be a poset in a class of posets P. A smallest positive integer r is called reducibility number of P with respect to P if there exists a non-empty subset S of P with |S|=r and P-S∈P. The reducibility numbers for the power set 2ⁿ of an n-set (n?2) with respect to the classes of distributive lattices, modular lattices and Boolean lattices are calculated. Also, it is shown that the reducibility number r of the lattice of all subgroups of a finite group G with respect to the class of all distributive lattices is 1 if and only if the order of G has at most two distinct prime divisors; further if r is a prime number then order of G is divisible by exactly three distinct primes. The class of pseudo-complemented u-posets is shown to be reducible. Deletable elements in semidistributive posets are characterized.     

On Pseudocomplemented and Stone Ordered Sets

The aim of this paper is to characterize both the pseudocomplemented and Stone ordered sets in a manner similar to that used previously for Boolean and distributive ordered sets. The sublattice G(A) of the Dedekind–Mac Neille completion DM(A) of an ordered set A generated by A is said to be the characteristic lattice of A. We will show that there are distributive pseudocomplemented ordered sets whose characteristic lattices are not pseudocomplemented. We can define a stronger notion of pseudocomplementedness by demanding that both A and G(A) be pseudocomplemented. It turns out that the two concepts are the same for finite and Stone ordered sets.     

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.     

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.     

Finite distributive lattices are congruence lattices of almost-geometric lattices

A semimodular lattice L of finite length will be called an almost-geometric lattice if the order J(L) of its nonzero join-irreducible elements is a cardinal sum of at most two-element chains. We prove that each finite distributive lattice is isomorphic to the lattice of congruences of a finite almost-geometric lattice.     

Simplicial elimination schemes,extremal lattices and maximal antichain lattices

Fix a partial order P=(X, <). We first show that bipartite orders are sufficient to study structural properties of the lattice of maximal antichains. We show that all orders having the same lattice of maximal antichains can be reduced to one representative order (called the poset of irreducibles by Markowsky [14]). We then define the strong simplicial elimination scheme to characterize orders which have distributive lattice of maximal antichains. The notion of simplicial elimination corresponds to the decomposition process described in [14] for extremal lattices. This notion leads to simple greedy algorithms for distributivity checking, lattice recognition and jump number computation. In the last section, we give several algorithms for lattices and orders.     

Representing homomorphisms of distributive lattices as restrictions of congruences of rectangular lattices

Let be a {0, 1}-homomorphism of a finite distributive lattice D into the congruence lattice Con L of a rectangular (whence finite, planar, and semimodular) lattice L. We prove that L is a filter of an appropriate rectangular lattice K such that ConK is isomorphic with D and is represented by the restriction map from Con K to Con L. The particular case where is an embedding was proved by E.T. Schmidt. Our result implies that each {0, 1}-lattice homomorphism between two finite distributive lattices can be represented by the restriction of congruences of an appropriate rectangular lattice to a rectangular filter.     

A cover-preserving embedding of semimodular lattices into geometric lattices

Extending former results by G. Grätzer and E.W. Kiss (1986) [5] and M. Wild (1993) [9] on finite (upper) semimodular lattices, we prove that each semimodular lattice L of finite length has a cover-preserving embedding into a geometric lattice G of the same length. The number of atoms of our G equals the number of join-irreducible elements of L.     

The lattice of strict completions of a finite poset

For a given finite poset , we construct strict completions of P which are models of all finite lattices L such that the set of join-irreducible elements of L is isomorphic to P. This family of lattices, , turns out to be itself a lattice, which is lower bounded and lower semimodular. We determine the join-irreducible elements of this lattice. We relate properties of the lattice to properties of our given poset P, and in particular we characterize the posets P for which . Finally we study the case where is distributive. Received October 13, 2000; accepted in final form June 13, 2001.     

A note on congruence lattices of slim semimodular lattices

Recently, G. Grätzer has raised an interesting problem: Which distributive lattices are congruence lattices of slim semimodular lattices? We give an eight element slim distributive lattice that cannot be represented as the congruence lattice of a slim semimodular lattice. Our lattice demonstrates the difficulty of the problem.     

A construction of semimodular lattices

In this paper we prove that if is a finite lattice, and r is an integral valued function on satisfying some very natural conditions, then there exists a finite geometric (that is, semimodular and atomistic) lattice I containing as a sublattice such that r is the height function of restricted to . Moreover, we show that if, for all intervals [e, f] of , semimodular lattices I, of length at most r(f)-r(e) are given, then I can be chosen to contain I in its interval [e, f] as a cover preserving {0}-sublattice. As applications, we obtain results of R. P. Dilworth and D. T. Finkbeiner.     

The semilattice tensor product of projective distributive lattices

Grant A. Fraser defined the semilattice tensor productA ⊗B of distributive latticesA, B and showed that it is a distributive lattice. He proved that ifA ⊗B is projective then so areA andB, that ifA andB are finite and projective thenA ⊗B is projective, and he gave two infinite projective distributive lattices whose semilattice tensor product is not projective. We extend these results by proving that ifA andB are distributive lattices with more than one element thenA ⊗B is projective if and only if bothA andB are projective and both have a greatest element. Presented by W. Taylor.     

Sublattices of complete lattices with continuity conditions

Various embedding problems of lattices into complete lattices are solved. We prove that for any join-semilattice S with the minimal join-cover refinement property, the ideal lattice Id S of S is both algebraic and dually algebraic. Furthermore, if there are no infinite D-sequences in J(S), then Id S can be embedded into a direct product of finite lower bounded lattices. We also find a system of infinitary identities that characterize sublattices of complete, lower continuous, and join-semidistributive lattices. These conditions are satisfied by any (not necessarily finitely generated) lower bounded lattice and by any locally finite, join-semidistributive lattice. Furthermore, they imply M. Erné’s dual staircase distributivity.On the other hand, we prove that the subspace lattice of any infinite-dimensional vector space cannot be embedded into any ℵ₀-complete, ℵ₀-upper continuous, and ℵ₀-lower continuous lattice. A similar result holds for the lattice of all order-convex subsets of any infinite chain.Dedicated to the memory of Ivan RivalReceived April 4, 2003; accepted in final form June 16, 2004.This revised version was published online in August 2005 with a corrected cover date.     

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.     

Finite lattices and congruences. A survey

In the early forties, R.P. Dilworth proved his famous result: Every finite distributive lattice D can be represented as the congruence lattice of a finite lattice L. In one of our early papers, we presented the first published proof of this result; in fact we proved: Every finite distributive lattice D can be represented as the congruence lattice of a finite sectionally complemented lattice L.We have been publishing papers on this topic for 45 years. In this survey paper, we are going to review some of our results and a host of related results by others: Making L nice.If being nice is an algebraic property such as being semimodular or sectionally complemented, then we have tried in many instances to prove a stronger form of these results by verifying that every finite lattice has a congruence-preserving extension that is nice. We shall discuss some of the techniques we use to construct nice lattices and congruence-preserving extensions.We shall describe some results on the spectrum of a congruence of a finite sectionally complemented lattice, measuring the sizes of the congruence classes. It turns out that with very few restrictions, these can be as bad as we wish.We shall also review some results on simultaneous representation of two distributive lattices. We conclude with the magic wand construction, which holds out the promise of obtaining results that go beyond what can be achieved with the older techniques.In Celebration of the Sixtieth Birthday of Ralph N. McKenzieReceived November 26, 2002; accepted in final form June 18, 2004.     

Distributive Lattices with a Generalized Implication: Topological Duality

In this paper we introduce the notion of generalized implication for lattices, as a binary function ⇒ that maps every pair of elements of a lattice to an ideal. We prove that a bounded lattice A is distributive if and only if there exists a generalized implication ⇒ defined in A satisfying certain conditions, and we study the class of bounded distributive lattices A endowed with a generalized implication as a common abstraction of the notions of annihilator (Mandelker, Duke Math J 37:377–386, 1970), Quasi-modal algebras (Celani, Math Bohem 126:721–736, 2001), and weakly Heyting algebras (Celani and Jansana, Math Log Q 51:219–246, 2005). We introduce the suitable notions of morphisms in order to obtain a category, as well as the corresponding notion of congruence. We develop a Priestley style topological duality for the bounded distributive lattices with a generalized implication. This duality generalizes the duality given in Celani and Jansana (Math Log Q 51:219–246, 2005) for weakly Heyting algebras and the duality given in Celani (Math Bohem 126:721–736, 2001) for Quasi-modal algebras.     

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 the number of join-irreducibles in a congruence representation of a finite distributive lattice

For a finite lattice L, let $ \trianglelefteq_L $ denote the reflexive and transitive closure of the join-dependency relation on L, defined on the set J(L) of all join-irreducible elements of L. We characterize the relations of the form $ \trianglelefteq_L $, as follows: Theorem. Let $ \trianglelefteq $ be a quasi-ordering on a finite set P. Then the following conditions are equivalent:(i) There exists a finite lattice L such that $ \langle J(L), \trianglelefteq_L $ is isomorphic to the quasi-ordered set $ \langle P, \trianglelefteq \rangle $.(ii) $ |\{x\in P|p \trianglelefteq x\}| \neq 2 $, for any $ p \in P $.For a finite lattice L, let $ \mathrm{je}(L) = |J(L)|-|J(\mathrm{Con} L)| $ where Con L is the congruence lattice of L. It is well-known that the inequality $ \mathrm{je}(L) \geq 0 $ holds. For a finite distributive lattice D, let us define the join- excess function:$ \mathrm{JE}(D) =\mathrm{min(je} (L) | \mathrm{Con} L \cong D). $We provide a formula for computing the join-excess function of a finite distributive lattice D. This formula implies that $ \mathrm{JE}(D) \leq (2/3)| \mathrm{J}(D)|$ , for any finite distributive lattice D; the constant 2/3 is best possible.A special case of this formula gives a characterization of congruence lattices of finite lower bounded lattices.Dedicated to the memory of Gian-Carlo Rota     

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.