Graphical algebras — a new approach to congruence lattices

In 1970, H. Werner considered the question of which sublattices of partition lattices are congruence lattices for an algebra on the underlying set of the partition lattices. He showed that a complete sublattice of a partition lattice is a congruence lattice if and only if it is closed under a new operation called graphical composition. We study the properties of this new operation, viewed as an operation on an abstract lattice. We obtain some necessary properties, and we also obtain some sufficient conditions for an operation on an abstract lattice L to be this operation on a congruence lattice isomorphic to L. We use this result to give a new proof of Grätzer and Schmidt’s result that any algebraic lattice occurs as a congruence lattice.     

Lattices with Complemented Tolerance Lattice

We characterize lattices with a complemented tolerance lattice. As an application of our results we give a characterization of bounded weakly atomic modular lattices with a Boolean tolerance lattice.     

On lattices embeddable into subsemigroup lattices. III: Nilpotent semigroups

We prove that the class of the lattices embeddable into subsemigroup lattices of n-nilpotent semigroups is a finitely based variety for all n < ω. Repnitski? showed that each lattice embeds into the subsemigroup lattice of a commutative nilsemigroup of index 2. In this proof he used a result of Bredikhin and Schein which states that each lattice embeds into the suborder lattices of an appropriate order. We give a direct proof of the Repnitski? result not appealing to the Bredikhin-Schein theorem, so answering a question in a book by Shevrin and Ovsyannikov.     

The free orthomodular lattice on countably many generators is a subalgebra of the free orthomodular lattice on three generators

We show every at most countable orthomodular lattice is a subalgebra of one generated by three elements. As a corollary we obtain that the free orthomodular lattice on countably many generators is a subalgebra of the free orthomodular lattice on three generators. This answers a question raised by Bruns in 1976 [2] and listed as Problem 15 in Kalmbach's book on orthomodular lattices [6]. Received April 12, 2001; accepted in final form May 6, 2002.     

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.     

An efficient lattice reduction method for F2-linear pseudorandom number generators using Mulders and Storjohann algorithm

Recent simulations often use highly parallel machines with many processors, and they need many pseudorandom number generators with distinct parameter sets, and hence we need an effective fast assessment of the generator with a given parameter set. Linear generators over the two-element field are good candidates, because of the powerful assessment via their dimensions of equidistribution. Some efficient algorithms to compute these dimensions use reduced bases of lattices associated with the generator. In this article, we use a fast lattice reduction algorithm by Mulders and Storjohann instead of Schmidt’s algorithm, and show that the order of computational complexity is lessened. Experiments show an improvement in the speed by a factor of three. We also report that just using a sparsest initial state (i.e., consisting of all 0 bits except one) significantly accelerates the lattice computation, in the case of Mersenne Twister generators.     

Non-representable distributive semilattices

We present two examples of distributive algebraic lattices which are not isomorphic to the congruence lattice of any lattice. The first such example was discovered by F. Wehrung in 2005. One of our examples is defined topologically, the other one involves majority algebras. In particular, we prove that the congruence lattice of the free majority algebra on (at least) ℵ₂ generators is not isomorphic to the congruence lattice of any lattice. Our method is a generalization of Wehrung’s approach, so that we are able to apply it to a larger class of distributive semilattices.     

Average site perimeter of directed animals on the two-dimensional lattices

We introduce new combinatorial (bijective) methods that enable us to compute the average value of three parameters of directed animals of a given area, including the site perimeter. Our results cover directed animals of any one-line source on the square lattice and its bounded variants, and we give counterparts for most of them in the triangular lattices. We thus prove conjectures by Conway and Le Borgne. The techniques used are based on Viennot’s correspondence between directed animals and heaps of pieces (or elements of a partially commutative monoid).     

Extremal Polygons with Minimal Perimeter

In this paper we will investigate an isoperimetric type problem in lattices. If K is a bounded O-symmetric (centrally symmetric with respect to the origin) convex body in En of volume v(K) = 2n det L which does not contain non-zero lattice points in its interior, we say that K is extremal with respect to the given lattice L. There are two variations of the isoperimetric problem for this class of polyhedra. The first one is: Which bodies have minimal surface area in the class of extremal bodies for a fixed n-dimensional lattice? And the second one is: Which bodies have minimal surface area in the class of extremal bodies with volume 1 of dimension n? We characterize the solutions of these two problems in the plane. There is a consequence of these results, the solutions of the above problems in the plane give the solution of the lattice-like covering problem: Determine those centrally symmetric convex bodies whose translated copies (with respect to a fixed lattice L) cover the space and have minimal surface area.

     

Lattice theory and metric geometry

K. Menger and G. Birkhoff recognized 70 years ago that lattice theory provides a framework for the development of incidence geometry (affine and projective geometry). We show in this article that lattice theory also provides a framework for the development of metric geometry (including the euclidean and classical non-euclidean geometries which were first discovered by A. Cayley and F. Klein). To this end we introduce and study the concept of a Cayley–Klein lattice. A detailed investigation of the groups of automorphisms and an algebraic characterization of Cayley–Klein lattices are included. The authors would like to thank an unknown referee for his helpful suggestions.     

矩阵代数的Kadison-Singer格的分类

研究了矩阵代数M_n(C)的KS格,证明了每个生成M_3(C)的KS格都相似于(?)_0或I-(?)_0,其中(?)_0为M_3(C)的一个极大对角投影套和一个赋值全非零的秩1投影所生成的KS格,从而M_3(C)的对角平凡的KS代数都是4维的.同时,还给出了几个生成M_4(C)但非同构的KS格的例子.     

Structure of lattices of varieties and lattices of quasivarieties: Similarity and difference. II

A general characterization of lattices of varieties and lattices of quasivarieties in terms of (quasi)Birkhoff classes is given and a method for constructing their homomorphic images is presented. As an application, it is proved that the lattice of varieties of modular lattices has a complete homomorphism onto the Boolean lattice of subsets of a countable set. Also, sufficient conditions are found for embedding the free lattice with generators in a given lattice of quasivarieties, and we show that these are also sufficient for a quasivariety to be Q-universal. Other applications and examples are given.Translated fromAlgebra i Logika, Vol. 34, No. 4, pp. 369–397, July-August, 1995.     

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

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

Non-Operator Reflexive Subspace Lattices

In [2] various types of closedness of subspace lattices were studied. In particular, the authors defined operator reflexivity which can be regarded as a one-point closedness of the lattice. They asked if all subspace lattices are operator reflexive. In this work we give an example that the answer is negative. The second author was supported by grant no. 201/06/0128 of GA CR.     

关于拟连续domain以及函数空间的注记

用伴随的方式给出了拟连续domain以及其Scott闭集格(又叫广义完全分配格)的等价刻画。此外,本文证明了拟连续格关于函数空间是不封闭的,从而不能构成cartesian闭范畴。     

About positive weak Dunford-Pettis operators on Banach lattices

We characterize Banach lattices for which each positive weak Dunford-Pettis operator from a Banach lattice into another dual Banach lattice is almost Dunford-Pettis. Also, we give some sufficient and necessary conditions for which the class of positive weak Dunford-Pettis operators coincides with that of positive Dunford-Pettis operators, and we derive some consequences.     

Involutive Residuated Lattices Based on Modular and Distributive Lattices

An involutive residuated lattice (IRL) is a lattice-ordered monoid possessing residual operations and a dualizing element. We show that a large class of self-dual lattices may be endowed with an IRL structure, and give examples of lattices which fail to admit IRLs with natural algebraic conditions. A classification of all IRLs based on the modular lattices M _n is provided.     

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.