Course No.：21508Z
Period：20
Credits：1
Course Category：Advanced Course
Aims & Requirements:
Students will learn the basic concepts of matroid theory, and the applications of matroid theory to survivable networks and uniformly dense matroids.
Primary Coverage：
Lecture 1: Introduction to survivable networks. Graph density functions. Uniformly dense graphs and examples. Uniformly dense permutation graphs. Some applications of uniformly dense graphs.
Lecture 2: The strength and fractional arboricity of a graph. Nash-Williams and Tutte’s packing and covering theorems. Packing and covering by $c$-forests. The existence theorems. More examples.
Lecture 3: An Erdos’ problem on the density of graphs. The solution of this Erdos problem. Graph families closed under contractions. Characterization of uniformly dense graphs and sufficient conditions.
Lecture 4: The reinforcement problem. Reinforcing the spanning tree packing numbers. Payan’s conjectures (one solved and one still open). Reinforcing the strength of a graph.
Lecture 5: Introduction to matroids. Axioms and examples. Graphic matroids.
Lecture 6: Matroid Duality. Matroid truncations and elongations.
Lecture 7: Edmonds’ matroid intersection theorem. Matroid unions. Packing and covering theorems and their generalizations.
Lecture 8: Matroid density functions. Uniformly dense matroids. Characterizations of uniformly dense matroids.
Lecture 9: Relationships between some of the density functions (by matroid elongation and by matroid truncation). Embedding of a matroid into a uniformly dense matroid of the same kind.
Lecture 10: Embedding of a matroid into a uniformly dense matroid of the same kind. Future research problems.
References:
Matroid Theory, by Hong-Jian Lai, Chinese Higher Education Press,(2020) ISBN: 7-04-010563-2
Author：Hongjian Lai
