Yoshio Sano (佐野良夫), Matroids on convex geometries

Matroids on convex geometries
Yoshio Sano (佐野良夫)
Department of Mathematics, POSTECH, Pohang
2010/5/14 Fri 4PM-5PM

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.


Comments are closed.