×

Resolutions of convex geometries. (English) Zbl 1477.52001

Summary: Convex geometries [P. H. Edelman and R. E. Jamison, Geom. Dedicata 19, 247–270 (1985; Zbl 0577.52001)] are finite combinatorial structures dual to union-closed antimatroids or learning spaces. We define an operation of resolution for convex geometries, which replaces each element of a base convex geometry by a fiber convex geometry. Contrary to what happens for similar constructions – compounds of hypergraphs, as in [M. Chein et al., Discrete Math. 37, 35–50 (1981; Zbl 0478.05071)], and compositions of set systems, as in [R. H. Möhring and F. J. Radermacher, Ann. Discrete Math. None, 257–356 (1984; Zbl 0567.90073)] –, resolutions of convex geometries always yield a convex geometry.
We investigate resolutions of special convex geometries: ordinal and affine. A resolution of ordinal convex geometries is again ordinal, but a resolution of affine convex geometries may fail to be affine. A notion of primitivity, which generalize the corresponding notion for posets, arises from resolutions: a convex geometry is primitive if it is not a resolution of smaller ones. We obtain a characterization of affine convex geometries that are primitive, and compute the number of primitive convex geometries on at most four elements. Several open problems are listed.

MSC:

52A01 Axiomatic and generalized convexity
05B25 Combinatorial aspects of finite geometries
06A07 Combinatorics of partially ordered sets
51D20 Combinatorial geometries and geometric closure systems
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Adaricheva, K., 2014. Algebraic convex geometries revisited.arXiv:1406.3721 · Zbl 1282.05022
[2] Adaricheva, K., and J. B. Nation, 2016a. Lattices of algebraic subsets and implicational classes. In G. Gr¨atzer and F. Wehrung, eds.,Lattice Theory: Special topics and applications, vol. 2, ch. 4, pp. 103-151. Birkh¨auser/Springer, Cham. · Zbl 1375.06005
[3] Adaricheva,K.,and J. B. Nation,2016b.Convex geometries.In G. Gr¨atzer and F. Wehrung, eds.,Lattice Theory: Special topics and applications, vol. 2, ch. 5, pp. 153-179. Birkh¨auser/Springer, Cham.
[4] Adaricheva, K. and J. B. Nation, 2016c.Bases of closure systems.In G. Gr¨atzer and F. Wehrung, eds.,Lattice Theory: Special topics and applications, vol. 2, ch. 6, pp. 181-213. Birkh¨auser/Springer, Cham. · Zbl 1403.06004
[5] Adaricheva, K., and J. B. Nation, 2016d. A class of infinite convex geometries.The Electronic Journal of Combinatorics23: #1.56.
[6] Aizerman, M. A., and A. V. Malishevski, 1981. General theory of best variants choice: some aspects.IEEE Transactions on Automatic Control26: 1030-1040. · Zbl 0466.90002
[7] Ando, K., 2006. Extreme point axioms for closure spaces.Discrete Mathematics306: 3181-3188. · Zbl 1110.54001
[8] Bang-Jensen, J., and G. Gutin, 2001.Digraphs. Springer Monographs in Mathematics. Springer, London.
[9] Bonizzoni, P., and G. Della Vedova, 1999. An algorithm for the modular decomposition of hypergraphs.Journal of Algorithms32: 65-86. · Zbl 0942.68095
[10] Boudabbous, I., and P. Ille. Ultracritical and hypercritical binary structures.Discrete Mathematics311: 1397-1409. · Zbl 1238.05103
[11] Boudabbous, Y., I. Zaguia, and N. Zaguia, 2010. Prime orders all of whose prime suborders are selfdual.Order27: 283-300. · Zbl 1207.06001
[12] Cantone, D., A. Giarlotta, S. Greco, and S. Watson, 2016.pm, nq-rationalizable choices.Journal of Mathematical Psychology73: 12-27. · Zbl 1396.91104
[13] Cantone, D., A. Giarlotta, and S. Watson, 2021. Choice resolutions.Social Choice and Welfare 56: 713-753. · Zbl 1471.91095
[14] Carpentiere, D., 2019.Resolution of Convex Geometries. Bachelor Thesis, University of Catania, Italy.
[15] the electronic journal of combinatorics28(4)(2021), #P4.2635
[16] Chernoff, H., 1954. Rational selection of decision functions.Econometrica22: 422-443. · Zbl 0059.12602
[17] Chein, M., M. Habib, and M. C. Maurer, 1981. Partitive hypergraphs.Discrete Mathematics 37: 35-50. · Zbl 0478.05071
[18] Chudnovsky, M., R. Kim, S.-I. Oum, and P. Seymour. Unavoidable induced subgraphs in large graphs with no homogeneous sets.Journal of Combinatorial Theory, Series B118: 1-12. · Zbl 1332.05112
[19] Danilov, V., and G. Koshevoy, 2009. Choice functions and extensive operators.Order26: 69-94. · Zbl 1160.05001
[20] D¨orfler, W., 1971. ¨Uber dieX-Summe von gerichteten Graphen.Archiv der Mathematik (Basel), 22: 24-36.
[21] Doignon, J.-P., and J.-C. Falmagne, 1999.Knowledge Spaces. Springer-Verlag, Berlin.
[22] Echenique, F., 2007. Counting combinatorial choice rules.Games and Economic Behavior58: 231-245. · Zbl 1168.91348
[23] Edelman, P. H., and R. E. Jamison, 1985. The theory of convex geometries.Geometriae Dedicata 19: 247-270. · Zbl 0577.52001
[24] Enright, J., 2001 The computational complexity of antimatroid properties.Advances in Applied Mathematics26: 23-46. · Zbl 0974.68065
[25] Falmagne J.-C., and J.-P. Doignon, 2011.Learning Spaces. Springer-Verlag, Berlin.
[26] Farber, M., and R. E. Jamison, 1986. Convexity in graphs and hypergraphs.SIAM Journal on Algebraic Discrete Methods7: 433-444. · Zbl 0591.05056
[27] Fedor˘cuk, V. V., 1968. Bicompacta with noncoinciding dimensionalities.Soviet Mathematics Doklady9: 1148-1150. · Zbl 0186.27003
[28] Foldes, S., and S. Radeleczki, 2016. Interval decomposition lattices are balanced.Demonstratio Mathematica49: 271-281. · Zbl 1352.06005
[29] Giarlotta, A., 2019. New trends in preference, utility, and choice: from a mono-approach to a multi-approach. In M. Doumpos, J. R. Figueira, S. Greco, and C. Zopounidis (eds.),New Perspectives in Multiple Criteria Decision Making, pp. 3-80. Springer, Cham.
[30] Giarlotta, A., and S. Watson, 2014. The pseudo-transitivity of preference relations: strict and weakpm, nq-Ferrers properties.Journal of Mathematical Psychology58: 45-54. · Zbl 1298.91082
[31] Giarlotta, A., and S. Watson, 2018. Strictpm,1q-Ferrers properties.Journal of Mathematical Psychology82: 84-96. · Zbl 1403.91123
[32] Goecke, O., B. Korte, and L. Lov´asz, 1989. Examples and algorithmic properties of greedoids. InCombinatorial Optimization (Como, 1986), vol. 1403 ofLecture Notes in Mathematics, pp. 113-161. Springer, Berlin.
[33] Gr¨atzer, G., 2011.Lattice Theory: Foundation. Birkh¨auser/Springer Basel AG, Basel.
[34] the electronic journal of combinatorics28(4)(2021), #P4.2636
[35] Guillet, A., J. Leblet, and J.-X. Rampon. Faithful extension on finite order classes.The Australasian Journal of Combinatorics69: 1-17. · Zbl 1423.06007
[36] Habib, M., F. de Montgolfier, L. Mouatadid, and M. Zou, 2019 A general algorithmic scheme for modular decompositions of hypergraphs and applications. InCombinatorial algorithms, vol. 11638 ofLecture Notes in Computer Science, pp. 251-264. Springer, Cham. · Zbl 07173536
[37] Harzheim, E., 2005.Ordered Sets, vol. 7 ofAdvances in Mathematics. Springer, New York. · Zbl 1072.06001
[38] Hiraguchi, T., 1951. On the dimension of partially ordered sets.Science Reports of Kanazawa University1: 77-94. · Zbl 0200.00013
[39] Hoffmann, U., and K. Merckx, 2018. A universality theorem for allowable sequences with applications.arXiv:1801.05992
[40] Ille, P., 2005. La d´ecomposition intervallaire des structures binaires.Gazette des Math´ematiciens 104: 39-58. · Zbl 1154.03309
[41] Ille, P., and R. Villemaire, 2014. Recognition of prime graphs from a prime subgraph.Discrete Mathematics327: 76-90. · Zbl 1288.05180
[42] Jamison-Waldner, R. E., 1982. A perspective on abstract convexity: classifying alignments by varieties. InConvexity and Related Combinatorial Geometry (Norman, Okla., 1980), vol. 76 ofLecture Notes in Pure and Applied Mathematics, pp. 113-150. Dekker, New York.
[43] Johnson, M. and R. Dean, 1996.An algebraic characterization of path independent choice functions.InThird International Meeting of the Society for Social Choice and Welfare, Maastricht, The Netherlands.
[44] Johnson, M. and R. Dean, 2001. Locally complete path independent choice functions and their lattices.Mathematical Social Sciences42: 53-87. · Zbl 0987.91024
[45] Kashiwabara, K., M. Nakamura, and Y. Okamoto, 2005. The affine representation theorem for abstract convex geometries.Computational Geometry30: 129-144. · Zbl 1113.52002
[46] Korte, B., L. Lov´asz, and R. Schrader, 1991.Greedoids, vol. 4 ofAlgorithms and Combinatorics. Springer-Verlag, Berlin. · Zbl 0733.05023
[47] Koshevoy, G. A., 1999. Choice functions and abstract convex geometries.Mathematical Social Sciences38: 35-44. · Zbl 0943.91031
[48] Levi, F. W., 1951. On Helly’s theorem and the axioms of convexity.Journal of the Indian Mathematical Society15(Pt A): 65-76. · Zbl 0044.19101
[49] Mao, H., 2017. Geometries, independence spaces and infinite antimatroids.Matematika (Johor) 33: 105-111.
[50] Mao, H., and S. Liu, 2012. On antimatroids of infinite character.Mathematica Pannonica23: 257-266. · Zbl 1289.05039
[51] the electronic journal of combinatorics28(4)(2021), #P4.2637
[52] Marti, J., and R. Pinosio, 2020. A discrete duality between nonmonotonic consequence relations and convex geometries.Order37: 151-171. · Zbl 1481.03011
[53] M´endez, M. A., 2015.Set Operads in Combinatorics and Computer Science. Springer Briefs in Mathematics. Springer, Cham.
[54] Merckx, K., 2013.Descriptions Lin´eaires de Polytopes Associ´es aux Antimatro¨ıdes. Master Thesis, Universit´e Libre de Bruxelles, Belgium.
[55] M¨ohring, R. H., 1985. Algorithmic aspects of the substitution decomposition in optimization over relations, sets systems and Boolean functions.Annals of Operations Research4: 195-225.
[56] M¨ohring, R. H., and F. J. Radermacher, 1984. Substitution decomposition for discrete structures and connections with combinatorial optimization. InAlgebraic and Combinatorial Methods in Operations Research, vol. 95 ofNorth-Holland Mathematics Studies, pp. 257-355, NorthHolland, Amsterdam.
[57] Monjardet, B., 1985. A use for frequently rediscovering a concept.Order1: 415-417. · Zbl 0558.06010
[58] Monjardet, B., 1990. The consequences of Dilworth’s work on lattices with unique irreducible decompositions. InThe Dilworth Theorems: Selected theorems of Robert P. Dilworth (Contemporary Mathematicians), pp. 192-199. Birkh¨auser Boston, MA.
[59] Monjardet, B., 2008. Statement of precedence and a comment on IIA terminology.Games and Economic Behavior, 62: 736-738. · Zbl 1141.91010
[60] Monjardet, B., and V. Raderanirina, 2001. The duality between the anti-exchange closure operators and the path independent choice operators on a finite set.Mathematical Social Science 41: 131-150. · Zbl 0994.91012
[61] Monteiro, L. F., S. Savini, and I. Viglizzo, 2017. Hasse diagrams of non-isomorphic posets with nelements, 2ďnď7,and the number of posets with 10 elements, without the aid of any computer program.arXiv:1710.10343
[62] Moulin, H., 1985. Choice functions over a finite set: a summary.Social Choice and Welfare2: 147-160. · Zbl 0576.90004
[63] Plott, C. R., 1973. Path independence, rationality, and social choice.Econometrica41: 1075- 1091. · Zbl 0297.90017
[64] Samuelson, P., 1938. A note on the pure theory of consumers’ behavior.Economica5: 61-71.
[65] Schmerl, J. H., and W. T. Trotter, 1993. Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures.Discrete Mathematics113: 191-205. · Zbl 0776.06002
[66] Schr¨oder, B., 2016.Ordered Sets: An introduction with connections from combinatorics to topology. Birkh¨auser/Springer, second edition.
[67] Sierksma, G., 1984. Exchange properties of convexity spaces. In M. Rosenfeld and J. Zaks, editors,Annals of Discrete Mathematics (20): Convexity and Graph Theory, vol. 87 ofNorthHolland Mathematics Studies, pp. 293-305. North-Holland. · Zbl 0563.52003
[68] the electronic journal of combinatorics28(4)(2021), #P4.2638
[69] Steinbach, P., 1990.Field Guide to Simple Graphs. Design Lab, 1990, Albuquerque TechnicalVocational Institute, Albuquerque, NM.
[70] Suzumura, K., 2016.Choice, Preferences, and Procedures: A rational choice theoretic approach. Harvard University Press, Cambridge, MA.
[71] Trotter, W. T., 1992.Combinatorics and Partially Ordered Sets: Dimension theory. The Johns Hopkins University Press, Baltimore, MD. · Zbl 0764.05001
[72] Uznanski,P.,2013.https://paracombinatorics.wordpress.com/2013/04/19/ enumeration-of-antimatroids-part-iv/(consulted on October 27, 2020).
[73] Wahl, N., 2001. Antimatroids of finite character.Journal of Geometry70: 168-175. · Zbl 0990.52001
[74] Watson, S., 1992. The construction of topological spaces: planks and resolutions. In M. Husek and J. van Mill (eds.),Recent Progress in General Topology, North-Holland, Amsterdam, pp. 673-757. · Zbl 0803.54001
[75] the electronic journal of combinatorics28(4)(2021), #P4
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.