Teorie matroidů / Matroid Theory - NDMI065

Annotation:
Introduction to matroid theory - definitions (independent sets, basis, cycles, rank function), operations on matroids (duality and minors), matroidal connectivity, classes of matroids and their representations.

Syllabus:
Definitions and basic examples.
Duality and minors.
Connectivity of matroids and comparsion with graph connectivity.
Matroid intersection theorem and its applications.
Representability, representable, binary and regular matroids.
Graphic matroids. Algorithmic aspects of matroids.

Literature:
Daniel Král', Ondřej Pangrác: Introduction to Matroid Theory (Lecture Notes), ITI series 2009-430 (errata),
James Oxley: Matroid Theory,
related scientific papers ...

Lecture notes:

• Chapter 1 - Definitions and basic examples.
• Chapter 2 - Duality and minors.
• Chapter 3 - Matroid algorithms.
• Chapter 4 - Applications of matroid intersection theorem.
• Chapter 5 - Connectivity.
• Chapter 6 - Representability.
• Chapter 7 - Graphic matroids.