Lectures: Thursdays 12:20 in S5.

Tutorials, lead by Babak Ghanbari: Tuesdays 10:40 in S11.

Grading: according to the final (oral) exam, focusing on the proofs and applications; see example questions below.

• 22.2. Perfect matchings: Tutte's theorem, Edmonds-Gallai decomposition, Petersen's theorem.
  • Lecture notes.
  • Slides.
• 29.2. Edmonds' blossom algorithm for finding largest matching.
  • Lecture notes.
• 7.3. Graph minors: definition and basic properties. Wagner's theorem and its relationship to Kuratovski's theorem. Tutte's contractible edge theorem and the characterization of 3-connected graphs.
  • Lecture notes.
  • Slides.
• 14.3. The proof of Tutte's and Wagner's theorems. Density of K_k-minor-free graphs. (We skipped the part on Hadwiger's conjecture.)
  • Lecture notes.
  • Slides.
• 21.3. Graphs on surfaces: classification of surfaces, their representation, genus and generalized Euler's formula.
  • Lecture notes.
  • Slides.
• 28.3. Graph coloring: Heawood's formula, Brooks' theorem.
  • Lecture notes. Includes the proof Vizing's theorem presented in the following lecture.
  • Slides.
• 2.4. Vizing's theorem. Chordal graphs: structural characterizations, clique, independence and chromatic number.
  • Lecture notes.
  • Slides.
• 4.4. Perfect graphs: examples, perfect graph theorems and their applications.
  • Lecture notes.
  • Slides.
• 25.4. Hamilton cycles: Dirac's and Ore's theorems, Chvátal's closure.
  • Lecture notes.
  • Slides.
• 2.5. Tutte's polynomial: equivalent definitions, related graph invariants.
  • Lecture notes.
  • Slides.
• 9.5. Enumeration: properties of power series coefficients, exponential generating functions. We did not do the part on more detailed analysis (subtraction of singularities).
  • Lecture notes.
  • Slides.
• 16.5. Symmetries: Burnside's lemma and Polya's enumeration. We did not manage to do Polya's enumeration.
  • Lecture notes.
  • Slides.
• 23.5. Extremal combinatorics: Turán's theorem, Erdos-Ko-Rado's and Erdos-Szekeres' theorems. We only managed to do Turán's theorem.
  • Lecture notes.
  • Slides.

1. Perfect matchings: Edmonds-Gallai decomposition, Tutte's theorem, Petersen's theorem on matchings in 3-regular bridgeless graphs. Application: finding a subgraph with prescribed degrees. Edmonds maximum matching algorithm. Number of perfect matchings in bipartite cubic graphs.
2. Graphs on surfaces: generalized Euler's formula, coloring and Heawood's formula.
3. Graph minors: Kuratowski theorem and Tutte's theorem on contractions in 3-connected graphs.
4. Edge and vertex coloring: Vizing's and Brooks' theorems.
5. Perfect graphs: perfectness of graph classes, weak (and strong) perfect graph theorem.
6. Tutte's polynomial: definitions, specializations (chromatic polynomial, ...), values.
7. Hamilton cycles: Dirac's and Ore's theorems, Chvátal's closure, hamiltonicity in planar graphs.
8. Enumeration: exponential generating functions, Burnside's lemma and Polya's enumeration.
9. Extremal theory: Turán's theorem, forbidden minors and degeneracy, Erdos-Ko-Rado's and Erdos-Szekeres' theorems.
10. Ramsey theory: hypergraphs, infinite and canonical versions, Erdos-Hajnal's conjecture.
11. Self-correcting codes: definitions, linear codes, Singleton's bound, Hamming's bound and code, Golay's code. Hadamard's code, Plotkin's bound, Gilbert-Varshamov's construction. Elias-Basallygo's bound.

1. Perfektní párovaní: Tutteho věta pomoci Edmonds-Gallaiovy dekompozice, Petersenova věta o existenci perfektního párovaní v 3-regulárním grafu bez mostu, hledáni podgrafu s předepsanými stupni. Edmondsův algoritmus pro nalezeni největšího párovaní. Počet párovaní v bipartitním kubickém grafu.
2. Plochy vyššího rodu: Eulerova formule, barevnost grafu na plochách, Heawoodova formule.
3. Grafové minory: Důkaz Kuratovského vety a Tutteho věta o 3-souvislých grafech.
4. Vrcholová a hranová barevnost grafů: Brooksova a Vizingova věta.
5. Perfektní grafy: třídy perfektních grafu, slabá a silná věta o perfektních grafech.
6. Tutteho polynom: definice, specializace (chromaticky polynom, ...), hodnoty.
7. Hamiltonovské kružnice: Diracova a Oreho věta, Chvátalův uzávěr, protipříklad na hamiltonovskost rovinných 3-souvislých 3-regulárních grafu a souvislost s vetou o 4 barvach.
8. Enumerace: zopakováni a prohloubeni výsledků o generujících funkcich, exponenciální generující funkce, Burnsideovo lemma a Polyova enumerace.
9. Extremální teorie: Turánova věta, zakázané minory vynucuji degenerovanost, Erdos-Ko-Radova a Erdos-Szekeresova věta.
10. Ramseyovská teorie: hypergrafy, nekonečná verze, kanonická Ramseyova věta, Erdos-Hajnalova hypoteza.
11. Samoopravné kódy: definice, lineární kódy, Singletonův odhad, Hammingův odhad a kód, Golayův kód. Hadamardův kód, Plotkinův odhad, Gilbert-Varshamova konstrukce. Elias-Basallygův odhad.

For the topic of matchings:

1. Prove Tutte's theorem using Edmonds-Gallai's theorem.
2. Prove Petersen's theorem using Tutte's theorem.
3. State Edmonds-Gallai's theorem and give a basic idea of its proof (the choice of set S, the outline of what we do to show it is an EG-set, maybe a detailed argument for one of the claims).

Recommended books:

• R. Diestel: Graph theory, Springer, 2005.
• Herbert S. Wilf: generatingfunctionology.
• B. Bollobas: Modern graph theory, Springer, 1998.
• S. Jukna: Extremal combinatorics: with applications in computer science, Springer, 2001.
• T. Kaiser: Samoopravne kody.
• L. Lovasz, M.D. Plummer: Matching theory, AMS Chelsea publishing, 2009.
• A. Schrijver: Combinatorial optimization, Springer, 2003.

Studijní text k Počtu párování v bipartitním kubickém grafu. Prezentace o grafech na plochách a Brooksově a Vizingově větě.

Matouškův text k Elias-Basallygovu odhadu.

Příklady ze cvičení (rok 2011).

• 1.serie
• 2.serie
• 3.serie

Příklady ze cvičení (rok 2010).

• 1.serie
• 2.serie
• 3.serie

Příklady ze cvičení (rok 2007, staré osnovy).

• Minimaxové věty.
• Extremální teorie.
• Barevnost grafů -- obvod, jednoznačnost
• Vybíravost
• Hranová barevnost, grafy na plochách
• Ještě jednou Turánova věta
• A ješte jednou
• Ramseyovky
• van den Waerden, Hales-Jewet

Příklady ze cvičení (rok 2009)

• Dokazte Hallovu vetu pomoci Tutteho vety.
• Dokazte, ze kazdy 3-regularni graf s nanejvys dvema mosty ma perfektni parovani.
• Dokazte, ze pro kazdy 3-regularni hranove 2-souvisly graf a jeho hranu e existuje perfektni parovani, ktere e obsahuje.
• Dokazte, ze kazdy k-regularni hranove k-souvisly graf se sudym poctem vrcholu ma perfektni parovani.
• Dokazte, ze kazdy k-regularni hranove (k-1)-souvisly graf se sudym poctem vrcholu ma perfektni parovani.
• Pro kazde k naleznete k-regularni hranove (k-2)-souvisly graf se sudym poctem vrcholu, ktery nema perfektni parovani.
• Naleznete algoritmus, ktery pro graf bez perfektniho parovani nalezne mnozinu vrcholu z Tutteho vety. Predpokladejte, ze mate k dispozici algoritmus zjistujici, zda graf ma perfektni parovani.
• Dokazte, ze determinant antisymetricke matice sousednosti grafu je nenulovy prave tehdy, kdyz graf ma perfektni parovani.
• Jestlize G je souvisly, ma alespon 4 vrcholy, a kazda hrana lezi v nejakem perfektnim parovani, pak G je hranove 2-souvisly.
• Urcete maximalni pocet hran grafu na 2n vrcholech bez perfektniho parovani.
• 2-souvisly graf bud nema zadne perfektni parovani, nebo ma alespon 2 perfektni parovani.
• Pro kazde n>1 existuje bipartitni graf, ktery hladovy algoritmus (odtrhavajici pokazde vrchol nejmensiho stupne, a barvici nejmensi pouzitelnou barvou) obarvi n barvami.
• Jestlize G je linegraph nejakeho grafu, pak G neobsahuje K_{1,3} jako indukovany podgraf. Opacna implikace neplati.
• Hranova barevnost bipartitniho grafu je rovna jeho maximalnimu stupni.
• Hranova barevnost 3-regularniho rovinneho grafu bez mostu je 3.
• Petersenuv graf ma hranovou barevnost 4.
• Ukazte, ze line graf bipartitniho grafu je perfektni.
• Ukazte, ze comparability grafy jsou perfektni.
• Ukazte, ze split grafy jsou perfektni.
• Graf je perfektni prave tehdy, kdyz kazdy jeho indukovany podgraf H obsahuje nezavislou mnozinu protinajici vsechny jeho kliky nejvetsi velikosti.
• Nahradime-li v perfektnim grafu vrchol v jinym perfektnim grafem H (tj. smazeme v a pridame uplny bipartitni graf mezi sousedy v a vrcholy H), pak vysledny graf je perfektni.
• Ukazte, ze nakresleni rovinneho 3-souvisleho grafu je (kombinatoricky) jednoznacne.
• Ukazte, ze graf je vnejskove rovinny prave tehdy, kdyz neobsahuje podrozdeleni K₄ a K_2,3.
• Ukazte, ze kazdy rovinny graf ma nakresleni, v nemz vsechny hrany jsou prime, tj., usecky.
• Jake podminky musi splnovat trida grafu C, aby platilo nasledujici: existuje mnozina grafu X takova, ze graf G patri do C prave tehdy, kdyz neobsahuje podrozdeleni grafu z X?
• Naleznete zakazane minory pro rovinne grafy.
• Naleznete nakresleni K₇ na torus.
• Dokazte, ze K₇ nelze nakreslit na Kleinovu lahev.
• Ktere grafy K_n,n lze nakreslit do projektivni roviny? Na torus? Na Kleinovu lahev?
• Naleznete kvadrangulaci projektivni roviny a toru barevnosti 4.
• Dokazte, ze kazdy graf bez podrozdeleni K₄ lze obarvit 3 barvami.
• Urcete pocet ruznych obarveni sten krychle 3 barvami. Dve obarveni povazujeme za stejna, jestlize se lisi pouze rotaci ci zrcadlenim.
• Urcete pocet navzajem neizomorfnich grafu na 4 vrcholech. Kolik z nich ma prave 5 hran?
• Pouzitim Polyovy enumeracni formule naleznete rekurzivni vzorec pro pocet zakorenenych ternarnich stromu (stromy lisici se pouze permutaci poradi synu v nekterych vrcholech se povazuji za stejne).
• Dokazte, ze koeficient Tutteho polynomu u x je roven c'(1), kde c je chromaticky polynom.
• Dokazte, ze pokud G je sjednocenim grafu G₁ a G₂ sdilejicich nanejvys jeden vrchol, pak T(G)=T(G₁)T(G₂).
• Pouzitim Tutteho polynomu urcete pravdepodobnost, ze graf vznikly z G odebranim kazde hrany s pravdepodobnosti p (nezavisle) je souvisly.
• Ukazte, ze je-li G rovinny a H jeho dual, pak T_G(x,y)=T_H(y,x).
• Hustota hran Turanova grafu t_k(n) se v limite blizi (k-1)/k.
• Urcete maximalni pocet podmnozin n-prvkove mnoziny takovych, ze kazde dve z nich maji neprazdny prunik.
• Urcete hodnotu R(K₃,2K₃).
• Urcete hodnotu R(2K₃,2K₃).
• Urcete hodnotu R(aK₂,bK₂).
• Ukazte, ze R(T₁,T₂) pro dva stromy T₁ a T₂ je linearni v poctu jejich vrcholu.
• Ukazte, ze pro libovolne obarveni konecnych podmnozin prirozenych cisel konecne mnoha barvami existuje nekonecna mnozina X takova, ze pro kazde n, vsechny n-prvkove podmnoziny X neobsahujici prvnich n prvku z X maji stejnou barvu.
• Zformulujte a dokazte kanonickou Ramseyovu vetu pro matice.
• Dokazte, ze kazda posloupnost nm+1 cisel obsahuje nerostouci podposloupnost delky n+1 nebo neklesajici podposloupnost delky m+1. Dokazte, ze toto tvrzeni neplati pro posloupnost delky nm.
• Naleznete obarveni prirozenych cisel dvema barvami, ktere neobsahuje nekonecne dlouhou monochromatickou aritmetickou posloupnost.
• Dokazte, ze prunikove grafy grafu funkci jsou perfektni.
• Ukazte, ze Hammingova vzdalenost je metrika.
• Ukazte, ze kod, ktery jsme odvodili z Fanovy roviny, je jednim z Hammingovych kodu.
• Naleznete "prirozenou" matici Hammingova kodu.
• Jak souvisi soucin slova s dualni matici Hammingova kodu s pozici chyby?
• Ukazte, ze je-li d sude, pak A(n,d)=A(n-1,d-1).