Matroids: Definitions, equivalence thereof, and examples. Linear representability over GF(2) and GF(3). The splitter theorem. Tutte's characterization of the graphic matroids.
Colin de Verdiere's graph parameter: Definition. Minormonotonicity, delta-wye operations, edge bound. Characterization of paths, outerplanar, planar, and (almost) linkless graphs.
Matroids: 1) "Matroid Theory", by James Oxley (ISBN 0-19-853563-5). 2) "Matroid Theory", by Dominic Welsh. Further references below.
Colin de Verdiere's graph parameter: This survey paper.
There will be a written exam covering the entire course on tuesday june 2, 14:00-17:00, room A.E (Roeterstraat 15). Making the exercise contained in the slides should prepare you for my part of this exam (although those exercises are often more time-consuming than what you may expect on a 3-hour exam).
Week 1. Matroids. Slides here. The slides contain exercises. References The various axiom systems and their equivalences are covered by both the books of Welsh and Oxley (chapters 1, 2.1, 3.1). You are encouraged to make your own proofs: none of these equivalences should be very hard, and self-made proofs are easier to remember. The basic examples of matroids can also be found in both books, with the exception of HPP matroids, which are a recent discovery. If you like these HPP matroids, find more information here and here. Exercises from Oxley: 1.1: all; 1.2: 1, 2, 7, 11, 12; 1.3: 4, 7; 1.4: 1, 6; 1.6: 10; 2.1: 12, 13; 3.1: 2, 7, 9.
Week 2. Linear matroids. Slides here. Find details in Oxley: chapters 6.1-6.5, and 9.1. Exercise from Oxley: 6.2: 7; 6.3: 4; 6.4: 5, 6, 9; 9.1: 2, 6.
Week 3. Matroids connectivity. Slides here. refer to Oxley: chapters 8 and 11.1. Exercises from Oxley: 8.1: 4; 8.4: 2, 4, 7, 8.
Week 4. No lecture. Dear students, I could not make it due to illness. Sorry to let you down. We'll meet again on may 12th.
Week 5. Graph minors and embeddings. Slides here. The paper "Knots and Links in Spatial Graphs" by Conway and Gordon, J. of Graph Th., Vol.7(1983) 445-453, contains the proof that K_6 has no linkless embedding.
Week 6. Colin de Verdiere's graph parameter. Slides here. The web pages of Lex Schrijver contain a survey on mu. Refer to sections 1, 2, 4 for the contents of this lecture.