Irena Penev

Combinatorics and Graph Theory 1 (winter 2020/2021)

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

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. It will be possible to take the exam online (over Zoom). Depending on the COVID-19 situation, it may or may not be possible to take the exam in person at the Department.

Course content
Double Counting: Sperner Theorem, The maximum number of edges in a graph without K4 and without K3.
Number of spanning trees (determinant proof) and electrical networks.
Generating functions (understood as Taylor series), applications: Catalan, Fibonacci numbers, solving recurrences, asymptotics of the solution.
Finite projective planes.
Error-correcting codes, basic properties. Hammnig code, Hadamard code. Existence of asymptotically good codes (Gilbert-Varshamov). Hamming's lower bound.
Maximum matching in graphs, Hall's theorem and its applications (Birkhoff-von Neumann theorem), Tutte theorem.
k-connectivity, Menger's theorem. Ear lemma, structure of 2-connected graphs.
Ramsey theorem, Ramsey theorem for p-tuples, Ramsey infinite theorem.
Kőnig's theorem on the infinite branch.

Lectures
Lecture 1: Estimates of factorials and binomial coeffcients (Lecture Notes) (Slides) (Tutorial 1 slides)

Lecture 2: Generating functions (part I) (Lecture Notes) (Slides)

Lecture 3: Generating functions (part II) (Lecture Notes) (Slides)

Lecture 4: Finite projective planes (part I) (Lecture Notes) (Slides)

Lecture 5: Finite projective planes (part II) (Lecture Notes) (Slides)

Lecture 6: Flows and cuts in networks (Lecture Notes) (Slides)

Lecture 7: Applications of networks (Lecture Notes) (Slides)

Lecture 8: Graph connectivity and Menger's theorems (Lecture Notes) (Slides)

Lecture 9: 2-connected graphs and the Ear lemma. Cayley's formula (Lecture Notes) (Slides)

Lecture 10: Sperner's theorem. Ramsey numbers (Lecture Notes) (Slides)

Lecture 11: Ramsey theory and Konig's infinity lemma (Lecture Notes) (Slides)

Lecture 12: Bounding the number of edges in graphs without certain subgraphs (Lecture Notes) (Slides)

Lecture 13: Error correcting codes (Lecture Notes) (Slides)

Lecture 14: Linear codes (Lecture Notes) (Slides)

HW assignments
HW#1 (due Monday, October 12, 2020 before midnight)

HW#2 (due Monday, October 19, 2020 before midnight)

HW#3 (due Monday, October 26, 2020 before midnight)

HW#4 (due Monday, November 2, 2020 before midnight)

HW#5 (due Monday, November 9, 2020 before midnight)

HW#6 (due Monday, November 23, 2020 before midnight)

HW#7 (due Monday, November 30, 2020 before midnight)

HW#8 (due Monday, December 7, 2020 before midnight)

HW#9 (due Monday, December 14, 2020 before midnight)

HW#10 (due Monday, January 4, 2021 before midnight)