KAIST Discrete Math Seminar

The notion of a matroid was introduced by H. Whitney in 1935 as an abstraction of “linear independence” in a vector space. In 1960’s, J. Edmonds found that matroids are closely related to an efficient algorithm. After then, many researchers have studied and extended Matroid Theory. In 2007, S. Fujishige, G. A. Koshevoy, and Y. Sano introduced cg-matroids as an generalization of matroids. They defined a matroid-like structure on an abstract convex geometry, where the notion of an abstract convex geometry was introduced by P. H. Edelman and R. E. Jamison in 1985. In this talk, I will introduce the theory of cg-matroids. In particular, I will talk about the definition and some examples of cg-matroids, some combinatorial properties and characterization of cg-matroids, and the relationship between cg-matroids and the greedy algorithm.