Instructors: Nick Brettell , Stéphan Thomassé and Nicolas Trotignon
Objective: Learn about matroids, through the book Matroid Theory, by James Oxley, Oxford University Press, 2011
Outline:
1) Introduction to matroids (Partition matroids, Graphic matroids, Representable matroids), and the Greedy Algorithm
(+ Independent set definition).
Section 1.8 of Oxley2012 (pp58-63)
Also, Preliminaries, Sections 1.1-1.4 (pp 1-30)
2) Graphic matroids, Minors, Binary matroids (+ Circuit definition).
Section 3.1 of Oxley2012 (pp100-109)
Section 9.1 of Oxley2012 (pp344-353)
3) Duality
(+ Bases definition).
Oxley2012 section 2.1-2.3 (pp 64-93)
4) Representability.
Section 6.1, 6.3-6.5 of Oxley2012 (pp158-169,176-204)
Also, Preliminaries, Sections 1.1-1.4 (pp 1-30)
5) Geometric representations and Connectivity.
Section 1.5 (pp32-42)
Section 4 (pp118-134)
Section 8.1-8.6 (pp291-331) of Oxley2012
6) Polymatroids.
Welsh1976 Chapter 18
7) Regular matroids, Seymour's Decomposition theorem.
Section 6.6 of Oxley2012 (pp204-210)
Section 10.1 of Oxley2012 (pp372-380)
Section 13 of Oxley2012 (pp489-523)