×

Les treillis pseudocomplémentés finis. (The finite pseudocomplemented lattices). (French) Zbl 0759.06010

Summary: Let \(L\) be a lattice with a least element denoted \(o\); \(g(t)\in L\) is a meet pseudocomplement of \(t\in L\) if \(x\land t=o\) is equivalent to \(x\leq g(t)\); \(L\) is meet pseudocomplemented if every element of \(L\) has a meet pseudocomplement. One defines dually the notion of join pseudocomplemented lattice. A lattice is pseudocomplemented if it is meet and join pseudocomplemented (such a lattice is sometimes called a double \(p\)-lattice, and the associated algebra a double \(p\)-algebra). These lattices have been intensively studied when they are distributive and infinite (Brouwer or Heyting lattices or algebras. Stone lattices or algebras). Examples of finite non-distributive pseudocomplemented lattices are the finite Coxeter groups endowed with the Bruhat weak ordering (especially, the ‘permutohedron’ lattice of Guilbaud and Rosenstiehl is obtained with the symmetric group), and the lattice of binary bracketings (Friedman and Tamari); these lattices are also complemented. We study the finite pseudocomplemented lattices, showing for instance that the pseudocomplements are obtained from the atoms and coatoms, that for complemented lattices meet pseudocomplementation is equivalent to join pseudocomplementation, and giving several results that clarify the structure of such lattices. These results can be applied especially to the permutohedron lattice and to the lattice of binary bracketings.

MSC:

06D15 Pseudocomplemented lattices
06C15 Complemented lattices, orthocomplemented lattices and posets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aigner, M., Combinatorial theory (1980), Springer-Verlag: Springer-Verlag berlin
[2] Balbes, R.; Horn, A., Stone lattices, Duke Math. J., 37, 537-546 (1970) · Zbl 0207.02802
[3] Balbes, B.; Horn, A., Injective and projective Heyting Algebras, Trans. Am. Math. Soc., 148, 549-559 (1970) · Zbl 0199.32203
[4] Barbut, M.; Monjardet, B., (Ordre et Classification, Alge‘bre et Combinatoire (1970), Hachette: Hachette Paris)
[5] Bennett, M. K.; Birkhoff, G., Two families of Newman lattices, Algebra Universalis (1992), a‘paraiˆtre · Zbl 0810.06006
[6] Birkhoff, G., (Lattice THeory (1940), Amrican Mathematical Society: Amrican Mathematical Society Providence, R.I.) · Zbl 0063.00402
[7] Bjo¨rner, A., Orderings of Coxeter groups, (Greene, C., Combinatorics and algebra. Combinatorics and algebra, Contemporary Mathematics, 34 (1984), American Mathematical Society: American Mathematical Society Providence, R.I.), 175-195
[8] Chameni-Nembua, C., Permutoe‘dre et choix social, (the‘se de doctorat de mathe´matiques (1989), Universite´de Paris V) · Zbl 0699.90008
[9] Chameni-Nembua, C., Re´gle majoritaire et distributivite´dans le permutoe‘dre, Math. Inf. Sci. hum., 108, 5-22 (1989) · Zbl 0699.90008
[10] Chameni-Nembua, C.; Monjardet, B., Finite pseudocomplemented lattices and ‘permutoe‘dre’, Discr. Math., 72 (1992), a‘paraiˆtre · Zbl 0759.06010
[11] Dilworth, R. P., Lattice with unique irreducible decompositions, Ann. Math.. (Bogart, K.; Freese, R.; Kung, J., The Dilworth Theorems (1990), Birkha¨user: Birkha¨user Boston), 41, 771-777 (1940), re´imprime´en · Zbl 0025.10202
[12] Duquenne, V.; Cherfouh, A., On the permutation lattice, report (September 1991)
[13] Dushnik, B.; Miller, E. W., Partially ordered sets, Am. J. Math., 63, 600-610 (1941) · Zbl 0025.31002
[14] Edelman, P.; Greene, C., Combinatorial correspondences for Young tableaux, balanced tableaux, and maximal chains in the weak Bruhat order of \(S_n\), (Greene, C., Combinatorics and Algebra. Combinatorics and Algebra, Contemporary Mathematics, 34 (1984), American Mathematical Society: American Mathematical Society Providence, R.I.), 155-162
[15] Edelman, P.; Greene, C., Balanced tableaux, Adv. Math., 63, 1, 42-99 (1987) · Zbl 0616.05005
[16] Frey, L., Parties distributives du treillis des permutations, (Ordres totaux finis. Ordres totaux finis, Mathe´matiques et Sciences de I’Homme XII (1971), Gauthier-Villars: Gauthier-Villars Paris), 115-126
[17] Frey, L.; Barbut, M., Techniques ordinales en analyse des donne´es: alge‘bre et Combinatoire (1971), Hachette: Hachette Paris · Zbl 0241.05001
[18] Friedman, H.; Tamari, D., Une structure de treillis fini induite par une loi demi-associative, J. Combin. Theory, Se´r. A, 2, 215-242 (1967) · Zbl 0158.01904
[19] Frink, O., Pseudo-complements in semi lattices, Duke Math. J., 29, 505-514 (1962) · Zbl 0114.01602
[20] Glivenko, V., Sur quelques points de la logique de Brouwer, Bull. Acad. Sci. Belg., 15, 183-188 (1929) · JFM 55.0030.05
[21] Guilbaud, G. Th., Les the´ories de I’inte´reˆt ge´ne´ral et le proble“me logique de I”agre´gation, Econ. Appliq.. (Ele´ments de la the´orie des jeux (1952), Dunod: Dunod Paris), 5 (1929), re´imprime´en
[22] Guilbaud, G. Th.; Rosenstiehl, P., (Ordres totaux finis. Ordres totaux finis, Mathe´matiques et Sciences de I’Homme XII (1971), Gauthier-Villars: Gauthier-Villars Paris), 71-100
[23] Gra¨tzer, G., (General Lattice Theory (1978), Birkha¨user-Verlag: Birkha¨user-Verlag Stuttgart)
[24] Huang, S.; Tamari, D., Problems of associativity: a simple proof for the lattice property of systems ordered by a semi-associative law, J. Combin. Theory, Se´r. A, 13, 7-13 (1972) · Zbl 0248.06003
[25] Huguet, D., La structure du treillis des polye‘dres de parenthe´sage, Algebra Universalis, 5, 82-87 (1975)
[26] Katrinak, T., The structure of distributive double \(p\)-algebras, regularity and congruences, Algebra Universalis, 3, 238-246 (1973) · Zbl 0276.08005
[27] Lakser, H., Exercices 30 et 31, (Gra¨tzer, G., General Lattice Theory (1978), Birkha¨user-Verlag: Birkha¨user-Verlag Stuttgart), 51
[28] Leclerc, B., A finite Coxeter group whose weak Bruhat order is not symmetric chain, Document CAMS, 074 (Octobre 1991)
[29] C. Le Conte de Poly-Barbut, Communications personnelles, 1986-1990.; C. Le Conte de Poly-Barbut, Communications personnelles, 1986-1990.
[30] Le Conte de Poly-Barbut, C., Automorphismes du permutoe‘dre et votes de Condorcet, Math. Inf. Sci. hum., 111, 73-82 (1990) · Zbl 0721.01005
[31] Le Conte de Poly-Barbut, C., Le diagramme du treillis permutoe“dre est intersection des diagrammes de deux produits directs d”ordres totaux, Math. Inf. Sci. hum., 112, 49-53 (1990) · Zbl 0788.06002
[32] Markowsky, G., Permutation lattices revisited (Janvier 1991), Univ. Maine Computer Science Dept., rapport non publie
[33] Monjardet, B., Treillis d’ordres, (Ordres totaux finis. Ordres totaux finis, Mathe´matiques et Sciences de I’Homme XII (1971), Gauthier-Villars: Gauthier-Villars Paris), 29-45
[34] Monjardet, B., The consequences of Dilworth’s work for lattices with unique irreducible decompositions, (Bogart, K.; Freese, R.; Kung, J., The Dilworth Theorems (1990), Birkha¨user: Birkha¨user Boston), 192-200
[35] Monjardet, B., Ele´ments pour une histoire de la me´diane me´trique, (Moyenne, Milieu et Centre: Histoires et Usages. Moyenne, Milieu et Centre: Histoires et Usages, Coll. Histoire des Sciences et Techniques, \(n^o 5 (1992)\), Editions de I’Ecole des Hautes Etudes en Sciences Sociales), 45-62
[36] Reeg, S.; Weis, W., Properties of Finite Lattices (1990), Darmstadt
[37] Salii, V. N., (Lattices with Unique Complements (1988), American Mathematical Society: American Mathematical Society Providence, R.I.) · Zbl 0632.06009
[38] Savage, I. R., Contributions to the theory of rank order statistics: applications of lattice theory, Rev. Int. Statist. Inst., 32, 52-64 (1964) · Zbl 0134.36403
[39] Stanley, R. P., On the number of reduced decompositions of elements of Coxeter groups, Europ. J. Combin., 5, 359-372 (1984) · Zbl 0587.20002
[40] Stone, M. H., Topological representations of distributive lattices and Brouwerian logics, Casopis Pest. Mat., 67, 1-25 (1937) · Zbl 0018.00303
[41] Tamari, D., Monoides pre´ordonne´s et chaines de Malcev, (The‘se de doctorat (1951), Universite´de Paris) · Zbl 0055.01501
[42] Varlet, J., Congruences dans les treillis pseudo-comple´mente´s, Bull. Soc. R. Sci. Lie‘ge, 9, 623-635 (1963) · Zbl 0118.02403
[43] Varlet, J., Contributionsa“I”e´tude des treillis pseudo-comple´mente´s et des treillis de Stone, Me´m. Soc. R. Sci. Lie‘ge, 8, 1-71 (1963) · Zbl 0113.01803
[44] Varlet, J., A regular variety of type (2, 2, 1, 1, 0, 0), Algebra Universalis, 2, 218-223 (1972) · Zbl 0256.06004
[45] Varlet, J., Structures alge´briques ordonne´es, (Notes d’un se´minaire Universite´de Lie‘ge (1974-1975)), 134
[46] Yanagimoto, T.; Okamoto, M., Partial orderings of permutations and monotonicity of a rank correlation statistic, Ann. Inst. Statist., 21, 489-506 (1969) · Zbl 0208.44704
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.