Computing congruence lattices of finite lattices
HTML articles powered by AMS MathViewer
- by Ralph Freese PDF
- Proc. Amer. Math. Soc. 125 (1997), 3457-3463 Request permission
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
- P. Crawley and R. P. Dilworth, Algebraic Theory of Lattices, Prentice-Hall, Englewood Cliffs, New Jersey, 1973.
- Alan Day, Doubling constructions in lattice theory, Canad. J. Math. 44 (1992), no. 2, 252–269. MR 1162342, DOI 10.4153/CJM-1992-017-7
- Sergio Sispanov, Generalización del teorema de Laguerre, Bol. Mat. 12 (1939), 113–117 (Spanish). MR 3
- Albert Eagle, Series for all the roots of the equation $(z-a)^m=k(z-b)^n$, Amer. Math. Monthly 46 (1939), 425–428. MR 6, DOI 10.2307/2303037
- 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, DOI 10.1090/surv/042
- W. Geyer, The class of lattices with $|L|=|\textrm {Con}(L)|$, General algebra and applications (Potsdam, 1992) Res. Exp. Math., vol. 20, Heldermann, Berlin, 1993, pp. 86–88. MR 1209888
- Winfried Geyer, On Tamari lattices, Discrete Math. 133 (1994), no. 1-3, 99–122. MR 1298967, DOI 10.1016/0012-365X(94)90019-1
- 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, DOI 10.1090/S0002-9939-1995-1301498-5
- 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, DOI 10.1090/S0002-9939-1995-1301498-5
- 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
- Robert Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput. 1 (1972), no. 2, 146–160. MR 304178, DOI 10.1137/0201010
Additional Information
- Ralph Freese
- Affiliation: Department of Mathematics, University of Hawaii, Honolulu, Hawaii 96822
- Email: ralph@math.hawaii.edu
- 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
- © Copyright 1997 American Mathematical Society
- 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