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.     

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.     

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.     

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.     

Insertion of lattice-valued and hedgehog-valued functions

Problems of inserting lattice-valued functions are investigated. We provide an analogue of the classical insertion theorem of Lane [Proc. Amer. Math. Soc. 49 (1975) 90-94] for L-valued functions where L is a ?-separable completely distributive lattice (i.e. L admits a countable join-dense subset which is free of completely join-irreducible elements). As a corollary we get an L-version of the Katětov-Tong insertion theorem due to Liu and Luo [Topology Appl. 45 (1992) 173-188] (our proof is different and much simpler). We show that ?-separable completely distributive lattices are closed under the formation of countable products. In particular, the Hilbert cube is a ?-separable completely distributive lattice and some join-dense subset is shown to be both order and topologically isomorphic to the hedgehog J(ω) with appropriately defined topology. This done, we deduce an insertion theorem for J(ω)-valued functions which is independent of that of Blair and Swardson [Indian J. Math. 29 (1987) 229-250]. Also, we provide an iff criterion for inserting a pair of semicontinuous function which yields, among others, a characterization of hereditarily normal spaces.     

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

Convex partitions of a finite lattice

The purpose of this paper is to introduce the lattice of convex partitions for a lattice L. Then we will show some properties of this lattice. Finally, we will show that if the convex partition lattice of L is finite and modular if and only if L is a finite chain. Presented by R. McKenzie. Received December 16, 2004; accepted in final form March 7, 2006.     

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.     

A structure theorem for dismantlable lattices and enumeration

The concept of `adjunct' operation of two lattices with respect to a pair of elements is introduced. A structure theorem namely, `A finite lattice is dismantlable if and only if it is an adjunct of chains' is obtained. Further it is established that for any adjunct representation of a dismantlable lattice the number of chains as well as the number of times a pair of elements occurs remains the same. If a dismantlable lattice L has n elements and n+k edges then it is proved that the number of irreducible elements of L lies between n-2k-2 and n-2. These results are used to enumerate the class of lattices with exactly two reducible elements, the class of lattices with n elements and upto n+1 edges, and their subclasses of distributive lattices and modular lattices. This revised version was published online in June 2006 with corrections to the Cover Date.     

A note on essentially convex orders

In this note, we determine precisely which partially ordered sets (posets) have the property that, whenever they occur as subposets of a larger poset, they occur there convexly, i.e., as convex subposets. As a corollary, we also determine which lattices have the property that, if they occur as sublattices of a finite distributive lattice L, then they also occur as closed intervals in L. Throughout, all sets will be finite.Dedicated to the memory of Ivan RivalReceived May 5, 2003; accepted in final form October 3, 2004.This revised version was published online in August 2005 with a corrected cover date.     

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     

Graded left modular lattices are supersolvable

We provide a direct proof that a finite graded lattice with a maximal chain of left modular elements is supersolvable. This result was first established via a detour through EL-labellings in [MT] by combining results of McNamara [Mc] and Liu [Li]. As part of our proof, we show that the maximum graded quotient of the free product of a chain and a single-element lattice is finite and distributive.Received May 24, 2004; accepted in final form October 12, 2004.     

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

On the lattice formed by all normal subloops of a finite loop

All normal subloops of a loopG form a modular latticeL _n (G). It is shown that a finite loopG has a complemented normal subloop lattice if and only ifG is a direct product of simple subloops. In particular,L _n (G) is a Boolean algebra if and only if no two isomorphic factors occurring in a decomposition ofG are abelian groups. The normal subloop lattice of a finite loop is a projective geometry if and only ifG is an elementary abelianp-group for some primep.     

Lattices on simplicial partitions

In this paper, (d+1)-pencil lattices on simplicial partitions in R^d are studied. The barycentric approach naturally extends the lattice from a simplex to a simplicial partition, providing a continuous piecewise polynomial interpolant over the extended lattice. The number of degrees of freedom is equal to the number of vertices of the simplicial partition. The constructive proof of this fact leads to an efficient computer algorithm for the design of a lattice.     

Optimal tristance anticodes in certain graphs

For z₁,z₂,z₃∈Zⁿ, the tristance d₃(z₁,z₂,z₃) is a generalization of the L₁-distance on Zⁿ to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticodeA_d of diameter d is a subset of Zⁿ with the property that d₃(z₁,z₂,z₃)?d for all z₁,z₂,z₃∈A_d. An anticode is optimal if it has the largest possible cardinality for its diameter d. We determine the cardinality and completely classify the optimal tristance anticodes in Z² for all diameters d?1. We then generalize this result to two related distance models: a different distance structure on Z² where d(z₁,z₂)=1 if z₁,z₂ are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when Z² is replaced by the hexagonal lattice A₂. We also investigate optimal tristance anticodes in Z³ and optimal quadristance anticodes in Z², and provide bounds on their cardinality. We conclude with a brief discussion of the applications of our results to multi-dimensional interleaving schemes and to connectivity loci in the game of Go.     

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.