Irena Penev

Combinatorics and Graph Theory 1 (winter 2021/2022)

Time and place
Lecture: Wednesday, 12:20-13:50, S9 and Zoom
Tutorial: Thursday, 15:40-17:10, S7 and Zoom

Zoom Meeting ID: 982 1738 4264
Zoom Passcode: e-mail me if you do not have it

Literature
Lecture notes. Last year's notes can be found here. This year's notes will be posted as the semester proceeds, and they will be a slightly edited version of last year's 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
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: Asymptotic notation. Estimates of factorials and binomial coefficients (Lecture Notes) (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. Graph connectivity (Lecture Notes) (Slides)

Lecture 8: Menger's theorems and the Ear lemma (Lecture Notes) (Slides)

Lecture 9: Triangle-free graphs and graphs without a C_4 subgraph. 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: Error correcting codes (Lecture Notes) (Slides)

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

Tutorials
Tutorial 1

Tutorial 2

Tutorial 3

Tutorial 4

Tutorial 5

Tutorial 6

Tutorial 7

Tutorial 8

Tutorial 9

HW assignments
HW#1 (due Wednesday, October 6, 2021 before midnight)

HW#2 (due Wednesday, October 13, 2021 before midnight)

HW#3 (due Wednesday, October 20, 2021 before midnight)

HW#4 (due Wednesday, November 10, 2021 before midnight)

HW#5 (due Wednesday, November 24, 2021 before midnight)

HW#6 (due Wednesday, December 1, 2021 before midnight)

HW#7 (due Wednesday, December 8, 2021 before midnight)

HW#8 (due Wednesday, December 15, 2021 before midnight)

HW#9 (due Wednesday, January 5, 2022 before midnight)