Course plan
This is the order in which I plan to discuss things in the course. I will fill out the missing parts well before the relevant date.
| Nr | Date | Content | Chapter | Recommended exercises | |
| 1 | 29/8 | Introduction | 1.1-1.3 | 1:1,2,3,4,6,8,9 | |
| 2 | 5/9 | Basics | 1.3-1.5,1.8 | 1:5,7,10,12,13,14,21,26,27(i) | |
| 3 | 12/9 | Matchings in bipartite graphs | 1.6,2.1 | 1:30,31, 2:1,4,9,11,14,16 +G-S Download G-S | |
| 4 | 19/9 | Matchings in general graphs | 2.2,2.5 + GE Download GE | 2:10,18,19,21,22,35,36 | hand-in 1 Download hand-in 1 distributed |
| 5 | 26/9 | Connectivity | 3.1-2 (not thm 3.2.6) |
3:1,2,5,7,8,9 |
|
| 6 | 3/10 | Menger's Theorem, Minors | 3.3,1.7 | 3:10,16,18,21,22, 1.33(finite) | deadline hand-in 1 |
| 7 | 10/10 | Tree-packing, Plane graphs | 2.4,4.1-2 | 2:27,28,29; 4:1,2,4,5,7 | |
| 8 | 13/10 | Planar graphs, Hadwiger conj | 4.2,4.4,7.3 | 4:16,20,21,23,24; 7:27,29,31,33 | |
| 9 | 27/10 | Coloring vertices | 5.1-2 | 5: 3,5,6,7,9,11,14,16 | hand-in 2 Download hand-in 2 distributed |
| 10 | 31/10 | Coloring edges and list coloring | 5.3-4 | 5:22,27,28,29,32,33,34,35 | |
| 11 | 7/11 | Random graphs | 11.1-2 | 11:1,2,3,4 | deadline hand-in 2 |
| 12 | 14/11 | Probabilistic method | 11.2-3 | 11:6,7,8,10,14 | |
| 13 | 21/11 | Threshold functions, Ramsey theory |
11.4 + Ramsey text Download Ramsey text |
11:11,13,15,16,18 + Ramsey 7.2.2, 7.2.3 | |
| 28/11 | Student presentations | ||||
| 14 | 5/12 | Turan's theorem, Szemeredi's regularity lemma | 7.1, 7.4 (pages 187-188) | 7:1,3,4,7,8,9,10,11,15,36,37 | |
| 15 | 12/12 | Guest lecture: Tom Britton | Large Networks Download Large Networks | ||
| 8/1 | Exam | ||||