Combinatorics and Graph Theory I

Office hours: by appointment, in S125 (Malostranské nám. 25, 1st floor).

Exercises

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

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.

1 March

Generating functions. Questions 3, 4.

8 March

Generating functions ctd. Questions 1, 5.

15 March

Flows in directed graphs. Questions 1, 4.

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

12 April

Graph connectivity. Questions 1,2

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

26 April

Finite projective planes. Questions 2, (3,) 4

3 May

Latin squares, Ramsey theory. Questions 1,3

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.