Representation of lattices via set-colored posets. (English) Zbl 06963372

Summary: This paper proposes a representation theory for any finite lattice via set-colored posets, in the spirit of Birkhoff for distributive lattices. The notion of colored posets was introduced in Nourine (2000) [34] and the generalization to set-colored posets was given in Nourine (2000) [35]. In this paper, we give a characterization of set-colored posets for general lattices, and show that set-colored posets capture the order induced by join-irreducible elements of a lattice as Birkhoff’s representation does for distributive lattices. We also give a classification for some lattices according to the coloring property of their set-colored representation including upper locally distributive, upper locally distributive, meet-extremal and semidistributive lattices.


06-XX Order, lattices, ordered algebraic structures
Full Text: DOI


[1] Adaricheva, K.; Nation, J. B., Convex geometries, (Grätzer, G.; Wehrung, F., Lattice Theory: Special Topics and Applications: Volume 2, (2016), Springer International Publishing Cham), 153-179 · Zbl 1390.06005
[2] Baïou, M.; Balinski, M., The stable allocation (or ordinal transportation) problem, Math. Oper. Res., 27, 4, 662-680, (2002) · Zbl 1083.90501
[3] Birkhoff, G., Lattices and their applications, Bull. Amer. Math. Soc., 44, 793-800, (1938) · JFM 64.0071.03
[4] Birkhoff, G., (Lattice Theory, Coll. Publ. XXV, (1967), American Mathematical Society Providence)
[5] Birkhoff, G., What can lattice do for you?, (Abbot, J. C., Trends in Lattice Theory, (1970), Van Nostrand-Reinhold New York), 1-40
[6] Birkhoff, G.; Frink, O., Representations of lattices by sets, Trans. Amer. Math. Soc., 64, 299-316, (1948) · Zbl 0032.00504
[7] Colomb, P.; Irlande, A.; Raynaud, O., Counting of Moore families for \(n = 7\), (ICFCA, (2010)), 72-87 · Zbl 1274.05013
[8] Davey, B. A.; Poguntke, W.; Rival, I., A characterization of semi-distributivity, Algebra Universalis, 5, 1, 72-75, (1975) · Zbl 0313.06002
[9] Davey, B. A.; Priestley, H. A., Introduction to lattices and orders, (1991), Cambridge University Press
[10] Dilworth, R. P., Lattices with unique irreducible decompositions, Ann. of Math., 41, 771-777, (1940) · JFM 66.0101.05
[11] Duquenne, V., The core of finite lattice, Discrete Math., 88, 133-147, (1991) · Zbl 0736.06012
[12] Edelman, P. H.; Saks, M. E., Combinatorial representation and convex dimension of convex geometries, Order, 5, 1, 23-32, (1988) · Zbl 0659.06005
[13] Freese, R.; Jezek, J.; Nation, J. B., (Free Lattices, Mathematical Surveys and Monographs, vol. 42, (1995), American Mathematical Society Providence, RI) · Zbl 0839.06005
[14] Ganter, B.; Wille, R., Formal concept analysis: mathematical foundations, (1996), Springer-Verlag Berlin · Zbl 0861.06001
[15] Gély, A.; Nourine, L.; Sadi, B., Enumeration aspects of maximal cliques and bicliques, Discrete Appl. Math., 157, 7, 1447-1459, (2009) · Zbl 1177.05056
[16] Geyer, W., Generalizing semidistributivity, Order, 10, 1, 77-92, (1993) · Zbl 0813.06007
[17] Grätzer, G., Lattice theory: foundation, (2011), Birkhäuser/Springer, Bassel · Zbl 1233.06001
[18] Gusfield, D.; Irving, R.; Leather, P.; Saks, M., Every finite distributive lattice is a set of stable matchings for a small stable marriage instance, J. Combin. Theory Ser. A, 44, 2, 304-309, (1987) · Zbl 0616.06009
[19] Habib, M.; Medina, R.; Nourine, L.; Steiner, G., Efficient algorithms on distributive lattices, Discrete Appl. Math., 110, 2-3, 169-187, (2001) · Zbl 0983.06009
[20] Habib, M.; Nourine, L., The number of Moore families on \(n = 6\), Discrete Math., 294, 3, 291-296, (2005) · Zbl 1083.06003
[21] Janssen, P.; Nourine, L., A simplicial elimination scheme for meet-semidistributive lattices and interval collapsing, Algebra Universalis, 50, 2, 171-178, (2003) · Zbl 1092.06004
[22] Jean-Claude, P.; Maurice, Q., On the structure of all minimum cuts in a network and applications, (Rayward-Smith, V., Combinatorial Optimization II, Mathematical Programming Studies, vol. 13, (1980)), 8-16 · Zbl 0442.90093
[23] Jégou, R.; Medina, R.; Nourine, L., Linear space algorithm for on-line detection of global predicates, (Desel, J., Structures in Concurrency Theory, Workshops in Computing, (1995), Springer Berlin), 175-189
[24] Kelly, D., Comparability graphs, (Rival, I., Graphs and Orders, (1985), D. Reidel Publishing Company), 3-40
[25] Knauer, K. B., Chip-firing, antimatroids, and polyhedra, Electron. Notes Discrete Math., 34, 9-13, (2009) · Zbl 1272.05121
[26] Knauer, K. B., Lattices and polyhedra from graphs, (2010), Technischen universitat Berlin, (Ph.D. thesis)
[27] Korte, B.; Lovász, L., Homomorphisms and Ramsey properties of antimatroids, Disc. Appl. Math, 15, 283-290, (1986) · Zbl 0647.05016
[28] MacNeille, H., Partially ordered sets, Trans. Amer. Math. Soc., 42, 90-96, (1937) · Zbl 0017.33904
[29] C. Magnien, H.D. Phan, L. Vuillon, Characterization of lattices induced by (extended) chip firing games, in: DM-CCG, 2001, pp. 229-244. · Zbl 1007.91503
[30] Markowsky, G., Combinatorial aspects of lattice theory with applications to the enumeration of free distributive lattices, (1973), Harvard University Cambridge, Massachsetts, (Ph.D. thesis)
[31] Markowsky, G., Some combinatorial aspects of lattice theory, (H. Lattice Theory Conf., (1973), Proc. Univ. of Houston), 36-68
[32] Markowsky, G., Primes, irreducibles and extremal lattices, Order, 9, 265-290, (1992) · Zbl 0778.06007
[33] Monjardet, B., The consequences of dilworth’s work on lattices with unique irreducible decompositions, (Bogart, K. P.; Freese, R.; Kung, J. P.S., The Dilworth Theorems: Selected Papers of Robert P. Dilworth, (1990), Birkhäuser Boston Boston, MA), 192-199
[34] Nourine, L., Colored posets and upper locally distributive lattices, technical report RR LIRMM 00060, (2000), Université Montpellier II, LIRMM
[35] Nourine, L., Une structuration algorithmique de la théorie des treillis, (Habilitation à diriger des recherches, (2000), Université de Montpellier II France)
[36] Roberts, F., T-colourings of graphs: recent results and open problems, Discrete Math., 93, 229-245, (1991) · Zbl 0751.05042
[37] Schröder, B. S.W., Ordered sets, an introduction, (2002), Birkhäuser Basel
[38] M.B. Squire, Enumerating the ideals of a poset, Preprint, North Carolina State University, 1995.
[39] Wille, R., Restructuring lattice theory: an approach based on hierarchies of contexts, (Rival, I., Ordered Sets, NATO ASI, vol. 83, (1982), Reidel Dordecht, Holland), 445-470
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.