Course Description

MATH 8041. Matroid Theory I

Code Title Credits Contact
Course Code MATE 8041
Course Title Matroid Theory I
Credits 3
Hours 3 per week
Prerequisites MATH 6150, MATH 8001
Description Fundamental concepts and axioms of matroid theory. Duality in matroid and matroid operations. Vector representation of matroids. The matroid of a graph and graph planarity. Greedy algorithms on matroids. The union of matroids and its rank function. Efficient algorithms for some combinatorial optimization problems (packing, covering, intersection, etc.) on matroids with applications to a variety of combinatorial objects (e.g. graphs, matrices, algebraic dependencies, transversals).
Additional Information