Combinatorics and Graph Theory I

In the summer semester 2015/2016, I teach the English version of the basic course on Combinatorics and Graph Theory I. It is primarily intended for students of the English study programs, but everybody is welcome.

The lectures are held on every Tuesday from 10:40 in room S4.

Classes (exercises) are also on Tuesdays from 14:00 in room S11. They are taught by Ondřej Pangrác. Czech-speaking students can also select any classes of the Czech version of the course – we will try to keep all versions compatible.

date topics [source]
23. 2. Asymptotic estimates of functions. Motivation: amount of information needed to sort N elements. Estimating factorials: nn/2 ≤ n! ≤ ((n+1)/2)n, e(n/e)n ≤ n! ≤ en(n/e)n, Stirling's formula (proof omitted). Estimating binomial coefficients: (n/k)k ≤ C(n,k) ≤ (ne/k)k. The middle binomial coefficient: 4n/(2n+1) ≤ C(2n,n) ≤ 4n. [I 3.4–3.6]
1. 3. Toy examples of using polynomial multiplication and the Binomial theorem to get combinatorial identities. Generating functions and basic operations on them (addition, multiplication, differentiation, integration, substitution). A remark on power series and their convergence. Prefix sums (F(x)/(1-x)). A formula for the n-th Fibonacci numbers via generating functions and partial fractions. [I 12.1–12.3]
8. 3. More on generating functions. Generalized Binomial theorem. A lemma on C(-a,b). Counting binary trees on n vertices, Catalan numbers. General theorem on linear recurrence relations, proved for the case with no multiple roots by linear algebra. A note on irrational numbers in algorithms. [I 12.2, 12.4]
15. 3. Finite projective planes: definition and basic properties, duality. General set systems, their incidence graphs and duality. [I 9.1]
22. 3. An algebraic construction of projective planes. Latin squares and their orthogonality, connections to projective planes. Systems of distinct representatives. Hall's theorem and its two interepretations: SDRs in set systems, one-sided perfect matchings in bipartite graphs. [I 9.2–9.3, ???]
29. 3. A proof of Hall's theorem. Application: Birkhoff's theorem on bistochastic matrices. [???]
5. 4. Network flows: basic definitions, augmenting paths, Ford-Fulkerson algorithm for finding a maximum flow and a proof of its correctness using cuts. [???]
12. 4. Network flows: Min-max theorem on maximum flows and minimum cuts. Networks with integer capacities have integral maxumum flows. Existence of maximum flow: compactness (sketch), Ford-Fulkerson with shortest paths. Correspondence between bipartite matchings and integral flows, König's theorem on vertex covers, a proof of Hall's theorem using flows. [???]
19. 4. Vertex and edge connectivity. Deleting an edge decreases ke and kv by at most one. Characterization of connectivity using disjoint paths: Menger's theorem. Corollary: kv ≤ ke ≤ δ. [???]
26. 4. Synthesis of 2-connected graphs from C3 by adding and subdividing edges, or by adding "ears" to Cn [I 4.6]. Counting spanning trees: deletion-contraction formula, Cayley's formula (a proof using vertebrates) [I 8.1, 8.3].
3. 5. Counting spanning trees: Kirchhoff's Matrix-tree theorem (using determinant of the Laplace matrix) [I 8.5]. Extremal combinatorics: maximum number of edges in a graph without triangles and quadrangles, a lower bound using finite projective planes [I 4.8, 7.3, 9.4]. Cauchy-Schwarz inequality [I 7.3].
10. 5. Introduction to Ramsey theory: the party of six [I 11.1], Pigeonhole principle, Ramsey theorem for graphs and its multi-color version [I 11.2]. A lower bound for Ramsey numbers using the probabilistic method [I 11.3].
17. 5. Infinite Ramsey theorem for countable graphs and how it implies the finite case. Ramsey theorem for p-tuples (infinite version only). Schur's theorem. Erdős-Szekeres theorem on points in convex position. [???]
24. 5. Introduction to coding theory: Codes and their parameters. Hamming's metric, code distance and its connections to error detection and correction. Examples: total code, repetition code, parity code, a code derived from Fano's plane. Linear codes and the class of Hamming codes. Singleton's bound. Hamming's bound and perfect codes. [???]

Exams

There are no official exam dates. If you want to take an exam, please let me know and we will arrange a date. You can also join any of my exams listed in SIS. The same applies to consultations.

You are expected to know the theory presented at the lectures (see the extended syllabus below) and to be able to use it for solving combinatorial problems, similar to those from the classes. The necessary (but generally not sufficient) condition of passing the exam is knowledge and understanding of all definitions and theorems from the syllabus.

Recommended reading

Stránku spravuje Martin Mareš