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 2017 are given by Andreas Feldmann.
Exercises will help consolidate lecture material and the textbooks:
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 (here is 2nd ed.)
Madhu Sudan, Algorithmic Introduction to Coding Theory (Lecture notes, Harvard). See also Chapter 1 of Chris Withrich's notes on Codes and Cryptography

Performance on exercises will not directly affect your grade for the course (which is decided by the lecturer). However, if you intend to be graded for the course, you require a "pass" for the exercises. A pass/fail grade for the exercises will be decided based on regular attendance, satisfactory work on the exercise sheets, and participation in presentation of solutions to exercises. Additionally, there will be two short tests, one in the middle and one at the end of the semester, both of which require passing in order to proceed to the exam.

Exercise classes are held at 14:00 on Wednesday afternoons (excepting Rector's Day on 17 May) in Room S11 in the MFF building at Mala Strana (lectures are just before, in the same room S11, beginning at 12:20).

Exercise sheets

22 February
Estimates. Questions 1, 4.
Solutions to selected exercises
1 March
Generating functions. Questions 3, 4.
Solutions to selected exercises
8 March
Generating functions ctd. Questions 1, 5.
Solutions to selected exercises
15 March
Flows in directed graphs. Questions 1, 4.
Solutions to selected exercises
29 March Review test on: Estimates of factorials and binomials (Invitation 3.4--3.6), Generating functions (Invitation 12.1--12.3), Network flows (Modern Graph Theory III.1). Definitions, theorem statements, elementary examples and applications.
5 April
Bipartite matching. Questions 1,2
Solutions to selected exercises
12 April
Graph connectivity. Questions 1,2
Solution to 1. For question 2 (due to Dirac) see B. Van Hout's notes on graph connectivity, Theorem 10.2.
19 April

Spanning trees and double counting. Questions 1, 3
Solutions to selected exercises
26 April
Finite projective planes. Questions 2, (3,) 4
Solutions to selected exercises
3 May
Latin squares, Ramsey theory. Questions 1,3
Solutions to selected exercises
10 May
Coding theory. Questions 3, 4
17 May No class.
24 May 80-minute written review test on: bipartite matchings, graph connectivity, ear decompositions, spanning trees & extremal theory - double counting arguments, finite projective planes, Latin squares, Ramsey theory, error correcting codes. Definitions, theorem statements, elementary examples and applications. Questions based on material in lecture notes,  exercise sheets and the relevant textbook chapters (Matoušek & Nešetřil, Bollobás). Coding theory purely based on material covered in lecture of 10 May.