Proceedings of the American Mathematical Society

Author(s): Ralph Freese
Journal: Proc. Amer. Math. Soc. 125 (1997), 3457-3463.
MSC (1991): Primary 06B10, 06B05, 06B15
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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

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

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

Ralph Freese
Affiliation: Department of Mathematics, University of Hawaii, Honolulu, Hawaii 96822
Email: ralph@math.hawaii.edu

DOI: 10.1090/S0002-9939-97-04332-3
PII: S 0002-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
Copyright of article: Copyright 1997, American Mathematical Society

Gr\"atzer, George and Wang, Dabin, A lower bound for congruence representations,Order(1) 14(1997), 67-74. (English) MR 98k:06008

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6826 (e) ISSN 0002-9939 (p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS