Computing congruence lattices

of finite lattices

Author:
Ralph Freese

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

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

MathSciNet review:
1451802

Full-text PDF Free Access

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.**Alan Day,*Doubling constructions in lattice theory*, Canad. J. Math.**44**(1992), no. 2, 252–269. MR**1162342**, 10.4153/CJM-1992-017-7**3.**R. P. Dilworth,*The arithmetical theory of Birkhoff lattices*, Duke Math. J.**8**(1941), 286–299. MR**0005094****4.**M. Hall and R. P. Dilworth,*The imbedding problem for modular lattices*, Ann. of Math. (2)**45**(1944), 450–456. MR**0010541****5.**Ralph Freese, Jaroslav Ježek, and J. B. Nation,*Free lattices*, Mathematical Surveys and Monographs, vol. 42, American Mathematical Society, Providence, RI, 1995. MR**1319815****6.**W. Geyer,*The class of lattices with \vert𝐿\vert=\vert{𝐶𝑜𝑛}(𝐿)\vert*, General algebra and applications (Potsdam, 1992) Res. Exp. Math., vol. 20, Heldermann, Berlin, 1993, pp. 86–88. MR**1209888****7.**Winfried Geyer,*On Tamari lattices*, Discrete Math.**133**(1994), no. 1-3, 99–122. MR**1298967**, 10.1016/0012-365X(94)90019-1**8.**G. Grätzer, H. Lakser, and E. T. Schmidt,*Congruence lattices of small planar lattices*, Proc. Amer. Math. Soc.**123**(1995), no. 9, 2619–2623. MR**1301498**, 10.1090/S0002-9939-1995-1301498-5**9.**George Grätzer, Ivan Rival, and Nejib Zaguia,*Small representations of finite distributive lattices as congruence lattices*, Proc. Amer. Math. Soc.**123**(1995), no. 7, 1959–1961. MR**1301499**, 10.1090/S0002-9939-1995-1301499-7**10.**Raoul Medina and Lhouari 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), no. 10, 1115–1120 (French, with English and French summaries). MR**1305686****11.**Robert Tarjan,*Depth-first search and linear graph algorithms*, SIAM J. Comput.**1**(1972), no. 2, 146–160. MR**0304178**

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:
http://dx.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