Matroid theory, SF3706 (graduate course)


Matroid theory is a discrete theory that tries to capture the concept of (linear and algebraic) dependence. There are natural links to graph theory, lattice theory, topological combinatorics, algebraic geometry and combinatorial optimization. This course is a graduate course in Matroid theory, which will cover the basics as well as some modern aspects and use of matroids.

Lecturer: Petter Brändén. Email: pbranden "at" kth "dot" se

When and where: Tuesdays at 10:15-12:00 in room 3721 at KTH.

Some literature

The main reference is Oxley's book below, but there will handouts and notes available.

James Oxley, Matroid theory. Second edition. Oxford Graduate Texts in Mathematics, 21. Oxford University Press, Oxford, 2011. xiv+684 pp. ISBN: 978-0-19-960339-8.
Brief survey by Oxley, PDF
Introduction to hyperplane arrangements by Stanley. PDF
Richard P. Stanley, Enumerative Combinatorics, Vol 1, Cambridge University Press, Free electronic copy
Matroid applications. Edited by Neil White. Encyclopedia of Mathematics and its Applications, 40. Cambridge University Press, Cambridge, 1992. xii+363 pp. ISBN: 0-521-38165-7 05-06.
Gian-Carlo Rota, On the foundations of combinatorial theory I. Theory of Mobius Functions, Journal

Examination

Three or four sets of homework problems will be handed out. Here is how the grading works:

Undergraduate students: Solving roughly 85% of the problems gives grade B, 75% gives C, 65% gives D, 55% & gives E, 50% gives Fx. In addition, one can choose to do a voluntary presentation of a topic or research article. If satisfactory, the presentation will raise the grade by one step.

Graduate students: In order to pass, one must solve 70% of the homework problems and make a satisfactory presentation.

Homework: Collaboration is allowed, but you should write the solutions yourself. Please show all your work!

HW1. (To be handed in Feb. 25): PDF

HW2. (To be handed in March 25): PDF

HW3. (To be handed in May 6): PDF

Research articles : Link

Plan/What we have done

28/1: Axioms for independents sets, bases, rank functions and circuits. Basic examples. Notes
4/2: Closure, lattice of flats, hyperplane arrangements. Notes
11/2: Incidence algebra, Mobius inversion, Cross-cut theorem. Notes
18/2: Characteristic polynomials, Chromatic polynomials, Tutte polynomials. Notes
25/2: Tutte polynomials, hyperplane arrangements and acyclic orientations Notes
4/3: Finite field method, duality Notes
11/3: Representing matroids Notes
18/3: Regular matroids, representable matroids Notes
25/3: Duals of graphic matroids, Transversal matroids Notes
4/4: Theorems of Hall and Rado Notes
11/4: NO CLASS
15/4: Induced matroids. Greedy algorithm Notes
22/4: Internal and external activities Notes
29/4: Shellings of matroid complexes and broken circuit complexes Notes
6/5: Shellings of the order complexes of geometric lattices Notes