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.

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

*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

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