A constructive approach to the finite congruence lattice representation problem

A finite lattice is representable if it is isomorphic to the congruence lattice of a finite algebra. In this paper, we develop methods by which we can construct new representable lattices from known ones. The techniques we employ are sufficient to show that every finite lattice which contains no three element antichains is representable. We then show that if an order polynomially complete lattice is representable then so is every one of its diagonal subdirect powers. Received August 30, 1999; accepted in final form November 29, 1999.     

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.     

The lattice of quasivarieties of undirected graphs

In this note, it is shown that the quasivariety of undirected graphs is Q-universal. Received March 3, 2000; accepted in final form January 31, 2001.     

A short proof of a theorem of Birkhoff

This paper gives a new proof of a theorem of G. Birkhoff: Every group can be represented as the automorphism group of a distributive lattice D; if is finite, D can be chosen to be finite. The new proof is short, and it is easily visualized. Received November 3, 1995; accepted in final form October 3, 1996.     

The preservation of Sahlqvist equations in completions of Boolean algebras with operators

Monk [1970] extended the notion of the completion of a Boolean algebra to Boolean algebras with operators. Under the assumption that the operators of such an algebra are completely additive, he showed that the completion of always exists and is unique up to isomorphisms over . Moreover, strictly positive equations are preserved under completions a strictly positive equation that holds in must hold in the completion of . In this paper we extend Monk’s preservation theorem by proving that certain kinds of Sahlqvist equations (as well as some other types of equations and implications) are preserved under completions. An example is given that shows that arbitrary Sahlqvist equations need not be preserved. Received May 3, 1998; accepted in final form October 7, 1998.     

Cauchy completions of MV-algebras

Abstract. An MV-convergence is a convergence on an MV-algebra which renders the operations continuous. We show that such convergences on a given MV-algebra A are exactly the restrictions of the bounded -convergences on the abelian -group in which A appears as the unit interval. Thus the theory of -convergence and Cauchy structures transfers to MV-algebras.?We outline the general theory, and then apply it to three particular MV-convergences and their corresponding Cauchy completions. The Cauchy completion arising from order convergence coincides with the Dedekind-MacNeille completion of an MV-algebra. The Cauchy completion arising from polar convergence allows a tidy proof of the existence and uniqueness of the lateral completion of an MV-algebra. And the Cauchy completion arising from α-convergence gives rise to the cut completion of an MV-algebra. Received August 8, 2001; accepted in final form October 18, 2001.     

On clones, transformation monoids, and finite Boolean algebras

We prove that, for a finite Boolean algebra, there exist only finitely many clones which consist of polynomial functions of the algebra and contain the monoid of its unary polynomial functions. Received January 7, 2000; accepted in final form December 13, 2000.     

Correction to "Some properties of complete congruence lattices"

Received April 26, 2000; accepted in final form July 19, 2001.     

Self-dual lattice identities

Given a finitely based self-dual variety of lattices, is it definable, modulo lattice theory, by a single self-dual lattice identity? There are infinitely many examples with “yes” as the answer and infinitely many with “no.”. Received December 20, 1999; accepted in final form July 11, 2002.     

The connected partition lattice of a graph and the reconstruction conjecture

Previously we showed that many invariants of a graph can be computed from its abstract induced subgraph poset, which is the isomorphism class of the induced subgraph poset, suitably weighted by subgraph counting numbers. In this paper, we study the abstract bond lattice of a graph, which is the isomorphism class of the lattice of distinct unlabelled connected partitions of a graph, suitably weighted by subgraph counting numbers. We show that these two abstract posets can be constructed from each other except in a few trivial cases. The constructions rely on certain generalisations of a lemma of Kocay in graph reconstruction theory to abstract induced subgraph posets. As a corollary, trees are reconstructible from their abstract bond lattice. We show that the chromatic symmetric function and the symmetric Tutte polynomial of a graph can be computed from its abstract induced subgraph poset. Stanley has asked if every tree is determined up to isomorphism by its chromatic symmetric function. We prove a counting lemma, and indicate future directions for a study of Stanley's question.     

The complexity of checking identities for finite matrix rings

We complete the investigations into the word-problem for finite matrix rings. Namely we prove that M₂ (Z₃), the ring of 2 x 2 matrices over Z₃, has a coNP-complete term-equivalence (or identity checking) problem.     

On order-polynomial completeness of lattices

In this note we prove that the cardinality of an infinite order-polynomially complete lattice (if such a lattice exists) must be greater than each , where is defined such that and for . This strengthens the result in [4]. Received November 10, 1995; accepted in final form April 6, 1998.     

A criterion for a finite endoprimal algebra to be endodualisable

In this note the strategy for finding endoprimal algebras due to B. A. Davey and J. G. Pitkethly is further explored in the finite case. The Retraction Test Algebra Lemma is used as a tool to show that, in many quasivarieties, endoprimality is equivalent to endodualisability for finite algebras which are suitably related to finitely generated free algebras. Received September 2, 1998; accepted in final form June 3, 1999.     

A new characterization of arithmeticity

We prove that an equivalence lattice is arithmetical whenever for every and there exists a compatible choice function modulo , having a as a fixed point. The converse holds if L is finite. Received September 30, 1998; accepted in final form December 1, 1998.     

Generalized symmetric elements generated by a prime sequence

Let be a prime sequence in a local Noether lattice L. For denotes the set of finite joins in L of power products of the generalized symmetric elements of order k (majorization elements) in together with 0 and I. We have previously showed that for is a Noetherian distributive -domain. For and for any is again such a sub--domain of . For and is not closed under the meet of . However with its induced meet is again a Noetherian distributive -domain. Each finite set of majorization elements asymptotically forms a distributive sublattice of for k sufficiently large. Received March 2, 1998; accepted in final form June 11, 1998.     

Congruence join semidistributivity is equivalent to a congruence identity

We show that a locally finite variety is congruence join semidistributive if and only if it satisfies a congruence identity that is strong enough to force join semidistributivity in any lattice. Received February 9, 2000; accepted in final form November 23, 2000.     

On coatoms in lattices of quasivarieties of algebraic systems

It is found the necessary condition for the lattice of quasivarieties has a finite set of coatoms. In particular if a quasivariety is generated by a finitely generated abelian-by-polycyclic-by-finite group or a totally ordered group then it has a finite set of proper maximal subquasivarieties. Also it is proved that the set of quasiverbal congruence relations of a finitely defined universal algebra is closed under any meets. Received March 23, 1999; accepted in final form June 7, 1999.     

On characterizations of atomistic lattices

In the present paper we characterize atomistic lattices. These characterizations are given in terms of concepts related to pure elements (cf. [4], [6]) and neat elements (cf. [3]).