Kombinatorika a Grafy 1 (NDMI011) -- přednáška
Přednáška se koná každé pondělí v 15:40 v N1.
Přednášku vede Pepa Tkadlec. E-mail: pepa (AT) iuuk.mff.cuni.cz
Cvičení vedou: Eliška Červenková, Barbora Dohnalová, Tomáš Hons, David Mikšaník, Irena Penev a Pepa Tkadlec
Zápočet:
Zápočet bude udělen za zisk 100 bodů udělovaných průběžně za písemné testy, řešení domácích úloh, aktivitu na hodinách, apod. Maximální možný počet bodů, které lze získat, je zhruba 150. Konkrétní pravidla pro zisk zápočtu stanoví cvičící příslušného kroužku.
Stránky cvičení:
Zkouška:
Požadavky ke zkoušce: pdf.
Loňské písemky jsou na loňské stránce. Letoší písemky: Dec 17, ..
Zkouška má písemnou část (90 minut, dopoledne) a ústní část (odpoledne). Ústní část je obvykle poměrně krátká (<15 minut). Písemná část obsahuje několik úloh následujících typů: zformulujte definici; uveďte výsledek z přednášky; dokažte výsledek z přednášky; vyřešte úlohu související s probranou látkou. Celkem je z písemky možné získat až 30 bodů. Předběžné známky jsou pak
[26-30]: 1
[21-25]: 2
[16-20]: 3
[11-15]: 4 (ústní část je možná)
[ 0 -10]: 4 (ústní část není možná)
Zkoušející můžete iniciovat ústní část (po dohodě i vy). Během té se známka může změnit oběma směry.
Během zkoušky smíte používat jen psací potřeby a lahev s vodou (zejména: žádná elektronika, žádné poznámky).
Vezměte si s sebou doklad totožnosti.
Pro složení zkoušky je potřeba mít v SISu zápočet (neplatí pro předtermíny).
Termíny zkoušek (přihlašování v SISu od 1.12.):
Pozor, odhlásit se ze zkoušky je možné nejpozději 3 dny před termínem.
(předtermín) 17.12. písemka od 9.00 v N2, ústní od 12.30 v N2 (v tomto termínu výjimečně není potřeba mít v SISu zápočet)
(předtermín) 7.1. písemka od 8.30 v N2, ústní od 12.30 v N2 (v tomto termínu výjimečně není potřeba mít v SISu zápočet)
12.1. písemka od 9.00 v S9, ústní od 12.30 v S8
13.1. písemka od 9.00 v S9, ústní od 12.30 v S8
14.1. písemka od 9.00 v S9, ústní od 12.30 v S8
20.1. písemka od 9.00 v S5, ústní od 12.30 v S8
21.1. písemka od 9.00 v S9, ústní od 12.30 v S8
dále budou minimálně 2 termíny v létě, data určím nejpozději 30.4.
Zdroje:
[MN] J. Matoušek, J. Nešetřil: Invitation to discrete mathematics, 2nd edition, 2008.
[P] I. Penev: Combinatorics and Graph Theory 1 & 2 (pdf), kapitoly 1 -- 8.
záznamy přednášek Vítka Jelínka z roku 24/25 (pozor, probraná látka se trochu liší)
stránka Martina Balka z roku 22/23 (pozor, probraná látka se trochu liší)
Probraná látka:
29.9. Úvod, odhady faktoriálů a kombinačních čísel: [MN: chapter 3, P: chapter 1] [záznam]
- 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
6.10. Vytvořující funkce [P: chapter 2, MN: chapter 12] [záznam]
- baby example (7 balls from 5 red, 4 green, 3 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). Also a book generatingfunctionology by H. S. Wilf.
13.10. Víc vytvořujících funkcí [P: chapter 2, MN: chapter 12] [záznam]
- 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 (just stated) [MN 12.7 / here]
- bonus: the riddle (un, dos, tres, quatre, cinc, sis, ..) and the Veritasium video about the generalized binomial theorem
20.10. Konečné projektivní roviny [P: chapter 3, MN: chapter 9] [záznam]
- 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 of a set system [MN 9.1 / P 3.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}).
27.10. Konečné projektivní roviny a ortogonální latinské čtverce [P: chapter 3, MN: chapter 9] [záznam]
- Algebraic construction of FPPs from finite fields (proof sketched) [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. Also: sudoku is a latin square on steroids (CrackingTheCryptic).
3.11. Párování v bipartitních grafech [P: chapter 4.1, 4.4] [záznam]
- definice parovani, velikost m(G) nejvetsiho parovani
- definice tokove site, toku, rezu. Veta o celociselnosti max.toku, pokud jsou vahy celociselne (bez dukazu). Veta maxflow=mincut (bez dukazu).
- definice vrcholoveho pokryti, velikost vc(G) nejmensiho vrcholoveho pokryti
- König-Egerváryho veta: v bipartitnim grafu je m(G)=vc(G)
- definice parovani nasycujiciho partitu A, definice okoli N_G(A').
- Hallova veta: parovani nasycujici A existuje, kdyzz pro kazdou A'\subset A plati |N_G(A')|>=|A'| [P 4.4]
- bonus: The Harris & Ross paper from 1955 on where to cut the railways in the eastern block (map on page 44).
10.11. Aplikace Hallovy věty [P: chapter 4.4, 4.5], zacatek grafove souvislosti [P: chapter 5] [záznam]
- Existence of a perfect matching in a regular bipartite graph [P 4.4.2]
- Extending Latin rectangles to Latin squares [P 4.5.1]
- Alternative formulation of Hall theorem (for hypergraphs, with transversals = systems of distinct representatives) [P 4.4]
- edge cut, edge connectivity k_e(G), k-edge-connected graphs [P 5.1]
- vertex cut, vertex connectivity k_v(G), k-vertex-connected graphs [P 5.1]
- k_e(G), k_v(G) ≤ mindeg(G).
- k_e(G)-1 ≤ k_e(G-e) ≤ k_e(G) [P 5.1.1a]
- bonus: Karetní trik založený na Hallově větě,
17.11. Přednáška se nekoná (stání svátek).
24.11. Grafová souvislost [P: chapter 5] [záznam]
- k_v(G) ≤ k_e(G)
- Věta (Ford-Fulkerson). k_e(G)>=k, kdyžž pro každé 2 vrcholy existuje k hranově disjunktních cest [P: Global version of Menger's theorem, (b)]
- Věta (Menger). k_e(G)>=k, kdyžž pro každé 2 vrcholy existuje k vnitřně-vrcholově-disjunktních cest [důkaz: jen idea]
- most, artikulace
- Ušaté lemma (pro vrcholovou souvislost)
- bonus: proč artikulace. Also another notion to measure how well connected a graph is: expansion.
1.12. Počítání dvěma způsoby [P: chapter 6.2, 6.3, 6.4] [záznam]
- Erdős-Rényi nahodny graf ma skoro jiste velkou komponentu, ak p≥1.1/n, a je skoro jiste souvisly, ak p≥1.1logn/n (bez dukazu)
- Cayley's formula for the number of spanning trees of a complete graph (proof due to Pitman by double-counting, see e.g. Wiki)
- #spanning trees of a K_n minus one edge (bez dukazu)
- Sperner theorem about the size of the largest antichain in P([n])
- odbočka o nerovnostech: Cauchy-Schwarzova a Jensenova
- Graphs without a C_4 subgraph have O(n^{3/2}) edges [P 6.2.1]
- Bonus: A tool to play with the Erdős-Rényi graph. Also: 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?
8.12. Extremální kombinatorika a Ramseyovy věty [P: chapters 6.1, 7.1, 7.2] [záznam]
- ex(H,n) .. největší počet hran grafu na n vrcholech bez podgrafu H
- Mantelova věta: grafy bez K3 [P 6.1]
- Turánova věta (bez důkazu) [wiki]
- Dirichletův princip
- In a company of 6, there are 3 who either all know or all do not know each other [P 7.2.1]
- Ramseyovo číslo R(a,b) pro barvení hran K_n dvěma barvami
- Horní odhad R(a,b) ≤ C(a-1-b-1,a-1) [P 7.2.2]
- Dolní odhad R(k,k) ≥ 2^{k/2} [P 7.2.3]
- Důsledek (\sqrt 2)^k ≤ R(k,k) ≤ 4^k
- Silnější horní odhad R(k,k) ≤ 3.993^k (proof omitted, see a discussion here)
- Bonus: Erdős story about aliens, R(5,5), and R(6,6).
15.12. Ramseyovy věty a Samoopravné kódy [P: chapters 7.3, 8.1-8.3] [záznam]
- Kőnig's lemma (proof sketched) [P 7.5]
- (finite and infinite) Ramsey theorem for p-tuples = hypergraphs (proof omitted) [P 7.3, 7.4]
- Happy ending problem [P 7.3.1]
- Erdős-Szekeres theorem (wiki)
- Error-correcting codes over binary alphabet: Hamming distance, Hamming weight, (n,k,d)-code [P 8.2]
- Priklady: opakovaci kod, paritni kod [P 8.2.1],
- Bonus: A story about Esther Klein a George Szekeres.
5.1. [plán] Víc samoopravných kódů [P: chapter 8.4-8.6]
- code from a Fano plane [P 8.1]
- A code with minimum distance d can correct \floor{(d-1)/2} errors [P 8.2]
- combinatorial ball [P 8.3.1]
- Hamming bound [P 8.3]
- Gilbert-Varshamov bound [P 8.3]
- Hadamard matrix, Sylvester construction of Hadamard matrices, Hadamard code [P 8.2.2]
- 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]
- Bonus: Hadamard code was used to get the first photos of Mars to Earth.