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.     

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.     

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.     

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].     

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.     

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.     

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.     

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.     

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.     

Congruence lattices of function lattices

Thefunction lattice L ^P is the lattice of all isotone maps from a posetP into a latticeL.D. Duffus, B. Jónsson, and I. Rival proved in 1978 that for afinite poset P, the congruence lattice ofL ^P is a direct power of the congruence lattice ofL; the exponent is |P|.This result fails for infiniteP. However, utilizing a generalization of theL ^P construction, theL[D] construction (the extension ofL byD, whereD is a bounded distributive lattice), the second author proved in 1979 that ConL[D] is isomorphic to (ConL) [ConD] for afinite lattice L.In this paper we prove that the isomorphism ConL[D](ConL)[ConD] holds for a latticeL and a bounded distributive latticeD iff either ConL orD is finite.The research of the first author was supported by the NSERC of Canada.The research of the second author was supported by the Hungarian National Foundation for Scientific Research, under Grant No. 1903.     

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.     

Cover-preserving embedding of modular lattices

In this note we prove: If a subdirect product of finitely many finite projective geometries has the cover-preserving embedding property, then so does each factor.     

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.     

Cover-preserving order embeddings into Boolean lattices

It is not known which finite graphs occur as induced subgraphs of a hypercube. This is relevant in the theory of parallel computing. The ordered version of the problem is: Which finite posets P occur as cover-preserving subposets of a Boolean lattice? Our main Theorem gives (for 0,1-posets) a necessary and sufficient condition, which involves the chromatic number of a graph associated to P. It is applied respectively to upper balanced, meet extremal, meet semidistributive, and semidistributive lattices P. More specifically, we consider isometric embeddings of posets into Boolean lattices. In particular, answering a question of Ivan Rival to the positive, a nontrivial invariant for the covering graph of a poset is found.     

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     

Meet-regular intervals in lattices of finite length

Dedicated to Professor O. Krötenheerdt on the occasion of his sixtieth birthday     

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.     

The generalized Füredi conjecture holds for finite linear lattices

We say that a rank-unimodal poset P has rapidly decreasing rank numbers, or the RDR property, if above (resp. below) the largest ranks of P, the size of each level is at most half of the previous (resp. next) one. We show that a finite rank-unimodal, rank-symmetric, normalized matching, RDR poset of width w has a partition into w chains such that the sizes of the chains are one of two consecutive integers. In particular, there exists a partition of the linear lattices L_n(q) (subspaces of an n-dimensional vector space over a finite field, ordered by inclusion) into chains such that the number of chains is the width of L_n(q) and the sizes of the chains are one of two consecutive integers.     

Series-parallel posets and relative Ockham lattices

A study is undertaken of order-reversing maps on series-parallel posets and structural characterisations are obtained of various subclasses of such ordered sets. The results are applied to complete the authors' earlier investigation of classes of finite relate lattices, where is a variety of Ockham lattices and the distributive lattice duals of the algebras in are required to be series-parallel.