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).

Week 6
We proved the Berge-Tutte formula, using Gallai’s lemma on factor-critical graphs. Then we characterized the independent sets of the matching matroid, and then proved the rank formula (Section 2.3.2 of the lecture notes).

Week 7
We discussed how the rank axioms can be relaxed and how matroids can be defined via polymatroid functions, submodular functions, and intersecting submodular functions (Section 2.5 of the lecture notes and Sections 5.5.6 and 13.4 of Frank’s book).

Week 8
We finished the discussion of matroids defined by set functions, and then proved Edmonds’ matroid intersection theorem using the matroid union rank formula (Sections 2.5 and 3.3.1 of the lecture notes and Sections 13.4 of Frank’s book).

Week 9
We discussed Edmonds’ matroid intersection algorithm and the matroid union algorithm of Edmonds and Fulkerson (Sections 3.1.2 and 4.1.2 of the lecture notes and Sections 13.1.2 and 13.3.1 of Frank’s book).

Week 10
We proved the weight-splitting theorem on the maximum weight of a common basis in two matroids, and provided an algorithm that, for each value of $k$ between 0 and the rank, finds a maximum-weight common independent set of size $k$ (Section 3.2.3 of the lecture notes and Section 13.2.2 of Frank’s book).

Week 11
Using the the weight-splitting theorem on maximum-weight common bases, we derived an analogous result for the maximum weight of a common independent set. We also showed that if the total change of the weight function is $\Delta$, then the weight functions in an optimal splitting can be chosen to be $\Delta$-narrow. We further discussed some applications of matroid intersection and union: minimum-cost $k$-edge connected orientations and matroid union of different weight functions (Sections 3.2.1 and 3.2.2, and Lemma 3.3.11 of the lecture notes and Section 13.2.1 of Frank’s book).

Week 12
We showed that deciding if the ground set of two matroids can be partitioned into two common bases is oracle hard, and discussed the relation of this program to three matroid intersection. Then, as applications of (weighted) matroid intersection, we characterized the maximum size of induced independent sets and proved the Gröflin-Hoffman theorem (Section 3.3.1 of the lecture notes and Theorems 13.1.15 and 13.2.23 in Frank’s book).