Combinatorics and Graph Theory I
Office hours: by appointment, in S125 (Malostranské nám. 25, 1st floor).
ExercisesLectures 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 AprilGraph 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.