Schedule:

• Lecture: Thursday 12:20–13:50 in S3.
• Tutorials: Wednesday 14:00–15:30 in S11 (Guillermo Gamboa) or Thursday 14:00–15:30 in S11 (Gaurav Kucheriya).
• Office hours: Tuesday 12:00, office 220.

Conditions to pass the tutorials: Obtaining at least 50 points.

• Up to 30 points can be obtained by active participation in the tutorials (solving the tasks and presenting their solutions).
• 30 points can be obtained for short tests given at the beginning of each lecture.
• 30 points can be obtained for weekly homeworks.

The homeworks should be submitted in OWL. Use the following link to enroll.

Lecture notes

• 2.10.: Intro to combinatorics (exact formulas, recurrences, asymptotically precise estimates, growth rates, equivalences). Generating functions as an important tool for each of these possible outcomes. Homework, tutorials assignment.
• 9.10.: The correctness of the generating function approach, growth rate bound from the radius of convergence. Sum and product of generating functions, Application on the number of well-matched strings of brackets. Homework, tutorials assignment.
• 16.10.: Generalized Binomial Formula. Asymptotic estimates using analytic methods. Entropy and binomial coeficient estimates. Homework, tutorials assignment.
• 23.10.: Entropy in information theory. Homework, tutorials assignment.
• 30.10.: Error-correcting codes, basic concepts, examples, and inequalities (Hamming bound). Greedy code (in tutorials). Homework, tutorials assignment.
• 6.11.: Linear codes, Hamming code. Reed-Solomon code.
• 13.11.: Double-counting arguments and introduction to extremal combinatorics (maximum number of edges of K₃ and C₄-free graphs, largest possible antichain).
• 20.11.: Ramsey theorem (proof of the finite 2-color variant, other variants in passing). Existential proofs using random graphs, lower bound on the Ramsey numbers.
• 27.11.: Random graphs. Erdos-Renyi model and why different models of random graphs are needed (comparison to real-world large networks). Other models, mostly informally (configuration, preferential attachment and the power law).
• 4.12.: Vertex and edge connectivity, Menger's theorem.
• 11.12.: Matchings in bipartite graphs, Hall's theorem. Other variants (min-weight, stable) and their applications.
• 18.12.: Expanders as a more global notion of connectivity. Basic properties, spectral characterization. Rapid mixing of random walks, informal description of applications (randomness extractors).
• 8.1.: In contrast, balanced sublinear separators in planar graphs. Proof via interdigitating trees and via Koebe's touching disk representation. Application in divide-and-conquer algorithms (3-colorability of planar graphs).