Computing congruence lattices

of finite lattices

Author:
Ralph Freese

Journal:
Proc. Amer. Math. Soc. **125** (1997), 3457-3463

MSC (1991):
Primary 06B10, 06B05, 06B15

DOI:
https://doi.org/10.1090/S0002-9939-97-04332-3

MathSciNet review:
1451802

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An inequality between the number of coverings in the ordered set of join irreducible congruences on a lattice and the size of is given. Using this inequality it is shown that this ordered set can be computed in time , where .

**1.**P. Crawley and R. P. Dilworth,*Algebraic Theory of Lattices*, Prentice-Hall, Englewood Cliffs, New Jersey, 1973.**2.**A. Day,*Doubling constructions in lattice theory*, Canad. J. Math.**44**(1992), 252-269. MR**93f:06008****3.**R. P. Dilworth,*The arithmetical theory of Birkhoff lattices*, Duke Math. J.**8**(1941), 286-299. MR**3:100a****4.**R. P. Dilworth and M. Hall,*The embedding theorem for modular lattices*, Ann. of Math.**45**(1944), 450-456. MR**6:33c****5.**R. Freese, J. Je\v{z}ek, and J. B. Nation,*Free Lattices*, Amer. Math. Soc., Providence, 1995, Mathematical Surveys and Monographs, vol. 42. MR**96c:06013****6.**W. Geyer,*The class of lattices with*, General algebra and application, Heldermann, Berlin, 1993, pp. 86-88. MR**94c:06012****7.**W. Geyer,*On Tamari lattices*, Discrete Math.**133**(1994), 99-122. MR**95m:06021****8.**G. Grätzer, H. Lakser, and E. T. Schmidt,*Congruence lattices of small planar lattices*, Proc. Amer. Math. Soc.**123**(1995), 2619-2623. MR**95k:06017a****9.**G. Grätzer, I. Rival, and N. Zaguia,*Small representations of finite distributive lattices as congruence lattices*, Proc. Amer. Math. Soc.**123**(1995), 1959-1961; Correction, Proc. Amer. Math. Soc., to appear. MR**95k:06017b****10.**R. Medina and L. Nourine,*Algorithme efficace de génération des idéaux d'un ensemble ordonné*, C. R. Acad. Sci. Paris Sér. I Math.**319**(1994), 1115-1120. MR**95i:06006****11.**R. E. Tarjan,*Depth first searches and linear graph algorithms*, SIAM J. of Computing**1**(1972), 146-160. MR**46:3313**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (1991):
06B10,
06B05,
06B15

Retrieve articles in all journals with MSC (1991): 06B10, 06B05, 06B15

Additional Information

**Ralph Freese**

Affiliation:
Department of Mathematics, University of Hawaii, Honolulu, Hawaii 96822

Email:
ralph@math.hawaii.edu

DOI:
https://doi.org/10.1090/S0002-9939-97-04332-3

Keywords:
Congruence lattice,
algorithm

Received by editor(s):
June 11, 1996

Additional Notes:
This research was partially supported by NSF grant no. DMS–9500752

Communicated by:
Lance W. Small

Article copyright:
© Copyright 1997
American Mathematical Society