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 2018
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
satisfactory work on the quizzes. Additionally, there will be two
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 15:40 on Monday afternoons
(excepting Easter Monday 2 April) in
Room S11 in the MFF building at Mala Strana.
Exercise sheets
Exercises will be given in printed form in class on the Monday,
consisting of problems related to the material
covered in the previous week's lecture. (A pdf of the exercise sheet
will also be posted on this
page.) Solutions are to be handed in written form in class a week later.
18 February
Binomial
coefficients as counting subsets of size k from {1,2, ... , n}and as a
function of n defined by n(n-1)...(n-k+1)/k! which is defined for n not
necessarily a positive integer. Binomial Theorem for positive integer
exponent, Generalized Binomial Theorem (for real exponent), number of
solutions to i_1+i_2+.... + i_r = m as a binomial coefficient (proof
"by blobs and lines,"also counts multisets of size m from {1,2,..., r}
in which i_k = multiplicity of k), Binomial Theorem with negative
integer exponent. Coefficients of polynomials, notation [x^k] p(x) for
coefficient of x^k in the polynomial p(x), multiplying two polynomials
(convolution of coefficient sequences). Applications in proving
identities e.g. from (1+x)^n(1+x)^n = (1+x)^{2n} and (1+x)^n (1-x)^n =
(1-x^2)^n. Multinomial theorem (briefly).
25 February
Exercise sheet 1.
Review of Generalized Binomial Theorem and Multinomial Theorem.
(Ordinary) generating functions: multiplication as convolution of
sequences. Differentiation of binomial identity (linear operation on
sequences, "differentiating term by term" for polynomials and power
series within radius of convergence). A certain binomial identity by
induction or by partitioning solutions to i_1+i_2+.... + i_{r+2} = n-r
according to value of last variable [Ex. 3.3.3 M&N, 2nd ed.] +
review of Pascal's identity. Picking out coefficient of a given term in
a power series (in possibly more than one variable) using binomial
theorem (multinomial theorem): numerical examples.
Reading: Matoušek and
Nešetřil,
Invitation to Discrete
Mathematics, 2nd ed., Sections 3.3, 12.1-12.2.
5 March
Exercise sheet 2.
Harmonic series estimates. Worked solution to exercise sheet 1: q. 2,
and MVT proof of 1+x <= e^x for all real x.
12 March
Exercise sheet 3.
Generating functions - Ex. sheet 2: problems 1 and 5(a).
Generalized binomial theorem, multinomial theorem, multiplying
power series = convolution of coefficient sequences, partial sums of a
sequence and multiplication by (1-x)^{-1}, g.f. for recursively defined
sequences such as the Fibonacci sequence, finding a closed formula by
use of partial fractions.
19 March
Exercise sheet 4.
Flows on networks. Max-Flow Min-Cut theorem (for edge capacities) -
review of edge cuts (separating source from sink), feasible flows,
f-augmenting paths, maximum flow
f equivalent to no
f-augmenting
paths. Max-Flow Min-Cut for vertex capacities (vertex cut as subset X
of vertices not including source/sink such that no positive-valued flow
from source to sink can be defined on the graph with X removed). Hall's
Marriage Theorem: proof by max-flow min-cut theorem - matchings
of bipartite graph correspond to flows of associated network with
vertex capacities 1. Supposing no complete matching of the given
bipartite graph, use maximum flow in network to construct vertex cut of
minimum capacity (size), producing then a complementary set of vertices
whose neighbourhood is smaller than itself. (Corresponds to
first proof in Bollobas,
Modern Graph Theory, III.3.)
26 March
Exercise sheet 5 (optional).
Worked solutions to Exercise sheet 4, questions 1,2,3, and 4(i) and
(iii).
2 April. NO CLASS
(Easter).
9 April. Review test
on Estimates of factorials and binomials, Generating
functions, Network flows, Bipartite matchings, Graph
connectivity, Ear decompositions.
Exercise sheet 6.
16 April.
Exercise sheet 7.
Double counting: applications to spanning trees and extremal theory.
(Ex. sheet 6 worked solutions.)
23 April.
Exercise sheet 8.
Finite projective planes. Recap (axioms, lines contain r+1 points,
points contained in r+1 lines, where r is the order; Fano plane;
incidence matrix; incidence graph - no odd cycles or C_4,
(r+1)-regular; dual projective plane). Worked solutions to questions 1
and 3 on exercise sheet 7.
30 April. (Dr
Tiwary) Ramsey theory, Latin squares
7 May.
Exercise sheet 9. (Problems 2 and 4 covered in class.)
Codes, Hamming distance, minimum distance, error-detecting and error-correcting, sphere-packing bound (Hamming bound).
14 May.
Linear codes.
21 May. Second
review test: double counting, extremal theory, projective planes, Latin
squares, Ramsey theory, error-correcting codes
