Irena Penev

NDMI012: Combinatorics and Graph Theory 2 (summer 2022)

Time and place
Lecture: Tuesday, 17:20-18:50, S9
Tutorial: Thursday, 15:40-17:10, S11



Literature
Lecture notes. Last year's lecture notes can be found here. This year's lecture notes will be similar (though not necessarily identical) to last year's, and they'll be posted as the semester progresses. The order of lectures might differ from last year's. Lecture notes for Combinatorics Graph Theory 1 can be found here.

Course requirements and grading
Tutorial: To obtain tutorial credit, students must satisfy both of the following requirements: (1) obtain at least 50% total on HW assignments (the lowest score will be dropped), and (2) obtain at least 50% total on in-class quizzes (the lowest score will be dropped). HW problems will be proofs or relatively complex calculations. Quizzes will cover definitions, theorem statements, and routine calculations.

Lecture: To take the exam, students must first obtain tutorial credit. The exam will be written, and it will consist of problems similar to HW problems and problems from the tutorial.

Course content
Matchings in general graphs
Hamiltonian cycles, Ore condition, Chvátal closure
Surfaces of higher genus, generalized Euler's formula, Heawood's formula
Lemma on the contractible edge, Tutte's theorem on 3-connected graphs, Kuratowski's theorem
Graph coloring, Brooks' theorem, Vizing's theorem
Tutte polynomial: equivalent definitions, important points, cycle space, and cut space of a graph
Ordinary and Exponential Generating Functions
Burnside's lemma, Polya's enumeration, examples of applications
Sunflower theorem, Erdös-Ko-Rado Theorem, Turan's Theorem
Perfect graphs, Dilworth's theorem
Chordal graphs

Lectures
Lecture 1: Matchings in general graphs (Lecture Notes) (Slides)

Lecture 2: Edmonds' Blossom algorithm (Lecture Notes) (Slides)

Lecture 3: Minors and planar graphs (part I) (Lecture Notes) (Slides)

Lecture 4: Minors and planar graphs (part II) (Lecture Notes) (Slides)

Lecture 5: Graphs on surfaces (Lecture Notes) (Slides)

Lecture 6: Vertex and edge coloring: Brooks' theorem and Vizing's theorem (Lecture Notes) (Slides)

Lecture 7: Chordal graphs (Lecture Notes) (Slides)

Lecture 8: Perfect graphs (Lecture Notes) (Slides)

Lecture 9: The Tutte polynomial (Lecture Notes) (Slides)

Lecture 10: Hamiltonian graphs (Lecture Notes) (Slides)

Lecture 11: Burnside's lemma and applications (Lecture Notes) (Slides)

Lecture 12: Polya enumeration theorem. Exponential generating functions (Lecture Notes) (Slides)

Lecture 13: Extremal combinatorics (Lecture Notes) (Slides)

Tutorials
Tutorial 1

Tutorial 2

Tutorial 3

Tutorial 4

Tutorial 5

Tutorial 6

Tutorial 7

Tutorial 8

Tutorial 9

Tutorial 10

Tutorial 11

Tutorial 12

Tutorial 13

Tutorial 14

HW assignments
HW#1 (due Thursday, February 24, at the beginning of the tutorial)

HW#2 (due Thursday, March 3, at the beginning of the tutorial)

HW#3 (due Thursday, March 17, at the beginning of the tutorial)

HW#4 (due Thursday, March 24, at the beginning of the tutorial)

HW#5 (due Thursday, March 31, at the beginning of the tutorial)

HW#6 (due Thursday, April 7, at the beginning of the tutorial)

HW#7 (due Thursday, April 14, at the beginning of the tutorial)

HW#8 (due Thursday, April 21, at the beginning of the tutorial)

HW#9 (due Thursday, May 5, at the beginning of the tutorial)

HW#10 (due Thursday, May 12, at the beginning of the tutorial)