×

Matroids on convex geometries (cg-matroids). (English) Zbl 1114.52018

Summary: We consider matroidal structures on convex geometries, which we call cg-matroids. The concept of a cg-matroid is closely related to but different from that of a supermatroid introduced by Dunstan, Ingleton, and Welsh in 1972. Distributive supermatroids or poset matroids are supermatroids defined on distributive lattices or sets of order ideals of posets. The class of cg-matroids includes distributive supermatroids (or poset matroids). We also introduce the concept of a strict cg-matroid, which turns out to be exactly a cg-matroid that is also a supermatroid. We show characterizations of cg-matroids and strict cg-matroids by means of the exchange property for bases and the augmentation property for independent sets. We also examine submodularity structures of strict cg-matroids.

MSC:

52C99 Discrete geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aizerman, M. A.; Malishevski, A. M., General theory of best variants choice: some aspects, IEEE Trans. Automat. Control, 26, 1030-1040 (1981) · Zbl 0466.90002
[2] Ando, K., Extreme point axioms for closure spaces, Discrete Math, 306, 3181-3188 (2006) · Zbl 1110.54001
[3] Barnabei, M.; Nicoletti, G.; Pezzoli, L., The symmetric exchange property for poset matroids, Adv. in Math., 102, 230-239 (1993) · Zbl 0793.05035
[4] Barnabei, M.; Nicoletti, G.; Pezzoli, L., Matroids on partially ordered sets, Adv. in Appl. Math., 21, 78-112 (1998) · Zbl 0908.05025
[5] Danilov, V. I.; Koshevoy, G. A., Mathematics of Plott choice functions, Math. Social Sci., 49, 245-272 (2005) · Zbl 1115.91022
[6] Dietrich, B. L., A circuit set characterization of antimatroids, J. Combin. Theory Ser. B, 43, 314-321 (1987) · Zbl 0659.05036
[7] F.D.J. Dunstan, A.W. Ingleton, D.J.A. Welsh, Supermatroids, in: Proceedings of the Conference on Combinatorial Mathematics Mathematical Institue Oxford, 1972, Combinatorics (1972) 72-122.; F.D.J. Dunstan, A.W. Ingleton, D.J.A. Welsh, Supermatroids, in: Proceedings of the Conference on Combinatorial Mathematics Mathematical Institue Oxford, 1972, Combinatorics (1972) 72-122.
[8] Edelman, P. H.; Jamison, R. E., The theory of convex geometries, Geom. Dedicata, 19, 247-270 (1985) · Zbl 0577.52001
[9] Edmonds, J., Submodular functions, matroids, and certain polyhedra, (Guy, R.; Hanani, H.; Sauer, N.; Schönheim, J., Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications (1970), Gordon and Breach: Gordon and Breach New York), 69-87
[10] Emelichev, V. A.; Ovchinnikov, V. G., Symmetric supermatroids, Dokl. Akad. Nauk BSSR, 27, 389-391 (1983), (in Russian) · Zbl 0531.05028
[11] V. A. Emelichev, V. G. Ovchinnikov, On the theory of optimization on antichains having the Steinitz exchange property, Kibernetika (2) (1985) 55-58 (in Russian).; V. A. Emelichev, V. G. Ovchinnikov, On the theory of optimization on antichains having the Steinitz exchange property, Kibernetika (2) (1985) 55-58 (in Russian). · Zbl 0587.90098
[12] Faigle, U., Geometries on partially ordered sets, J. Combin. Theory Ser. B, 28, 26-51 (1980) · Zbl 0359.05018
[13] U. Faigle, On supermatroids with submodular rank function, Algebraic Methods in Graph Theory, vol. I, Szeged, 1978, Colloq. Math. Soc. János Bolyai 25 (1981) 149-158.; U. Faigle, On supermatroids with submodular rank function, Algebraic Methods in Graph Theory, vol. I, Szeged, 1978, Colloq. Math. Soc. János Bolyai 25 (1981) 149-158.
[14] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Methods, 7, 433-444 (1986) · Zbl 0591.05056
[15] S. Fujishige, Submodular Functions and Optimization, second ed., Elsevier, Amsterdam, 2005, Ann. Discrete Math. 58 (2005).; S. Fujishige, Submodular Functions and Optimization, second ed., Elsevier, Amsterdam, 2005, Ann. Discrete Math. 58 (2005). · Zbl 1119.90044
[16] Hildenbrandt, R., Parametric properties of the transportation problem and relations to supermatroids, Optimization, 39, 165-189 (1997) · Zbl 0872.90063
[17] Korte, B.; Lovász, L., The intersection of matroids and antimatroids, Discrete Math., 73, 143-157 (1988/1989) · Zbl 0726.05027
[18] B. Korte, L. Lovász, R. Schrader, Greedoids, Algorithms Combin. 4 (1991).; B. Korte, L. Lovász, R. Schrader, Greedoids, Algorithms Combin. 4 (1991).
[19] Koshevoy, G. A., Choice functions and abstract convex geometries, Math. Social Sci., 38, 35-44 (1999) · Zbl 0943.91031
[20] Kovalëv, M. M., The partial-order method, Dokl. Akad. Nauk BSSR, 24, 113-116 (1980), (in Russian) · Zbl 0434.90078
[21] Kovalëv, M. M., Maximization of convex functions on supermatroids, Dokl. Akad. Nauk BSSR, 27, 584-587 (1983), (in Russian) · Zbl 0517.05021
[22] Kovalëv, M. M.; Milanov, P., Monotone functions of multi-valued logic and supermatroids, Zh. Vychisl. Mat. Mat. Fiz., 24, 786-790 (1984), (in Russian) · Zbl 0576.90071
[23] Lovász, L., Submodular functions and convexity, (Bachem, A.; Grötschel, M.; Korte, B., Mathematical Programming—the State of the Art (1983), Springer: Springer Berlin), 235-257
[24] Moulin, H., Choice functions over a finite set: a summary, Soc. Welf., 2, 147-160 (1985) · Zbl 0576.90004
[25] Oxley, J., Matroid Theory (1992), Oxford University Press: Oxford University Press Oxford · Zbl 0784.05002
[26] Peled, U. N.; Srinivasan, M. K., Poset matching—a distributive analog of independent matching, Discrete Math., 114, 403-424 (1993) · Zbl 0783.05037
[27] Pfaltz, J. L., Closure lattices, Discrete Math., 154, 217-236 (1996) · Zbl 0852.06002
[28] Tardos, É., An intersection theorem for supermatroids, J. Combin. Theory Ser. B, 50, 150-159 (1990) · Zbl 0727.05016
[29] Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press London · Zbl 0343.05002
[30] N. White (Ed.), Theory of Matroids, Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge University Press, Cambridge, 1986.; N. White (Ed.), Theory of Matroids, Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge University Press, Cambridge, 1986.
[31] N. White (Ed.), Combinatorial Geometries, Encyclopedia of Mathematics and its Applications, vol. 29, Cambridge University Press, Cambridge, 1987.; N. White (Ed.), Combinatorial Geometries, Encyclopedia of Mathematics and its Applications, vol. 29, Cambridge University Press, Cambridge, 1987.
[32] Whitney, H., On the abstract properties of linear dependence, Amer. J. Math., 57, 509-533 (1935) · JFM 61.0073.03
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.