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 (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.