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.     

Finite Intervals in the Lattice of Topologies

We discuss the question whether every finite interval in the lattice of all topologies on some set is isomorphic to an interval in the lattice of all topologies on a finite set – or, equivalently, whether the finite intervals in lattices of topologies are, up to isomorphism, exactly the duals of finite intervals in lattices of quasiorders. The answer to this question is in the affirmative at least for finite atomistic lattices. Applying recent results about intervals in lattices of quasiorders, we see that, for example, the five-element modular but non-distributive lattice cannot be an interval in the lattice of topologies. We show that a finite lattice whose greatest element is the join of two atoms is an interval of T ₀-topologies iff it is the four-element Boolean lattice or the five-element non-modular lattice. But only the first of these two selfdual lattices is an interval of orders because order intervals are known to be dually locally distributive.     

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.     

Remarks on affine complete distributive lattices

We characterise the Priestley spaces corresponding to affine complete bounded distributive lattices. Moreover we prove that the class of affine complete bounded distributive lattices is closed under products and free products. We show that every (not necessarily bounded) distributive lattice can be embedded in an affine complete one and that ℚ ∩ [0, 1] is initial in the class of affine complete lattices.     

Lattice-valued fuzzy Turing machines: Computing power, universality and efficiency

In this paper we study fuzzy Turing machines with membership degrees in distributive lattices, which we called them lattice-valued fuzzy Turing machines. First we give several formulations of lattice-valued fuzzy Turing machines, including in particular deterministic and non-deterministic lattice-valued fuzzy Turing machines (l-DTMcs and l-NTMs). We then show that l-DTMcs and l-NTMs are not equivalent as the acceptors of fuzzy languages. This contrasts sharply with classical Turing machines. Second, we show that lattice-valued fuzzy Turing machines can recognize n-r.e. sets in the sense of Bedregal and Figueira, the super-computing power of fuzzy Turing machines is established in the lattice-setting. Third, we show that the truth-valued lattice being finite is a necessary and sufficient condition for the existence of a universal lattice-valued fuzzy Turing machine. For an infinite distributive lattice with a compact metric, we also show that a universal fuzzy Turing machine exists in an approximate sense. This means, for any prescribed accuracy, there is a universal machine that can simulate any lattice-valued fuzzy Turing machine on it with the given accuracy. Finally, we introduce the notions of lattice-valued fuzzy polynomial time-bounded computation (lP) and lattice-valued non-deterministic fuzzy polynomial time-bounded computation (lNP), and investigate their connections with P and NP. We claim that lattice-valued fuzzy Turing machines are more efficient than classical Turing machines.     

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.     

On Lattices of Uniformities

We study lattice theoretical properties of lattices of uniformities such as modularity, distributive laws and the existence of (relative) complements. For this the concepts of permutable uniformities (see Definition 3.1) and independent uniformities (see Definition 4.1) are important. Moreover, we show that e.g. the lattice of all lattice uniformities on a lattice L is a closed sublattice of the lattice of all uniformities on L.     

分配格与模格的另一二条件等价定义

针对分配格与模格的格等式定义问题,得知了二条件是定义分配格与模格的最少条件,并进一步证明了Sholander's basis是定义分配格的最短最少变量格等式,最后又从分配格和模格的基本定义出发给出了新的分配格的二条件和三条件等价定义等式及模格的二条件与三条件等价定义等式.     

Z-Join Spectra of Z-Supercompactly Generated Lattices

The main result of this paper is a generalization of the classical equivalence between the category of continuous posets and the category of completely distributive lattices, based on the fact that the continuous posets are precisely the spectra of completely distributive lattices. Here we show that for so-called hereditary and union complete subset selections Z, the category of Z-continuous posets is equivalent (via a suitable spectrum functor) to the category of Z-supercompactly generated lattices; these are completely distributive lattices with a join-dense subset of certain Z-hypercompact elements. By appropriate change of the morphisms, these equivalences turn into dualities. We present two different approaches: the first one directly uses the Z-join ideal completion and the Z-below relation; the other combines two known equivalence theorems, namely a topological representation of Z-continuous posets and a general lattice theoretical representation of closure spaces.     

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.     

Semimodular Lattices and Semibuildings

In a ranked lattice, we consider two maximal chains, or flags to be i-adjacent if they are equal except possibly on rank i. Thus, a finite rank lattice is a chamber system. If the lattice is semimodular, as noted in [9], there is a Jordan-Hölder permutation between any two flags. This permutation has the properties of an S_n-distance function on the chamber system of flags. Using these notions, we define a W-semibuilding as a chamber system with certain additional properties similar to properties Tits used to characterize buildings. We show that finite rank semimodular lattices form an S_n-semibuilding, and develop a flag-based axiomatization of semimodular lattices. We refine these properties to axiomatize geometric, modular and distributive lattices as well, and to reprove Tits' result that S_n-buildings correspond to relatively complemented modular lattices (see [16], Section 6.1.5).     

A Distributive Lattice Structure Connecting Dyck Paths,Noncrossing Partitions and 312-avoiding Permutations

In [Ferrari, L. and Pinzani, R.: Lattices of lattice paths. J. Stat. Plan. Inference 135 (2005), 77–92] a natural order on Dyck paths of any fixed length inducing a distributive lattice structure is defined. We transfer this order to noncrossing partitions along a well-known bijection [Simion, R.: Noncrossing partitions. Discrete Math. 217 (2000), 367–409], thus showing that noncrossing partitions can be endowed with a distributive lattice structure having some combinatorial relevance. Finally we prove that our lattices are isomorphic to the posets of 312-avoiding permutations with the order induced by the strong Bruhat order of the symmetric group.     

Coproducts of bounded distributive lattices: cancellation

Let denote the coproduct of the bounded distributive lattices L and M. At the 1981 Banff Conference on Ordered Sets, the following question was posed: What is the largest class L of finite distributive lattices such that, for every non-trivial Boolean lattice B and every implies ? In this note, the problem is solved. Received March 2, 1999; accepted in final form July 10, 2000.     

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.     

对称扩展的有界分配格的同余关系及其应用

给出了对称扩展的有界分配格的定义,即带有满足一定条件的一元运算的有界分配格.然后给出了这种分配格上的主同余的等式刻划及其可补性.最后,讨论了对称扩展的有界分配格的次直不可约性。     

Singularities of Toric Varieties Associated with Finite Distributive Lattices

With each finite lattice L we associate a projectively embedded scheme V(L); as Hibi has shown, the lattice D is distributive if and only if V(D) is irreducible, in which case it is a toric variety. We first apply Birkhoff's structure theorem for finite distributive lattices to show that the orbit decomposition of V(D) gives a lattice isomorphic to the lattice of contractions of the bounded poset of join-irreducibles of D. Then we describe the singular locus of V(D) by applying some general theory of toric varieties to the fan dual to the order polytope of P: V(D) is nonsingular along an orbit closure if and only if each fibre of the corresponding contraction is a tree. Finally, we examine the local rings and associated graded rings of orbit closures in V(D). This leads to a second (self-contained) proof that the singular locus is as described, and a similar combinatorial criterion for the normal link of an orbit closure to be irreducible.     

Cambrian lattices

For an arbitrary finite Coxeter group W, we define the family of Cambrian lattices for W as quotients of the weak order on W with respect to certain lattice congruences. We associate to each Cambrian lattice a complete fan, which we conjecture is the normal fan of a polytope combinatorially isomorphic to the generalized associahedron for W. In types A and B we obtain, by means of a fiber-polytope construction, combinatorial realizations of the Cambrian lattices in terms of triangulations and in terms of permutations. Using this combinatorial information, we prove in types A and B that the Cambrian fans are combinatorially isomorphic to the normal fans of the generalized associahedra and that one of the Cambrian fans is linearly isomorphic to Fomin and Zelevinsky's construction of the normal fan as a “cluster fan.” Our construction does not require a crystallographic Coxeter group and therefore suggests a definition, at least on the level of cellular spheres, of a generalized associahedron for any finite Coxeter group. The Tamari lattice is one of the Cambrian lattices of type A, and two “Tamari” lattices in type B are identified and characterized in terms of signed pattern avoidance. We also show that open intervals in Cambrian lattices are either contractible or homotopy equivalent to spheres.     

Group-valued modular functions

Modular functions on a lattice (m(x)+m(y)=m(x∪y)+m(x∩y)) live on modular lattices in that they are induced by modular functions on a quotient modular lattice. Those which identify pairs of the distributive inequality live on distributive lattices in the same sense. The structure of all modular functions on a lattice of finite height is determined. The “distance function” derived by Kranz from a modular function is shown to satisfy the triangle inequality. Presented by E. Nelson.     

Efficient algorithms on distributive lattices

We present several efficient algorithms on distributive lattices. They are based on a compact representation of the lattice, called the ideal tree. This allows us to exploit regularities in the structure of distributive lattices. The algorithms include a linear-time algorithm to reconstruct the covering graph of a distributive lattice from its ideal tree, a linear-time incremental algorithm for building the ideal lattice of a poset and a new incremental algorithm for listing the ideals of a poset in a combinatorial Gray code manner (in an code.)