×

The presence of lattice theory in discrete problems of mathematical social sciences. Why. (English) Zbl 1054.91062

Summary: We point out many fields of mathematical social sciences where lattices are present, for instance the discrete resources allocation problems. However, we do not intend to survey the use of lattice theory in such discrete problems. Rather, we present an overview on the ubiquity and polymorphism of finite lattice theory, which accounts for its presence in these problems (like in many others). Indeed, on one hand lattices are on the border of two fundamental mathematical structures, namely algebra and order, and on the other hand they are naturally induced by several other significant mathematical objects like set systems, operators, binary relations or implications. We set out these different aspects and we illustrate them in the case of two significant classes of lattices, the lower locally distributive lattices and the distributive lattices.

MSC:

91B68 Matching models
Full Text: DOI

References:

[1] Adams, E. N., N-trees as nestings: complexity, similarity and consensus, Journal of Classification, 3, 2, 299-317 (1986) · Zbl 0647.62057
[2] Alkan, A., On preferences over subsets and the lattice structure of stable matchings, Review Economic Design, 6, 99-111 (2001) · Zbl 0986.91033
[3] Armstrong, W. W., Dependency structures of data base relationships, Information Processing, 74, 580-583 (1974) · Zbl 0296.68038
[4] Avann, S. P., Locally atomic upper locally distributive lattices, Mathematische Annalen, 175, 320-336 (1968) · Zbl 0157.34203
[5] Barbut, M., Note sur l’algèbre des techniques d’analyse hièrarchique, (Matalon, B., L’analyse hiérarchique (1965), Gauthier-Villars: Gauthier-Villars Paris)
[6] Barbut, M.; Monjardet, B., Ordre et Classification, Algèbre et Combinatoire, tomes I et II (1970), Hachette: Hachette Paris · Zbl 0267.06001
[7] Barthélemy, J. P.; Monjardet, B., The median procedure in cluster analysis and social choice theory, Mathematical Social Science, 1, 235-268 (1981) · Zbl 0486.62057
[8] Barthélemy, J. P.; Janowitz, M. F., A formal theory of consensus, SIAM Journal of Discrete Mathematics, 4, 305-322 (1991) · Zbl 0734.90008
[9] Barthélemy, J. P.; Leclerc, B.; Monjardet, B., Ensembles ordonnés et taxonomie mathématique, Annals of Discrete Mathematics, 23, 523-548 (1984) · Zbl 0566.62051
[10] Behrendt, G., Maximal antichains in partially ordered sets, Ars Combinatoria, C25, 149-157 (1988) · Zbl 0657.06003
[11] Bertet, K., Nebut, M., 2002. Efficient algorithms on the family associated to an implicational system, preprint.; Bertet, K., Nebut, M., 2002. Efficient algorithms on the family associated to an implicational system, preprint. · Zbl 1062.06004
[12] Bilbao, J. M., Cooperative Games on Combinatorial Structures (2000), Kluwer · Zbl 0983.91013
[13] Bilbao, J. M.; Edelman, P. H., The Shapley value on convex geometries, Discrete Applied Mathematics, 103, 1-3, 33-40 (2000) · Zbl 0955.91002
[14] Birkhoff, G., (Lattice Theory (1940), American Mathematical Society: American Mathematical Society Providence), 1967 · Zbl 0063.00402
[15] Birkhoff, G., What can lattices do for you, (Abbot, J. C., Trends in Lattice Theory (1970), Van Nostrand: Van Nostrand New York), 1-40
[16] Blair, C., Every finite distributive lattice is a set of stable matchings, Journal of Cominatorial Theory (A), 37, 353-356 (1984) · Zbl 0546.06009
[17] Boole, G., 1847. The Mathematical Analysis of Logic. Cambridge.; Boole, G., 1847. The Mathematical Analysis of Logic. Cambridge. · Zbl 0041.34803
[18] Buchi, J. R., Finite Automata, their Algebras and Grammars. Towards a Theory of Formal Expressions (1989), Springer · Zbl 0715.68062
[19] Burosch, G.; Demetrovics, J.; Katona, G., The poset of closures as model of changing databases, Order, 4, 30-59 (1987) · Zbl 0648.06004
[20] Caspard, N., A characterization theorem for the canonical basis of a closure operator, Order, 16, 3, 227-230 (1999) · Zbl 0959.06005
[21] Caspard, N.; Monjardet, B., The lattice of closure systems, closure operators and implicational systems on a finite set: a survey, Discrete Applied Mathematics, 127, 2, 241-269 (2003) · Zbl 1026.06008
[22] Crapo, H.; Rota, G. C., On the Foundations of Combinatorial Theory II: Combinatorial Geometries (1970), MIT Press: MIT Press Cambridge, MA · Zbl 0231.05024
[23] Crown, G. D.; Janowitz, M. F.; Powers, R. C., Neutral consensus functions, Mathematical Social Sciences, 25, 3, 231-250 (1993) · Zbl 0774.90006
[24] Davey, B. A.; Priestley, H. A., Introduction to Lattices and Order (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0701.06001
[25] Dedekind, R., Über Zelegungen von Zahlen durch ihre grösten gemeinsamen Teiler, Gesammelte Werke, 2, 103-148 (1900)
[26] Demetrovics, J.; Hua, N. S., Databases, closure operations and Sperner families, (Frank, P.; etal., Extremal Problems for Finite Sets (1991), János Bolyai Mathematical Society: János Bolyai Mathematical Society Budapest), 199-203 · Zbl 0839.68025
[27] Demetrovics, J.; Libkin, L. O.; Muchnik, I. B., Functional dependencies in relational databases: a lattice point of view, Discrete Applied Mathematics, 40, 155-185 (1992) · Zbl 0767.68029
[28] Dilworth, R. P., Lattices with unique irreducible representations, Annals of Mathematics, 41, 771-777 (1940) · Zbl 0025.10202
[29] Doignon, J. P.; Falmagne, J. C., Knowledge Spaces (1999), Springer: Springer Berlin · Zbl 0908.92040
[30] Domenach, F.; Leclerc, B., On the roles of Galois connections in classification, (Schwaiger, M.; Opitz, O., Explanatory Data Analysis in Empirical Research (2002), Springer: Springer Berlin), 31-40
[31] Domenach, F., Leclerc, B., 2003. Closure systems, implicational systems, overhanging relations and the case of hierarchical classification. Mathematics Social Science, In press..; Domenach, F., Leclerc, B., 2003. Closure systems, implicational systems, overhanging relations and the case of hierarchical classification. Mathematics Social Science, In press.. · Zbl 1059.93007
[32] Duntsch, I.; Gediga, G., Rough Set Data Analysis: A Road to Non-Invasive Knowledge Discovery (2000), Methodos Publishers
[33] Duntsch, I.; Gediga, G., A note on the correspondence among entail relations, rough set dependencies and logical consequence, Journal of Mathematical Psychology, 45, 393-401 (2001) · Zbl 0995.06001
[34] Duquenne, V., What can lattices do for experimental designs, Mathematical Social Sciences, 11, 243-281 (1986) · Zbl 0609.62118
[35] Duquenne, V., The core of finite lattice, Discrete Mathematics, 88, 2-3, 133-147 (1991) · Zbl 0736.06012
[36] Duquenne, V., glad (General Lattice Analysis and Design): a Fortran Program for a glad User (1992), Maison des Sciences de l’Homme: Maison des Sciences de l’Homme Paris
[37] Duquenne, V., Models of possessions and lattice analysis, Social Science Information, 2, 253-267 (1995)
[38] Duquenne, V., Latticial structure in data analysis, Theoretical Computer Science, 217, 407-436 (1999) · Zbl 1034.68510
[39] Edelman, P. H.; Jamison, R. E., The theory of convex geometries, Geometriae Dedicata, 19, 247-270 (1985) · Zbl 0577.52001
[40] Edelman, P. H.; Saks, M. E., Combinatorial representations and convex dimension of convex geometries, Order, 5, 1, 23-32 (1988) · Zbl 0659.06005
[41] Faigle, U.; Kern, W., The Shapley value for cooperative games under precedence constraints, International Journal of Game Theory, 21, 249-266 (1992) · Zbl 0779.90078
[42] Fleiner, T., A fixed-point approach to stable matchings and some applications, Mathematics of Operations Research, 28, 1, 103-126 (2003) · Zbl 1082.90096
[43] Gabbay, D. M., Theoretical foundations for non-monotonic reasoning in expert systems, (Apt, K. R., Logics and Models of Concurrent Systems (1985), Springer: Springer Berlin), 439-457 · Zbl 0581.68068
[44] Gale, D.; Shapley, M., College admissions and the stability of marriage, American Mathematical Monthly, 69, 9-15 (1962) · Zbl 0109.24403
[45] Ganter, B.; Wille, R., Formal Concept Analysis, Mathematical Foundations (1999), Springer: Springer Berlin · Zbl 0909.06001
[46] Gilboa, I.; Lehrer, E., Global games, International Journal of Game Theory, 20, 129-147 (1991) · Zbl 0743.90122
[47] Guigues, L.; Duquenne, V., Familles minimales d’implications informatives résultant d’un tableau de données binaires, Mathématiques et Sciences Humaines, 95, 5-18 (1986) · Zbl 1504.68217
[48] Grätzer, G., General Lattice Theory (1991), Birkhäuser Verlag: Birkhäuser Verlag Stuttgart · Zbl 0385.06015
[49] Gusfield, D.; Irving, R. W., The Stable Marriage Problem Structure and Algorithms (1989), MIT Press: MIT Press Cambridge · Zbl 0703.68046
[50] Hausdorff, F., 1914. Grundzüge der Mengenlehere, Leipzig.; Hausdorff, F., 1914. Grundzüge der Mengenlehere, Leipzig. · JFM 45.0123.01
[51] Hertz, P., Über Axiomensysteme für beliebige Satzsysteme, Mathematische Annalen, 101, 457-514 (1929) · JFM 55.0627.01
[52] Jamison-Waldner, R. E., Copoints in antimatroı̈ds, Congressum Numerantium, 29, 535-544 (1980) · Zbl 0463.05005
[53] Janowitz, M. F., An ordinal model for cluster analysis—15 years in retrospect, (Gaul, W.; Pfeifer, D., From Data to Knowledge: Theoretical and Practical Aspects of Classification, Data Analysis and Knowledge Organization (1995), Springer: Springer Berlin), 58-72 · Zbl 0877.62065
[54] Knuth, D., Mariages Stables (1976), Montréal University Press: Montréal University Press Montréal · Zbl 0358.68057
[55] Korte, B.; Lovasz, L.; Schrader, R., Greedoids (1991), Springer: Springer Berlin · Zbl 0733.05023
[56] Koshevoy, G. A., Choice functions and abstract convex geometries, Mathematical Social Sciences, 38, 1, 35-44 (1999) · Zbl 0943.91031
[57] Kuznetsov, S. O., On computing the size of a lattice and related decision problems, Order, 18, 313-321 (2001) · Zbl 0991.06006
[58] Leclerc, B., Lattice valuations, medians and majorities, Discrete Mathematics, 111, 345-356 (1993) · Zbl 0785.06006
[59] Leclerc, B.; Monjardet, B., Latticial theory of consensus, (Barnett, W.; Moulin, H.; Salles, M.; Schofield, N., Social Choice, Welfare and Ethics (1994), Cambridge University Press: Cambridge University Press Cambridge), 239-252 · Zbl 0941.91029
[60] Maier, D., The Theory of Relational Data Bases (1983), Computer Science Press · Zbl 0519.68082
[61] Magnien, C.; Phan, H. D.; Vuillon, L., Characterization of lattices induced by (extended) Chip Firing Games, (Discrete Mathematics and Theoretical Computer Sciences Proceedings (2001)), 229-244 · Zbl 1007.91503
[62] Markowsky, G., The factorization and representation of lattices, Transactions of the American Mathematical Society, 203, 185-200 (1975) · Zbl 0302.06011
[63] Martin, N. M.; Pollard, S., Closure Spaces and Logic (1996), Kluwer · Zbl 0855.54001
[64] Monjardet, B., The consequences of Dilworth’s work on lattices with unique irreducible decompositions, (Bogart, K. P.; Freese, R.; Kung, J., The Dilworth Theorems Selected Papers of Robert P. Dilworth (1990), Birkhäuser: Birkhäuser Boston), 192-201
[65] Monjardet, B.; Raderanirina, V., The duality between the anti-exchange closure operators and the path independent choice operators on a finite set, Mathematical Social Sciences, 41, 2, 131-150 (2001) · Zbl 0994.91012
[66] Monjardet, B., Raderanirina, V., 2003. Lattice of choice functions and consensus problems, Social choice and Welfare, in press.; Monjardet, B., Raderanirina, V., 2003. Lattice of choice functions and consensus problems, Social choice and Welfare, in press. · Zbl 1109.91341
[67] Moore, E.H., 1909. On a form of general analysis with applications to linear differential and integral equations. In: Atti del IV Congr. Int. dei Mat. II. Roma, pp. 98-114.; Moore, E.H., 1909. On a form of general analysis with applications to linear differential and integral equations. In: Atti del IV Congr. Int. dei Mat. II. Roma, pp. 98-114. · JFM 40.0396.01
[68] Morvan, M.; Nourine, L., Simplicial elimination schemes, extremal lattices and maximal antichain lattices, Order, 13, 2, 159-173 (1996) · Zbl 0859.06005
[69] Nicoletti, G.; White, N., Axioms systems, Theory of Matroids (1986), Cambridge University Press: Cambridge University Press Cambridge
[70] Nourine, L., 2000. Une structuration algorithmique de la théorie des treillis, thèse d’habilitation, Université de Montpellier II.; Nourine, L., 2000. Une structuration algorithmique de la théorie des treillis, thèse d’habilitation, Université de Montpellier II.
[71] Novotny, M., Dependence spaces of information systems, (Orlowska, E., Incomplete Information. Rough Set Analysis (1997), Physica Verlag: Physica Verlag Heidelberg), 193-246
[72] Novotny, J.; Pawlak, Z., Algebraic theory of independence in information systems, Fundamenta Informaticae, 14, 454-476 (1991) · Zbl 0727.68118
[73] Novotny, J.; Novotny, M., Notes on the algebraic approach to information systems, Fundamenta Informaticae, 16, 263-273 (1992) · Zbl 0762.68058
[74] (Orlowska, E., Incomplete Information. Rough Set Analysis (1997), Physica Verlag: Physica Verlag Heidelberg) · Zbl 0878.00031
[75] Pawlak, Z., Rough sets, International Journal Computing and Information Science, 11, 341-356 (1982) · Zbl 0501.68053
[76] Peirce, C. S., On the algebra of logic, American Journal of Mathematics, 3, 15-57 (1880) · JFM 12.0041.01
[77] Peirce, C. S., On the logic of number, American Journal of Mathematics, 4, 85-95 (1881) · JFM 13.0055.02
[78] Reuter, K., The jump number and the lattice of maximal antichains, Discrete Mathematics, 88, 289-307 (1991) · Zbl 0731.06003
[79] Roth, A. E.; Sotomayor, M., Two Sided Matching: A Study in Game-Theoretic Modeling and Analysis (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0726.90003
[80] Schröder, E., (Vorlesungen ûber die Algebra der Logik, vol. 1 (1890), Teubner Verlag: Teubner Verlag Leipzig), 191-281
[81] Scott, D. S., Completeness and axiomatizability in many-valued logics, (Henkin, L.; etal., Proceedings of the Tarski Symposium, Proceedings of Symposia in Pure Mathematics 25 (1974), American Mathematical Society: American Mathematical Society Providence), 411-435 · Zbl 0318.02021
[82] Scott, D. S., Domains for denotational semantics, (Nielsen, M.; Schmidt, E. T., Automata, Languages and Programming, Lecture Notes in Computer Science 140 (1982), Springer: Springer Berlin, Heidelberg), 577-613 · Zbl 0495.68025
[83] Speed, T. P., What is analysis of variance, The Annals of Statistics, 15, 885-941 (1987) · Zbl 0637.62070
[84] Stern, M., Semimodular Lattices, Encyclopedia of Mathematics (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0957.06008
[85] Tarski, A., Fundamentale Begriffe der Methodologie der Deductiven Wissenchaften, Monatshefte fur Mathematik und Physik, 37, 361-404 (1930) · JFM 56.0046.02
[86] (White, N., Theory of Matroids (1986), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0579.00001
[87] Wild, M., A theory of finite closure spaces based on implications, Advances in Mathematics, 108, 1, 118-139 (1994) · Zbl 0863.54002
[88] Wild, M., 1995. Computations with finite closure systems and implications. In: Du, Z., Li, M., (Eds.), Computing and Combinatorics, Lecture Notes in Computer Science 959. Springer, Berlin, Heidelberg, pp. 111-120.; Wild, M., 1995. Computations with finite closure systems and implications. In: Du, Z., Li, M., (Eds.), Computing and Combinatorics, Lecture Notes in Computer Science 959. Springer, Berlin, Heidelberg, pp. 111-120. · Zbl 1527.68148
[89] Wille, R., Restructuring lattice theory: an approach based on hierarchies of concepts, (Rival, I., Ordered Sets (1982), D. Reidel: D. Reidel Dordrecht), 445-470 · Zbl 0491.06008
[90] Winksel, G.; Larsen, K. G., Using information systems to solve domain equations recursively, (Kahn, G.; Plotkin, G. D., Lecture Notes in Computer Science 173 (1984), Springer: Springer Berlin, Heidelberg), 109-130 · Zbl 0539.68019
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.