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:
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. Loňské písemky jsou na loňské stránce. 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á)
Vy i zkoušející můžete iniciovat ústní část. 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.):
(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.
Pozor, odhlásit se ze zkoušky je možné nejpozději 3 dny před termínem.
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. [plán] 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. [plán] Počítání dvěma způsoby [P: chapter 6.3, 6.4]
- 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 (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 [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?
8.12. [plán] Ramseyovy věty
15.12. [plán] Samoopravné kódy
5.1. [plán] Víc samoopravných kódů