Combinatorics and Graphs 1 (NDMI011) -- lecture
The lecture takes place every Tuesday at 9.00 in S9.
The lecture is given by Pepa Tkadlec. E-mail: josef.tkadlec (AT) iuuk.mff.cuni.cz
The tutorial is given by Volodymyr Kuznietsov: tutorial website
Combinatorics and Graphs 1 (NDMI011) -- lecture
The lecture takes place every Tuesday at 9.00 in S9.
The lecture is given by Pepa Tkadlec. E-mail: josef.tkadlec (AT) iuuk.mff.cuni.cz
The tutorial is given by Volodymyr Kuznietsov: tutorial website
Credit requirements:
see the tutorial website
Exam:
The exam will have a written part (starting in the morning) and an oral part (in the afternoon). More information will appear here by November 30.
Resources:
We will mostly follow the lecture notes from Zdenek Dvorak's website:
[D] Z Dvorak: Lecture notes
Other resources include:
[P] I. Penev: Combinatorics and Graph Theory 1 & 2 (pdf).
[MN] J. Matoušek, J. Nešetřil: Invitation to discrete mathematics, 2nd edition, 2008.
Material covered:
We will mostly follow the lecture notes of Zdenek Dvorak from last year. See Zdenek's website.
Lecture 1 (Sept 29): [D: Lesson 1], without subsection 1.1.4.
bonus [just for fun]: a formula for the n-th prime
bonus: 52! is a very large number
Lecture 2 (Oct 6): [D: Lesson 2].
bonus: Taylor series (explained by Taylor Swift and Elon Musk)
Lecture 3 (Oct 13): [D: Lesson 3, section 3.1 and Example 15 from section 3.2] (by Zdenek Dvorak)
bonus: a riddle due to R. Stanley (Enumerative Combinatorics, Vol 2, exercise 6.24): "Explain the significance of the following sequence: un, dos, tres, quatre, cinc, sis, set, vuit, nou, deu, ..." (solution)
bonus: a Veritasium video about the generalized binomial theorem
Lecture 4 (Oct 20): Factorial/binomial bounds and a build up to entropy
factorial bounds (n/e)n ≤ n! ≤ en(n/e)n (by integral) [MN: 3.5.5]
Stirling formula n! ~ (2\pi n)1/2(n/e)^n (just stated) [MN: 3.5]
binomial bounds (n/k)k ≤ C(n,k) ≤ (en/k)k [MN: 3.6.1]
bounds on the central binomial coefficient 22n/(2n1/2) ≤ C(2n,n) ≤ 22n/(2n)1/2 [MN: 3.6.2]
[D]-Lesson 4 up to Example 20, plus Thm 22 (proof not complete)
Lecture 5 (Oct 27):
Entropy ([D: Lesson 4] until Thm 22 and example 23),
Error-correcting codes ([D: Lesson 5], part 5.1)
[plan] Lecture 6 (Nov 3): more Error-correcting codes