Kombinatorika a grafy II / Combinatorics and graph theory II

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.

Plan of lectures
  • 22.2. Perfect matchings: Tutte's theorem, Edmonds-Gallai decomposition, Petersen's theorem.
  • 29.2. Edmonds' blossom algorithm for finding largest matching.
  • 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.
  • 14.3. The proof of Tutte's and Wagner's theorems. Density of Kk-minor-free graphs. (We skipped the part on Hadwiger's conjecture.)
  • 21.3. Graphs on surfaces: classification of surfaces, their representation, genus and generalized Euler's formula.
  • 28.3. Graph coloring: Heawood's formula, Vizing's and Brooks' theorems.
  • 4.4. Proof of Vizing's theorem. Chordal graphs: structural characterizations, clique, independence and chromatic number.
  • 11.4. Perfect graphs: examples, perfect graph theorems and their applications.
  • 18.4. Hamilton cycles: Dirac's and Ore's theorems, Chvátal's closure.
  • 25.4. Tutte's polynomial: equivalent definitions, related graph invariants.
  • 2.5. Enumeration: properties of power series coefficients, exponential generating functions.
  • 9.5. Symmetries: Burnside's lemma and Polya's enumeration.
  • 16.5. Extremal combinatorics: Turán's theorem, Erdos-Ko-Rado's and Erdos-Szekeres' theorems.
  • 23.5. Reserve.
Syllabus
  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).

Other materials

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

  • Other results on perfect matchings (counting, algorithm).
  • 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).