Combinatorics and Graph Theory I
Office hours: by appointment, in S125 (Malostranské nám. 25, 1st floor).
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
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).
Questions 1, 4.1 March
. Questions 3, 4.
Generating functions ctd.
Questions 1, 5.
Flows in directed graphs
. Questions 1, 4.
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.
12 AprilGraph connectivity.
For question 2 (due to Dirac) see B. Van Hout's notes on graph connectivity
, Theorem 10.2.
Spanning trees and double counting.
Questions 1, 3
Finite projective planes
. Questions 2, (3,) 4
Latin squares, Ramsey theory
. Questions 1,3
. Questions 3, 4
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.