Irena Penev

NDMI012: Combinatorics and Graph Theory 2 (summer 2021)

Time and place
Lecture: Wednesday, 15:40-17:10, Zoom
Tutorial: Wednesday, 17:20-18:50, Zoom

Meeting ID: 992 8919 4962

Passcode: If you don't have it, e-mail me (ipenev [at] iuuk [dot] mff [dot] cuni [dot] cz)

Literature
Lecture notes.

Course requirements and grading
Tutorial: To obtain tutorial credit, students must obtain at least 40% total on HW assignments. The lowest two HW scores will be dropped.

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 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: Vertex and edge coloring: Brooks' theorem and Vizing's theorem (Lecture Notes) (Slides)

Lecture 6: Vertex and edge coloring: Chordal graphs (Lecture Notes) (Slides)

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

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

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

Lecture 10: Extremal combinatorics (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: Graphs on surfaces (Lecture Notes) (Slides)

HW assignments
HW#1 (due Tuesday, March 9, 2021 before midnight)

HW#2 (due Tuesday, March 25, 2021 before midnight)

HW#3 (due Tuesday, March 30, 2021 before midnight)

HW#4 (due Tuesday, April 6, 2021 before midnight)

HW#5 (due Tuesday, April 13, 2021 before midnight)

HW#6 (due Tuesday, April 20, 2021 before midnight)

HW#7 (due Tuesday, May 11, 2021 before midnight)

HW#8 (due Tuesday, May 18, 2021 before midnight)

HW#9 (due Tuesday, May 25, 2021 before midnight)

HW#10 (due Tuesday, June 1, 2021 before midnight)