A:C&T
Arrangements: Combinatorics & Topology


Introduction to

matroid theory

BeNeFri lecture Spring 2018, University of Fribourg



Time and place: Thursdays, 8:15-12:00 , U Fribourg Pérolles, MathII (Lonza). First meeting: February 22 at 10:15 .

Description: Matroid theory arose as a combinatorial generalisation of both linear algebra and graph theory. During the 20th century it has grown into a fascinating structural theory, unifying vast areas of combinatorics and establishing strong connections to many other mathematical disciplines (from optimisation theory to commutative algebra and tropical geometry).

This course is about the basics, and will build solely on basic facts of (linear) algebra. 
We will begin with presenting an array of different definitions and proving their equivalence. We will then discuss polynomial invariants of matroids as well as representability questions. After that — as time will permit, and according to the interests/backgrounds of the participants — we will touch upon some of the connections to other mathematical disciplines.

Main literature: (Available on hold in the department's library)
  • [O] J. Oxley, Matroid theory, Oxford University Press, 2011 (2. Ed.).
  • [W] N. White, Matroid applications, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, 1992.
Format: Lecture with some exercises. For those who need credit points, an oral examination. The exact format will be discussed during the first meeting.

Contact: SNSF-Prof. Emanuele Delucchi, emanuele.delucchi "at" unifr.ch
Lecture 1, February 22. - Introduction
Suggested "warm-up" exercises: [click here]
Lecture 3, March 7. - Bases, rank.
Reference: [O], pages 15 - 22.
Suggested exercises: [click here].
Lecture 4, March 15. - The characteristic polynomial; deletion and contraction
Suggested exercises: [click here]
Lecture 5, March 22. - Arrangements, chamber count (A)
Reference: see e-mailed handout notes.
Lecture 6, March 29. - Geometric lattices (A)
Suggested exercises: [click here]
Reference: see e-mailed handout notes.
Lecture 7, April 12. - Duality and diagrams
Reference: [this] plus e-mailed handout notes.
Suggested exercises: [click here]
Lecture 8, April 19. - The Tutte polynomial (B)
Reference: e-mailed handout notes, based on [W, chapter 6].
Suggested exercises: [click here]
Lecture 9, April 26. - (Lecture by F. Babaee: Bergman complexes and tropical geometry)
Lecture 10, May 3.- Flows on graphs and flows polynomials (B)
Reference: see e-mailed handout notes.
Suggested exercises: [click here]
Lecture 11, May 10. - No lecture
Lecture 12, May 17. - Matroids and optimization (A)
Reference: handout notes [click here], based on [W, chapter 8].
Lecture 13, May 24. - Review
May 31 - No lecture (``Fête-Dieu '')