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.     

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.     

Transversally bounded lattices

A problem stemming from a boundedness question for torsion modules and its translation into ideal lattices is explored in the setting of abstract lattices. Call a complete lattice L transversally bounded (resp., uniformly transversally bounded) if for all families (X _i)_iIof nonempty subsets of L with the property that {x _iiI}<1 for all choices of x _iX _i, almost all of the sets X _ihave join smaller than 1 (resp., _jJ X _jhas join smaller than 1 for some cofinite subset J of I). It is shown that the lattices which are transversally bounded, but not uniformly so, correspond to certain ultrafilters with peculiar boundedness properties similar to those studied by Ramsey. The prototypical candidates of the two types of lattices which one is led to construct from ultrafilters (in particular the lattices arising from what will be called Ramsey systems) appear to be of interest beyond the questions at stake.     

Binary hyperidentities of lattices

Summary An equational identity of a given type involves two kinds of symbols: individual variables and the operation symbols. For example, the distributive identity: x (y + z) = x y + x z has three variable symbols {x, y, z} and two operation symbols {+, }. Here the variables range over all the elements of the base set while the two operation symbols are fixed. However, we shall say that an identity ishypersatisfied by a varietyV if, whenever we also allow the operation symbols to range over all polynomials of appropriate arity, the resulting identities are all satisfied byV in the usual sense. For example, the ring of integers Z; +, satisfies the above distributive law, but it does not hypersatisfy the same formal law because, e.g., the identityx + (y z) = (x + y) (x + z) is not valid. By contrast, is hypersatisfied by the variety of all distributive lattices and is thus referred to as a distributive latticehyperidentity. Thus a hyperidentity may be viewed as an equational scheme for writing a class of identities of a given type and the original identities themselves are obtained as special cases by substituting specific polynomials of appropriate arity for the operation symbols in the scheme. In this paper, we provide afinite equational scheme which is a basis for the set of all binary lattice hyperidentities of type 2, 2, .This research was supported by the NSERC operating grant # 8215     

Posets Generated by Irreducible Elements

Let J be a fixed partially ordered set (poset). Among all posets in which J is join-dense and consists of all completely join-irreducible elements, there is an up to isomorphism unique greatest one, the Alexandroff completion L. Moreover, the class of all such posets has a canonical set of representatives, C ₀ L, consisting of those sets between J and L which intersect each of the intervals I _j =[j ,j ] (jJ), where j and j denote the greatest element of L less than, respectively, not greater than j. The complete lattices in C ₀ L form a closure system C L, consisting of all Dedekind–MacNeille completions of posets in C ₀ L. We describe explicitly those L for which C ₀ L, respectively, C L is a (complete atomic) Boolean lattice, and similarly, those for which C L is distributive (or modular). Analogous results are obtained for C L, the closure system of all posets in C ₀ L that are closed under meets of less than elements (where is any cardinal number).     

A horn sentence for involution lattices of quasiorders

The quasiorders of a setA form a lattice Quord(A) with an involution ^–1={x, y: y, x}. Some results in [1] and Chajda and Pinus [2] lead to the problem whether every lattice with involution can be embedded in Quord(A) for some setA. Using the author's approach to the word problem of lattices (cf. [3]), which also applies for involution lattices, it is shown that the answer is negative.Research supported by the Hungarian National Foundation for Scientific Research (OTKA), under grant no. T 7442.     

On an isomorphism problem on the closed-set lattice of a graph

Let (G) and V(G) be, respectively, the closed-set lattice and the vertex set of a graph G. Any lattice isomorphism : V(G)(G) induces a bijection : V(G)V(G) such that for each x in V(G), (x)=x' in V(G') iff ({x})={x'}. A graph G is strongly sensitive if for any graph G' and any lattice isomorphism : (G)(G), the bijection induced by is a graph isomorphism of G onto G'. In this paper we present some sufficient conditions for graphs to be strongly sensitive and prove in particular that all C ₄-free graphs and all covering graphs of finite lattices are strongly sensitive.     

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.     

The order dimension of multinomial lattices

Using the notion of Ferrers dimension of incidence structures, the order dimension of multi-nomial lattices (i.e. lattices of multi-permutations) is determined. In particular, it is shown that the lattice of all permutations on ann-element set has dimensionn–1.     

Transversals of families in complete lattices,and torsion in product modules

Suppose L is a complete lattice containing no copy of the power-set 2 and no uncountable well-ordered chains. It is shown that for any family of nonempty subsets , one can choose elements p _i X _i so that _A p _i majorizes all elements of all but finitely many of the X _i . Ring-theoretic consequences are deduced: for instance, the direct product of a family of torsion modules over a commutative Noetherian integral domain R is torsion if and only if some element of R annihilates all but finitely many of the modules.     

A structural characterization of non-Arguesian lattices

This is the first of a planned series of papers on the structure of non-Arguesian modular lattices. Apart from the (subspace lattices of) non-Arguesian projective planes, the best known examples of such lattices are obtained via the Hall-Dilworth construction by badly gluing together two projective planes of the same order. Our principal result shows that every non-Arguesian modular lattice L retains some of the flavor of these examples: There exist in the ideal lattice of L 20 intervals, not necessarily distinct, that form non-degenerate projective plains, and 10 points and 10 lines in these planes that constitute in a natural sense a classical non-Arguesian configuration.Research supported by NSERC Operating Grant A8190.Research supported by NSF Grant DMS-8300107.     

Semimodular lattices with isomorphic graphs

Two discrete modular lattice and have isomorphic graphs if and only if is of the form A × and is of the form A × for some lattices A and and . We prove that for discrete semimodular lattices and this latter condition holds if and only if and have isomorphic graphs and the isomorphism preserves the order on all cover-preserving sublattices of which are isomorphic to the seven-element, semimodular, nonmodular lattice (see Figure 1). This answers in the affirmative a question posed by J. Jakubik.     

A geometric construction of the K-loop of a hyperbolic space

It is well known that the homogeneous orthochronous proper Lorentzgroup is isomorphic to the proper motion group of the hyperbolic space. To each Lorentz boost \ {id} there corresponds in the hyperbolic space exactly one lineL such that fixes each of the two ends ofL . Furthermore has no fixed points but each plane containingL is fixed by . If we fix a pointo, then to each other pointa there is exactly one boosta ⁺ such thatL _a+ is the line joiningo anda anda ⁺(o)=a. The set P of points of the hyperbolic space is turned in a K-loop (P, +) bya+b:=a ⁺(b). Each line of the hyperbolic space has the representationa+Z(b) wherea, b P,b 0 andZ(b):= {x P |x+b=b+x}.Dedicated to H. Salzmann on the occasion of his 65th birthdaySupported by the NATO Scientific Affairs Division grant CRG 900103.     

Hilbert lattices with the extension property

Separable Hilbert lattices are constructed that enjoy the following property: each ortho-isomorphism between arbitrary interval sublattices [0, a] and [0, b] of height at least 3 (a, b ) extends to an ortho-automorphism of the lattice #x2112.     

Identities of cofinal sublattices

If V is a variety of lattices and L a free lattice in V on uncountably many generators, then any cofinal sublattice of L generates all of V. On the other hand, any modular lattice without chains of order-type +1 has a cofinal distributive sublattice. More generally, if a modular lattice L has a distributive sublattice which is cofinal modulo intervals with ACC, this may be enlarged to a cofinal distributive sublattice. Examples are given showing that these existence results are sharp in several ways. Some similar results and questions on existence of cofinal sublattices with DCC are noted.This work was done while the first author was partly supported by NSF contract MCS 82-02632, and the second author by an NSF Graduate Fellowship.     

Some asymptotic results useful in enumeration problems

Suppose one is given two related generating functionsa(x) = a _n x ⁿ andb(x) = b _n x ⁿ , often it is of interest to determine the limiting behaviour of the quantitiesa _n /b _n We survey some earlier results of this nature and give some new ones     

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.     

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.     

Infinite intervals in free lattices

if u/v is any infinite interval in FL(X), the free lattice with generating set X, and then u/v contains a sublattice isomorphic to FL(Y). This result answers a question posed by Ralph Freese and J. B. Nation in their paper Covers in Free Lattices [2] and the principal techniques used in proving this result all come from that paper. The most difficult step in the argument is to show that there are incomparable elements in any infinite interval.     

Circle orders,N-gon orders and the crossing number

Let ={P ₁,...,P _m } be a family of sets. A partial order P(, <) on is naturally defined by the condition P _i <P _j iff P _i is contained in P _j . When the elements of are disks (i.e. circles together with their interiors), P(, <) is called a circle order; if the elements of are n-polygons, P(, <) is called an n-gon order. In this paper we study circle orders and n-gon orders. The crossing number of a partial order introduced in [5] is studied here. We show that for every n, there are partial orders with crossing number n. We prove next that the crossing number of circle orders is at most 2 and that the crossing number of n-gon orders is at most 2n. We then produce for every n4 partial orders of dimension n which are not circle orders. Also for every n>3, we prove that there are partial orders of dimension 2n+2 which are not n-gon orders. Finally, we prove that every partial order of dimension 2n is an n-gon order.This research was supported under Natural Sciences and Engineering Research Council of Canada (NSERC Canada) grant numbers A2507 and A0977.