On the rank functions of $\mathcal{H}$-matroids

Year 2016, , 7 - 11, 11.01.2016

Yoshio Sano

https://doi.org/10.13069/jacodesmath.26764

Abstract

The notion of $\mathcal{H}$-matroids was introduced by U. Faigle and S. Fujishige in 2009 as a general model for matroids and the greedy algorithm. They gave a characterization of $\mathcal{H}$-matroids by the greedy algorithm. In this note, we give a characterization of some $\mathcal{H}$-matroids by rank functions.

Keywords

Matroid, H-Matroid, Simplicial complex, Rank function

2010 MSC: 05B35, 90C27

Abstract

References

• U. Faigle, S. Fujishige, A general model for matroids and the greedy algorithm, Math. Program. Ser.
• A 119(2) (2009) 353–369.
• S. Fujishige, Submodular functions and optimization, Annals of Discrete Mathematics, Elsevier, Amsterdam, 2005.
• S. Fujishige, G. A. Koshevoy, Y. Sano, Matroids on convex geometries (cg-matroids), Discrete Math. 307(15) (2007) 1936–1950.
• B. Korte, L. Lovász, R. Schrader, Greedoids, Algorithms and combinatorics, Vol. 4, Springer-Verlag, Berlin, 1991.
• J. Oxley, Matroid theory, Oxford University Press, Oxford, 1992.
• Y. Sano, Rank functions of strict cg-matroids, Discrete Math. 38(20) (2008) 4734–4744.
• Y. Sano, Matroids on convex geometries: subclasses, operations, and optimization, Publ. Res. Inst.
• Math. Sci. 47(3) (2011) 671–703.
• A. Schrijver, Combinatorial optimization. Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24, Springer-Verlag, Berlin, 2003.
• D. J. A. Welsh, Matroid theory, Academic Press, London, 1976.
• H. Whitney, On the abstract properties of linear dependence, Amer. J. Math. 57(3) (1935) 509–533.