Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



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

Abstract | References | Similar Articles | Additional Information

Abstract: An inequality between the number of coverings in the ordered set $\operatorname{J}({\mathbf{Con\;J}})$ of join irreducible congruences on a lattice $\operatorname{L}$ and the size of ${\mathbf{L}}$ is given. Using this inequality it is shown that this ordered set can be computed in time $O(n^2 \log _2 n)$, where $n=|L|$.

References [Enhancements On Off] (What's this?)

  • 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 $\vert L\vert=\vert\textup{Con}(L)\vert$, 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

Similar Articles

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

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

American Mathematical Society