Combinatorics and Graph Theory I
Office
hours: by appointment, in S125 (Malostranské nám. 25, 1st floor).
Lectures
for the course Combinatorics and Graph Theory I in the summer semester
of 2020
are given by
Andreas Feldmann.
Regular quizzes (short tests reviewing material from lectures from the previous week) and supplementary material to that covered by lectures:
Jiří Matoušek and Jaroslav Nešetřil,
Invitation
to Discrete Mathematics, 2nd ed., 2009
B. Bollobás,
Modern Graph Theory,
Springer, 1998
R. Diestel,
Graph Theory, 4th
ed., Springer, 2010
Madhu Sudan,
Algorithmic
Introduction to Coding Theory (Lecture notes, Harvard). See also
Chapter 1 of Chris Withrich's
notes
on Codes and Cryptography.
While performance on quizzes will not directly affect
your grade for the course (which is decided by the lecturer), satisfactory marks are prerequisite for taking the exam for
presentation of solutions to exercises.
A pass/fail
grade for the exercise class will be decided based on sufficient marks on the regular quizzes.
Exercise classes are
held immediately after the lecture at 14:00 on Friday afternoons
(excepting Good Friday 10 April and the two public holidays on 1 May and 8 May) in
Room S9 in the MFF building at Mala Strana.
Classes
21 February
Harmonic--Geometric--Arithmetic--Root-Mean-Square Inequality (for two numbers).
Proof using MVT that e^x>=1+x for all real x.
Application of this inequality to show that n\choose k is bounded above by (en/k)^k (as in Matousek and Nesetril).
Alternative proof of e(n/e)^n <= n! <= en(n/e)^n using lower and upper approximations to integral of ln x over [1,n].
28 February
QUIZ on estimates for factorials and binomial coefficients (definitions, lemmas, and main theorems).
Generating functions and power series. Taylor's formula for coefficients (statement only). Generalized binomial theorem (statement only). Operations on generating functions and corresponding operations on coefficient sequences.
Examples of Fibonacci numbers and binary trees.
6 March
QUIZ on generating functions (definitions, toy example, operations on generating functions).
Example of binary trees (Catalan numbers). Full binary trees, parenthesizing a product.
6 March
QUIZ on network flows (up to and including the Ford--Fulkerson Theorem).
