Josef “Pepa” Tkadlec

Combinatorics and Graphs 1 (NDMI011) -- lecture

The lecture takes place every Tuesday at 10.40 in S5.
The lecture is given by Pepa Tkadlec. E-mail: josef.tkadlec (AT) iuuk.mff.cuni.cz
The tutorial is given by Hadi Zamani: tutorial website

Credit requirements:

see the tutorial website

Exam:

The exam has a written part (starts in the morning, 90 mins) and an oral part (in the afternoon). The oral part will typically be quite short (<10 mins).
In the written part, you might be asked to state a definition, state a result from the lecture, prove a result from the lecture, and/or to solve a problem related to the material covered in the lecture. In total, you can obtain up to 30 points. The preliminary grades are then [26-30]: 1, [21-25]: 2, [16-20]: 3, [11-15]: 4 (oral part possible), [0-10]: 4 (oral part not possible). Both you and the examiner may decide to initiate the oral part. There, the grade may change in either direction.

During the exam, you are only allowed to use a pen/pencil and a bottle of water (in particular: no electronics, no notes). Bring your ID. In order to get a passing grade from the exam you must have obtained the credit ("zápočet") beforehand. Students are encouraged to take the exam with the lecturer whose lectures they attended (in particular, exams run by Vit Jelinek are in Czech).

Exam requirements: pdf.

Past exams: Sample exam, Dec 16, Jan 14, Jan 15, Jan 27, Feb 3, Feb 11, Jun 11

Exam dates:

Dec 16 (includes the material not yet covered, for this date only credit="zápočet" is not required beforehand)

Jan 14: Written part starts at 8:30 in S4, oral part at 13:00 in S7.
Jan 15: Written part starts at 9:00 in N2, oral part at 13:00 in N9.
Jan 27: Written part starts at 9:00 in S1, oral part at 13:00 in S6.
Feb 3: Written part starts at 11:00 in S4, oral part at 15:00 in S6.
Feb 11: Written part starts at 9:00 in S9, oral part at 13:05 in S10.
June 11: Written part starts at 9:00 in S1, oral part at 12.30 in S1.

Note that unregistering from an exam date in the last 3 days before the date is not possible.

Resources:

[P] I. Penev: Combinatorics and Graph Theory 1 & 2 (pdf). The course material is covered pretty much exactly by chapters 1 -- 8.
[MN] J. Matoušek, J. Nešetřil: Invitation to discrete mathematics, 2nd edition, 2008.
Martin Balko's website from the 22/23 edition (in Czech)

Material covered:

First lecture (Oct 1): Estimating factorials and binomials: [P: chapter 1, MN: chapter 3]
- introduction, basic info, overview
- easy factorial bounds nn/2 ≤ n! ≤ nn and stronger bounds e(n/e)n ≤ n! ≤ en(n/e)n (by integral) [MN: 3.5.5]
- Stirling formula n! ~ (2\pi n)1/2(n/e)^n (just stated) [MN: 3.5]
- binomial bounds (n/k)k ≤ C(n,k) ≤ (en/k)k [MN: 3.6.1]
- bounds on the central binomial coefficient 22n/(2n1/2) ≤ C(2n,n) ≤ 22n/(2n)1/2 [MN: 3.6.2]
- Example: random walk on a line [P: 1.4]
- bonus [fun stuff]: 52! is a very large number
Second lecture (Oct 8): Generating functions [P: chapter 2, MN: chapter 12]
- baby example (7 balls from 3 red, 4 green, 5 blue) [MN 12.1]
- definition, example (1,1,1,..) -> 1/(1-x), comment on assumptions (x from a tiny neighborhood of 0)
- dictionary for translating between sequences and their generating functions [MN 12.2 / P 2.4]
- solving linear recurrences with constant coefficients, on the example of Fibonacci numbers [MN 12.3 / P 2.3]
- bonus: recall the Taylor series (explained by Taylor Swift and Elon Musk)
Third lecture (Oct 15): More generating functions [P: chapter 2, MN: chapter 12]
- generalized binomial coefficients, generalized binomial theorem (proof sketched) [MN 12.2 / P 2.2]
- corollary (1-x)^{-n} = \sum_{i=0}^\infty \binom{n+i-1}{n-1} x^i [MN 12.2]
- rooted binary trees, #rooted binary trees is the n-th Catalan number C_n=\frac1{n+1}\binom{2n}{n} [MN 12.4 / P 2.5]
- #partitions of n into odd parts = #partitions of n into distinct parts [MN 12.7 / here]
- bonus: the riddle (un, dos, tres, quatre, cinc, sis, ..) and the Veritasium video about the generalized binomial theorem
Fourth lecture (Oct 22): Finite projective planes [P: chapter 3, MN: chapter 9]
- definition, non-examples, example (Fano plane) [MN: 9.1]
- every two lines have the same size; order of the projective plane [MN: 9.1 / P 3.1.2]
- every point of an FPP (X,L) of order n lies on n+1 lines, |X|=n^2+n+1, |L|=n^2+n+1 [MN 9.1 / P 3.1.4]
- incidence graph and the dual of a set system [MN 9.1 / P 3.2]
- dual of a FPP of order n is a FPP of order n [MN 9.1 / P 3.2.2]
- existence of FPP of order 3; existence of FPPs of order n=p^\alpha (just stated); conjectured non-existence for other n [MN 9.2]
- bonus: Matt Parker video about FPPs and Dobble (spoiler alert: contains an answer to the riddle {0,1,3,13,32,36,43,52}).
Fifth lecture (Oct 29): Finite projective planes, cont'd [P: chapter 3, MN: chapter 9]
- Algebraic construction of FPPs from finite fields [MN: 9.2]
- latin square, orthogonality [MN: 9.3]
- max # of mutually orthogonal latin squares ("M.O.L.S.") of order n is at most n-1 [MN 9.3]
- an FPP of order n exists iff there exist n-1 M.O.L.S. [MN 9.3]
- bonus: Numberphile video about M.O.L.S.
Sixth lecture (Nov 5): No lecture (dean's day).
Seventh lecture (Nov 12): Flows in networks [P: chapter 4.1, 4.2, 4.3]
- Network. Flow, its value. A flow value can be measured at a partition [P 4.2.3]. Every network has a max flow (proof sketched) [P 4.1.1]
- Cuts, elementary cuts [P 4.2.1]. Any cut contains an elementary cut [P 4.2.2]
- Flow values ≤ cut capacities [P 4.2.4].
- Augmenting paths [P 4.2.5]. Max-flow min-cut theorem [P 4.2]
- Ford-Fulkerson algorithm [P 4.3]. On integer-networks the FF algorithm terminates and outputs an integer max flow (proof omitted) [P 4.3.4]
- bonus: The Harris & Ross paper from 1955 on where to cut the railways in the eastern block (map on page 44)
Eighth lecture (Nov 19): [by M. Tyomkyn] Applications of flows in networks [P: chapter 4.4, 4.5]
- König-Egerváry theorem (proof omitted)
- Hall's theorem (graph-theoretic formulation, with matchings) [P 4.4]
- Hall's theorem (combinatorial formulation, with transversals = systems of distinct representatives) [P 4.4]
- Defect Hall theorem [wiki]
- Existence of a perfect matching in a regular bipartite graph [P 4.4.2]
- Extending Latin rectangles to Latin squares [P 4.5.1]
- bonus: A card trick based on the Hall theorem
Ninth lecture (Nov 326): Graph connectivity [P: chapter 5.1, 5.2]
- edge cut, edge connectivity k_e(G), k-edge-connected graphs
- vertex cut, vertex connectivity k_v(G), k-vertex-connected graphs
- k_e(G)-1 ≤ k_e(G-e) ≤ k_e(G) [P 5.1.1a]
- k_v(G)-1 ≤ k_v(G-e) ≤ k_v(G) [P 5.1.2a]
- k_v(G) ≤ k_e(G) [P 5.1.3]
- Ford-Fulkerson theorem: A graph is k-edge-connected iff for every 2 vertices there exist k edge-disjoint paths [P: Global version of Menger's theorem, (b)]
- Menger theorem: A graph is k-vertex-connected iff for every 2 vertices there exist k vertex-disjoint paths (proof sketched) [P: Global version of Menger's theorem, (a)]
- bonus: Another notion to measure how well connected a graph is: expansion
Tenth lecture (Dec 3): Graph connectivity, cont'd [P: chapter 5.3] and double counting [P: chapter 6.3, 6.4]
- bridge, articulation, edge subdivision
- subdividing an edge of a vertex-2-connected graph preserves vertex-2-connectivity
- Ear lemma
- Cayley's formula for the number of spanning trees of a complete graph (proof due to Pitman by double-counting, see e.g. Wiki)
- Exercise: #spanning trees of a K_n minus one edge (proof omitted).
- Sperner theorem about the size of the largest antichain in P([n])
- Graphs without a C_4 subgraph have O(n^{3/2}) edges (proof omitted) [P 6.2.1]
- bonus riddle (Erdős-Ko-Rado theorem): At most how many subsets of size 5 can you choose from {1,2,..,10} so that every 2 of them intersect?
Eleventh lecture (Dec 10): Ramsey theory [P: chapter 7]
- Pigeonhole principle
- In a company of 6, there are 3 who either all know or all do not know each other [P 7.2.1]
- Ramsey number R(k,l) for coloring edges of K_n in 2 colors
- R(k,l) ≤ C(k-l-2,k-1) [P 7.2.2]
- R(k,l) ≥ 2^{k/2} [P 7.2.3]
- Corollary (\sqrt 2)^k ≤ R(k,k) ≤ 4^k
- Infinite Ramsey theorem for p-tuples = hypergraphs [P 7.4]
- Kőnig's lemma (proof sketched) [P 7.5]
- (finite) Ramsey theorem for p-tuples = hypergraphs (proof omitted) [P 7.3]
- Bonus: Erdős story about aliens, R(5,5), and R(6,6).
Twelfth lecture (Dec 17): Ramsey theory, cont'd [P: chapter 7.3]. Error-correcting codes [P: chapter 8]
- Happy ending problem [P 7.3.1]
- Erdős-Szekeres theorem
- Error-correcting codes over binary alphabet: Hamming distance, Hamming weight, (n,k,d)-code [P 8.2]
- A code with minimum distance d can correct \floor{(d-1)/2} errors [P 8.2]
- Special codes: repetition code, parity code [P 8.2.1], code from a Fano plane [P 8.1]
- Hadamard matrix, Sylvester construction of Hadamard matrices, Hadamard code [P 8.2.2]
- Bonus: Hadamard code was used to get the first photos of Mars to Earth.
Thirteenth lecture (Jan 7): Error-correcting codes, cont'd [P: chapter 8.3 -- 8.6]
- error-correcting codes: reminder
- combinatorial ball [P 8.3.1]
- Hamming bound [P 8.3]
- Gilbert-Varshamov bound [P 8.3]
- linear codes, [n,k,d]-codes [P 8.5], minimum distance of an [n,k,d]-code [P 8.5.2]
- "orthogonal complement" C^\perp of a linear code [P 8.4]. C^\perp of an [n,k,d]-code is a subspace of dimension n-k (proof omitted) [P 8.4.1]
- generator matrix and parity check matrix of an [n,k,d]-code [P 8.5]
- If C is an [n,k,d]-code and P its parity check matrix then x \in C iff P * x^T=0 (proof omitted)
- Hamming codes [P 8.6]
- Hamming code H_r is an [n=2^r-1, k=2^r-r-1, d=3]-code (proof omitted) [P 8.6]
- Example of correcting an error with H_3 [P 8.6]