Matroids on convex geometries (cg-matroids)
- 作者：Satoru Fujishige ; Gleb A. Koshevoy ; Yoshio Sano
- 关键词：Matroids ; Convex geometries ; Base exchange property ; Supermatroids
- 刊名：Discrete Mathematics
- 出版年：2007
- 期刊代码：47_0012365x
- 类别：cp
- 出版时间：6 July 2007
- 卷：307
- 期：15
- 页码：1936-1950
- 文件大小：249 K
摘要
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.