Kombinatorika a grafy 2

Schedule:

  • Lecture on Tuesdays 14:00-15:30 in my office 323.
  • Tutorials (lead by Andreas Feldmann) on Mondays 10:40-12:10 in S10.

Grading: according to the final (oral) exam, focusing on the proofs and applications.

Plan of lectures
  • 11.10. and 18.10. perfect matchings
  • 25.10. graphs on surfaces
  • 1.11. graph minors
  • 15.11. edge and vertex coloring
  • 22.11. perfect graphs
  • 29.11. Hamilton cycles
  • 6.12. Tutte's polynomial
  • 13.12. and 20.12. enumeration
  • 3.1. extremal theory
  • 10.1. self-correcting codes
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.
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).