Kombinatorika a teorie grafů II - ZS 2008/09

Přednáška se koná v pondělí od 12:20 do 13:50 v posluchárně S4. Cvičení jsou od 14:00 do 15:30 v posluchárnách S7 a S8 po přednášce. Cvičení v S7 vede Tomáš Gavenčiak a já; cvičení v S8 Bernard Lidický. Informace o cvičení Bernarda Lidického včetně řešení některých příkladů ze cvičení lze nalézt zde.

Přednáška bude pokrývat několik vybraných témat z teorie grafů a kombinatoriky, zejména z párování v grafech, barevnosti grafů, grafových algoritmů, grafů na plochách, extremálni kombinatoriky a algebraické kombinatoriky. V porovnání s minulým rokem, bude přednáska výrazně jednodušší, neboť její těžší části byly přesunuty do nově vytvořené přednášky Kombinatorika a teorie grafů III.

Zkoušky

Zkouška bude ústní. Zadání zkoušky budou tvořit tři příklady, z nichž jeden bude důkaz věty z přednášky a jeden bude příklad ze cvičení. Čas na přípravu nebude omezen, ale lze očekávat, že by vyřešení všech tří příkladů nemělo zabrat více než dvě hodiny. Před přihlášením ke zkoušce je nutné získat zápočet.

Zkušební termíny jsou vypsány na následující dny: 16/1 (předtermín), 19/1, 23/1, 26/1, 30/1, 2/2, 6/2 a 20/2. Studijní informační systém (SIS) vám neumožní se zapsat na termíny 23/1, 30/1, 2/2, 6/2 a 15/2 bez toho, aniž byste měli zápočet zapsán v SISu. Na termíny 19/1 a 23/1 se lze přihlásit i bez zápočtu v SISu, ale v době konání zkoušky už zápočet musíte mít udělen (zapsán v SISu nebo v indexu). Další jeden až dva termíny budou vypsány dodatečně na dobu po zkouškovém období - sledujte, prosím, SIS.

Na zkoušku se přihlašuje pomocí studijního informačního systému na adrese https://is.cuni.cz/studium/login.php. Na všechny termíny se lze přihlašovat do jednoho dne před konáním zkoušky a odhlašovat se lze do dvou dnů. Aby se zamezilo zbytečným prodlevám při zkoušení, jsou termíny vypsány tak, že na začátek zkoušení se může přihlásit 10 studentů a pak vždy po hodině 5 studentů (termíny se budou dále přidávat na stejné dny po naplnění kapacity již vypsaných termínů). Ve stejný den se přihlašujte přednostně na termíny s dřívějším začátkem. Na zkoušku se dostavate přibližně v hodinu, na kterou jste se zapsali - pokud dorazíte o dřiv, nemusíte čekat před posluchárnou, vejděte dovnitř a dostanete příklady. Jak je též uvedeno výše, společenský oděv není vyžadován.

Ukázkové zadání zkouškové písemky

Odpřednesená látka

Literatura

• B. Bollobas: Modern graph theory, Springer, 1998.
• J. A. Bondy, U. S. R. Murty: Graph theory with applications, Springer, 2008.
• R. Diestel: Graph theory, Springer, 2005.
• S. Jukna: Extremal combinatorics with applications in computer science, Springer, 2001.
• J. Matoušek: Elliasův-Bassalygův odhad v teorii samoopravných kódů, http://kam.mff.cuni.cz/~matousek/kody-eb.ps.
• J. Matoušek: Šestnáct miniatur, http://kam.mff.cuni.cz/~matousek/la-appls.ps.
• M. Sudan: Algorithmic Introduction to Coding Theory, http://theory.lcs.mit.edu/~madhu/FT01/course.html.

Cvičení

Párování v grafech

• Každý 2k-regulární graf se sudým počtem hran má k-faktor.
• Každý 2k-regulární graf lze rozložit na k disjuktních 2-faktorů.
• Dokažte, že každý k-regulární hranově k-souvislý graf se sudým počtem vrcholů má perfektní párování. Platí toto tvrzení pro hranově (k-1)-souvislé grafy? (k-2)-souvislé grafy?
• Dokažte, že každý kubický graf bez mostů má perfektní párování obsahující zadanou hranu.
• Dokažte, že každý kubický graf bez mostů má perfektní párování vynechávající zadanou hranu.
• Dokažte, že každý kubický graf bez mostů má perfektní párování vynechávající dvě zadané hrany.
• Nalezněte kubický graf bez mostů, který obsahuje dvě nesousední hrany neležící ve společném párování.
• Nalezněte kubický graf G bez mostů různý od K₄, který obsahuje dvě hrany e a f takové, že G nemá párování obsahující e a neobsahující f.

Grafy v rovině a na plochách

• Dokažte, že graf je vnějškově rovinný právě tehdy když neobsahuje podrozdělení K_2,3 nebo K₄.
• Nalezněte minimální nerovinný graf, jehož žádný vlastní podgraf na alespoň třech vrcholech není maximální rovinný.
• Které grafy K_n lze vnořit do projektivní roviny? Na torus?
• Nalezněte nakreslení Petersenova grafu do projektivní roviny a na toru.
• Nalezněte nakreslení K_3,3 do projektivní roviny a na toru.
• Nalezněte dvě neizomorfní dobré nakreslení K₅ na toru.
• Určete rod grafu K_1,2,2,2.
• Nalezněte graf nakreslený do projektivní roviny a na torus, jehož všechny stěny mají sudou velikost, ale jehož barevnost je aspoň tři. Jsou takové grafy, jejichž barevnost je aspoň čtyři?

Barevnost grafů

• Nechť G je graf barevnosti k, jehož kažďý vlastní podgraf má barevnost nejvýše k-1. Pak G je hranově (k-1)-souvislý. Musí být i k-souvislý?
• Dokažte, že každý bipartitní graf je Vizingovy třídy I.
• Dokažte, že každý rovinný kubický graf bez mostů je Vizingovy třídy I.
• Nalezněte nekonečně mnoho hranově 3-souvislých kubických grafů bez mostů Vizingovy třídy II.
• Určete hranovou barevnost grafu úplného grafu na n vrcholech.

Tutteho polynom

• Určete Tutteho polynom pro kružnici délky k.
• Určete Tutteho polynom pro dva vrcholy spojené k hranami.
• Nechť G je rovinný graf a H graf duální k G. Pak platí, že T_G(x,y)=T_H(y,x).
• Orientace grafu je totálně cyklická, pokud každá hrana leží v orientované kružnici. Dokažte, že graf G má T_G(0,2) totálně cyklických orientací.

Pólyova enumerace

Následující příklady řešte pomocí metod zavedených na přednášce.
• Kolika různými neekvivalentními způsoby lze obarvit stěny čtyrstěnu červenou, zelenou a modrou barvou?
• Kolika různými neekvivalentními způsoby lze obarvit stěny dvanáctistěnu červenou, zelenou a modrou barvou?
• Kolika různými neekvivalentními způsoby lze obarvit stěny dvanáctistěnu červenou, zelenou a modrou barvou tak, aby každá barva byla použita alespoň jednou?
• Určete cyklický index krychle pro grupu rotací působící na jejich vrcholech a pomocí něj určete, kolika neekvivalentními způsoby lze obarvit její vrcholy pomocí n barev.

Lineární kódy

• Ověřte, že Hadamardův kód s 2^k-bitovými slovy má minimální vzdálenost 2^k-1.
• Nechť P je matice, jejíž sloupce jsou všechny nenulové vektory dimenze n+1 nad tělesem GF(q) takové, že žadné dva nejsou násobkem jeden druhého. Ukažte, že P je matice ranku n+1 s (qⁿ⁺¹-1)/(q-1) sloupci. Dále ukažte, že minimální vzdálenost lineárního kódu s paritní maticí P je 3.
• Nechť C je lineární [n,k,d]-kód nad tělesem GF(q) a C' je kód, který vznikne z C restrikcí na slova, jejiž složky leží v podtělese GF(q'). Omezte parametry kódu C' pomocí n, k a d.
• Dokažte, že existuje třída dobrých lineárních binárních kódů.
• Dokažte, že náhodný lineární binární kód je dobrý. Přesněji, nalezněte r a d takové, že lineární obal náhodných rn lineárně nezávislých n-bitových vektorů je skoro jistě kód s minimální vahou alespoň dn.

Extremální kombinatorika

• Nechť V₁,...,V_s jsou disjunktní (k-1)-prvkové množiny a nechť F je systém všech s-prvkových množin S, které obsahují právě jeden prvek z každé z množin V₁,...,V_s. Kolik množin tvoří F? Ukažte, že F nemá slunečnici s k lístky.
• Nechť n-k+1 < s <= n a nechť F je systém všech s-prvkových podmnožin množiny {1,...,n}. Dokažte, ze F nemá slunečnici s k lístky.
• Nechť F je systém podmnožin množiny {1,...,n}, ve kterém se každé dvě podmnožiny protínají. Nalezněte optimální horní odhad na velikost F.
• Navrhněte a dokažte kanonickou Ramseyovu větu pro grafy.
• Nechť K je úplných graf se spočetně nekonečně vrcholy, jehož hrany jsou obarveny dvěma barvami. Předpokládejme, že pro každá n, K obsahuje úplný graf na n vrcholech, jehož všechny hrany jsou červené. Obsahuje pak nutně K nekonečný úplný graf, jehož všechny hrany jsou červené?
• Nechť K_X,Y$ je úplný bipartitní graf se spočetně nekonečně velkými partitami, jehož hrany jsou obarveny dvěma barvami. Je pravda, že pro každé n graf K_X,Y musí nutně obsahovat monochromatický podgraf izomorfní K_n,n? Monochromatický úplný podgraf s jednou partitou velikosti n a druhou nekonečně velkou? Oběma nekonečně velkými?
• Dokažte, že každá částečně uspořádaná množina s rs+1 prvky buď obsahuje řetězec délky r+1 nebo antiřetězec délky s+1.
• Nalezněte částečně uspořádanou množinu, která neobsahuje nekonečný antiřetězec, ale kterou není možné pokrýt konečně mnoha řetězci.
• Dokažte, že každou konečnou částečně uspořádanou množinu lze pokrýt tolika antiřetězci, kolik je maximální délka jejího řetězce.
• Ukažte, že existuje nekonečný hypergraf, který má nekonečnou barevnost, ale každý jeho konečný podhzpergraf má barevnost malou.