Matroid theory

Description
Class meetings: Lecture Mon 10:15-11:45 (Room 3.517) and Problem-solving class Tue 10:15-11:45 (Room 3.517). If you have any questions, you can email me to set up an appointment.

Grading: At the end of the semester, there will be an oral exam covering the lecture material; this determines the final course grade. The problem-solving sessions are taught by András Imolay (imolay.andras@gmail.com). Each week, a problem sheet is handed out in class and posted online; it usually includes exercises, one homework problem, one challenging problem, and sometimes a research question. We discuss the previous week’s problems in class, so students are expected to work on them in advance; working together is encouraged, but all solutions must be written up independently. Homework is worth up to 2 points, challenging problems up to 4 points, and presenting a solution in class 2 points; research questions may earn extra points. There are two tests during the semester, each with 7 problems worth 10 points each. Homework must be submitted within one week and challenging problems within three weeks, either electronically (LaTeX) or on paper. Final grades are based on total points: below 50 gives grade 1, 50-69 grade 2, 70-89 grade 3, 90-109 grade 4, 110-129 grade 5, with points above this counting as extra credit; bonus points may be given for active participation and attendance.

Lecture notes
A. Frank. Connections in Combinatorial Optimization.
A. Frank. Matroidelmélet (in Hungarian).

Week 1
We recalled the proof of Kruskal’s algorithm for finding a maximum-weight spanning tree in an edge-weighted graph, and observed that the same algorithm applies to a weighted set of vectors as well. We then introduced matroids via the independence axioms, gave an overview of the basic definitions, and discussed the circuit axioms (up to Section 1.3.2 of the lecture notes and Section 5.1 of Frank’s book).

Week 2
We concluded our discussion of the circuit axioms and defined the components of a matroid. We then reviewed the basis and rank axioms, defined the linear extension of a set function, and proved the generalized submodular inequality. We also discussed various matroid oracles and the relations between them (up to Section 1.5.2 of the lecture notes and Sections 5.2, 5.3, 5.5.1 and 12.2 of Frank’s book).

Week 3
We discussed basic matroid operations such as series and parallel extensions, truncation, and elongation. We defined the dual of a matroid and proved that the dual of a linear matroid is also linear. We then considered the restriction (deletion) and contraction operations, leading to the notion of matroid minors. We concluded the lecture by proving that the homomorphic image of a matroid is again a matroid, and as a corollary, we introduced the union of matroids (Section 2.1 of the lecture notes and Sections 5.4.1, 5.4.2 and 5.4.3 of Frank’s book).

Week 4
We proved Rado’s theorem on the maximum size of an M-independent matching in bipartite graphs. As a corollary, we deduced the rank function of the homomorphic image of a matroid, and used this for proving the matroid union theorem. We then considered matroid classes defined by families of sets. In particular, we gave a hypergraph characterization of paving matroids (Sections 2.2 and 2.4.2 of the lecture notes and Sections 5.3.1, 5.4.1 and 13.1.1 of Frank’s book ).

Week 5
We considered matroids defined by graphs: transversal matroids, deltoids, gammoids, and matching matroids. We proved that the dual of a gammoid is also a gammoid (Section 2.3 of the lecture notes and Section 5.4.4 of Frank’s book).