Combinatorics and Graph Theory II

Lecture on Wednesday 10:40, S11

Topics covered:

• 4. 10.: Characterisation of maximum matchings via augmenting paths. Blossom contraction and its relationship to maximum matchings. Edmonds' Blossom algorithm for finding a maximum matching in a graph [Blo,T]. Note that a part of the correctness proof will be covered at the tutorial session.
• 11. 10.: Proof of Tutte's characterisation of  graphs with a perfect matching [D]. Proof that every 3-regular 2-connected graph has a perfect matching (Petersen's theorem) [D].
• 18. 10.: Each 3-connected graph other than K_4 has an edge whose contraction preserves 3-connectivity; Tutte's characterisation of 3-connected graphs [D]. The notion of graph minor. Kuratowski's and Wagner's theorem [D].
• 25.10.: Proof of Kuratowski-Wagner completed. Homeomorphism. Informal introduction to surfaces. Addition of a handle or a cross-cap. Classification of surfaces, notion of orientable and non-orientable surface of genus g [D].
  
• 1. 11.: Generalized Euler's formula, its consequences for average and minimum degree and degeneracy of graphs embedded on a given surface, Heawood's upper bound on chromatic number [D].
• 15. 11.: Theorems of Brooks and Vizing [D].
• 22. 11.: Perfect graphs, weak perfect graph theorem [D].
• 29. 11.: Chordal graphs, their characterisation by perfect elimination scheme, their perfectness [Ba, HR]. Hamiltonicity: the Bondy-Chvátal theorem on Hamiltonian graphs [BCh].
  
• 6. 12.: Tutte polynomial of a multigraph, its contraction-deletion recurrences, its relationship to the chromatic polynomial [Bo].
• 13. 12.: Basics of formal power series. Ordinary generating functions of combinatorial classes, and the combinatorial meaning of their sums, products and powers [W].
• 20. 12.: Exponential generating functions, the combinatorial interpretation of their products and sums [W]. Basic notions of group actions: fixed points, stabilizers, orbits [Bo].
• 3. 1.: The orbit-stabilizer lemma, the Cauchy-Frobenius formula (a.k.a. Burnside lemma) in both weighted and unweighted version [Bo].
• 10. 1.: Turán's theorem [D]. Erdős-Ko-Rado theorem [EKR]. Sunflower lemma.

Literature: