**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