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: ???

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.

• 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.
• 9.10.: More on generating functions, Catalan numbers via generating functions and via Dyck paths.
• 16.10.: Asymptotic estimates using analytic methods (integration, radius of convergence). Entropy and binomial coeficient estimates.
• 23.10.: Double counting as one of the basic methods in combinatorics to prove identities and inequalities. Examples: Combinatorial number identities. Block designs. Maximum number of edges of K₃ and C₄-free graphs, basic introduction to extremal graph theory.
• 30.10.: 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).
• 6.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.
• 13.11.: Vertex and edge connectivity, Menger's theorem.
• 20.11.: Expanders as a more global notion of connectivity. Basic properties, spectral characterization. Rapid mixing of random walks, informal description of applications (randomness extractors).
• 27.11.: 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).
• 4.12.: Matchings in bipartite graphs, Hall's theorem. Other variants (min-weight, stable) and their applications.
• 11.12.: Error-correcting codes, basic concepts, examples, and inequalities (Hamming bound), random code.
• 18.12.: Linear codes, Hamming code.
• 8.1.: Other error-correcting code constructions (Reed-Solomon, codes from expanders).