Free and Finitely Presented Lattices
Description: We'll say more later but for now we'll
just say that free lattices don't cost much. In fact
the book only cost $39.
Open Problems
Free Lattices

(R. A. Dean) Can a free lattice have an ascending chain of
sublattices all isomorphic to FL(3)?

Which unary polynomials on free lattices are fixed point free?
For which unary polynomials f does
the join of f^{i}(a) exist for
all a?

Characterize those ordered sets which can be embedded
into a free lattice.

Which lattices (and in particular
which countable lattices) are sublattices of a free lattice?

Does there exist a quadruple
a < c_{1} <= c_{2} < b of
elements of a free lattice FL(X) such that the
intervals c_{1}/a and b/c_{2} are both
infinite and every element of b/a is comparable with either
c_{1} or c_{2}?

Describe all meet reducible elements a of FL(X)
such that every element above a is comparable with a canonical
meetand of a.

Which completely join irreducible
elements a in FL(X) are such that
kappa(a) is the dual of a?
Are there infinitely many for fixed X?
Finite Presented Lattices

Is there a polynomial
time algorithm which decides if an element
w in a finitely presented lattice FL(P) is completely
join irreducible?

Is there a
polynomial time algorithm which decides
if a finitely presented lattice is finite?

Is there an
algorithm to decide
if a finitely presented lattice is weakly atomic? of finite width?

Is there a
polynomial time algorithm which decides
if a finitely presented lattice is projective?

If L is a finitely presented lattice in which every nonzero join
irreducible element has a lower cover and the dual property holds, is
L finite?
Miscellaneous

Does every finitely generated lattice variety have a finite, convergent
AC term rewrite system? What about every variety generated
by a finite lower (or upper) bounded lattice?

Can one decide if an ordered set of size n
is a lattice in time faster than O(n^{5/2})?

If d(n) denotes the minimum cardinality of a
lattice of order dimension n,
is d(n) in O(n^{2})?

Is there an infinite lattice which is order polynomially complete?
5 May 1999
Ralph Freese
ralph@math.hawaii.edu