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

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

  2. Which unary polynomials on free lattices are fixed point free? For which unary polynomials f does the join of fi(a) exist for all a?

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

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

  5. Does there exist a quadruple a < c1 <= c2 < b of elements of a free lattice FL(X) such that the intervals c1/a and b/c2 are both infinite and every element of b/a is comparable with either c1 or c2?

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

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

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

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

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

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

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

  1. 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?

  2. Can one decide if an ordered set of size n is a lattice in time faster than O(n5/2)?

  3. If d(n) denotes the minimum cardinality of a lattice of order dimension n, is d(n) in O(n2)?

  4. Is there an infinite lattice which is order polynomially complete?


5 May 1999
Ralph Freese
ralph@math.hawaii.edu