Kombinatorika a grafy II / Combinatorics and graph theory II

Lectures: Mondays 9:00 on Zoom, meeting id 916 5806 9590 (e-mail me if you need the password).

Tutorials, lead by Carl Feghali: Thursdays 15:40 on Zoom.

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

Plan of lectures
  • 5.10. Perfect matchings: Tutte's theorem, Edmonds-Gallai decomposition, Petersen's theorem.
  • 12.10. Counting perfect matchings: in bipartite regular graphs, in planar graphs (Pfaffians).
  • Done up to the definition of the Pfaffian, will be finished on 19.10: Slides.
  • 19.10. 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.
  • 26.10. The proof of Tutte's and Wagner's theorem's. Hadwiger's conjecture.
  • 2.11. Graphs on surfaces: classification of surfaces, their representation, genus and generalized Euler's formula.
  • 9.11. Graph coloring: Heawood's formula, Vizing's and Brooks' theorems.
  • 16.11. Proof of Vizing's theorem. Chordal graphs: structural characterizations, clique, independence and chromatic number.
  • 23.11. Perfect graphs: examples, perfect graph theorems and their applications.
  • 30.11. Hamilton cycles: Dirac's and Ore's theorems, Chvátal's closure.
  • 7.12. Tutte's polynomial: equivalent definitions, related graph invariants.
  • 14.12. Enumeration: properties of power series coefficients, exponential generating functions.
  • 21.12. Symmetries: Burnside's lemma and Polya's enumeration.
  • 4.1. Extremal combinatorics: Turán's theorem, Erdos-Ko-Rado's and Erdos-Szekeres' theorems.
Obsah přednášek
  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.
Example exam questions

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).

Další materiály a zdroje

Doporučená literatura (recommended books):

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).

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

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

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 K4 a K2,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 K7 na torus.
  • Dokazte, ze K7 nelze nakreslit na Kleinovu lahev.
  • Ktere grafy Kn,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 K4 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 G1 a G2 sdilejicich nanejvys jeden vrchol, pak T(G)=T(G1)T(G2).
  • 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 TG(x,y)=TH(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(K3,2K3).
  • Urcete hodnotu R(2K3,2K3).
  • Urcete hodnotu R(aK2,bK2).
  • Ukazte, ze R(T1,T2) pro dva stromy T1 a T2 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).