NDMI073 Kombinatorika a grafy III - ZS 2011/12

Přednáška se bude konat v úterý od 15:40 do 17:10 v učebně S1 v budově na Malostranském náměstí; cvičení bude probíhat také v S1 a to hned po přednášce od 17:20 do 18:50. Cvičení povede Jan Volec.

Přednáška je určena zejména studentům, kteří uvažují o diplomové práci z oblasti kombinatoriky, teorie grafů, optimalizace nebo příbuzného oboru. V přednášce se pak zaměříme na pokročilejší partie kombinatoriky, zejména teorie grafů. Mezi probíraná témata budou patřit zejména základy teorie grafových minorů, stromová šířka, vybíravost grafů, Regularity Lemma s jeho jednoduchými aplikacemi a některé pokročilejší věty z extremální kombinatoriky.

Sylabus přednášky bude podobný předloňskému běhu a loňskému běhu přednášky. Studenti, kteří absolvovali přenášku NDMI012 Kombinatoriky a grafy II ve školním roce 2006/07 nebo 2007/08 by měli kontaktovat přednášejícího před zápisem přednášky vzhledem k možnému překryvu sylabů.

Zkouška

Při zkoušce bude požadována znalost vět z přednášky (včetně důkazů) a řešení příkladů, které byly na cvičení (viz seznam níže), včetně schopnosti použít postupy vedoucí k jejich vyřešení na podobné příklady.

Zápočet

Získání zápočtu je podmíněno aktivní účastí na cvičeních k přednášce a spočítaním stanoveného množství zadaných domacích úkolů (podrobnosti stanovuje cvičící). Studentům, kteří získali zápočet v minulých letech, stačí k získání zápočtu spočítat stanovené množství domacích úkolů.

Literatura

• B. Bollobas: Modern graph theory, Springer, 1998.
• R. Diestel: Graph theory, Springer, 2005.
• J. A. Bondy, U. S. R. Murty: Graph theory with applications, Springer, 2008.
• S. Jukna: Extremal combinatorics with applications in computer science, Springer, 2001.

Obsah přednášky

Příklady ze cvičení

• Dokažte, že vnějškově rovinné grafy jsou právě grafy, které neobsahují K₄ ani K_2,3 jako minor.
• Nechť H je graf maximálního stupně tři. Pak libovolný graf G obsahuje H jako minor právě tehdy, když G obsahuje podrozdělení H.
• Dokažte, že každý graf s minimálním stupněm tři obsahuje K₄ jako minor.
• Graf G je sériově-paralelní, pokud ho lze získat následujícími dvěma operacemi z grafů s dvěma význačnými vrcholy J a S, začínajíce s hranou, jejíž konce jsou J a S.
  Paralelní spojení: z grafu G s J a S a z grafu G' s J' a S' vznikne graf identifikací J a J' a identifikací S a S'.
  Sériové spojení: z grafu G s J a S a z grafu G' s J' a S' vznikne graf identifikací S a J'.
  Dokažte: Nechť G je 2-souvislý graf. G je sériově-paralelní právě tehdy když neobsahuje K4 jako minor.
• Dokažte, že každý graf na vrcholech stromové šířky nejvýše k má nejvýše k x n hran.
• Ukažte (bez použití Courcellovy věty), že 3-barevnost grafů omezené stromové šířky lze rozhodovat v lineárním čase (stromová dekompozice je součástí zadání).
• Dokažte, že každý graf s minimálním stupněm 2ⁿ obsahuje K_n jako minor.
• Dokažte, že každý graf na n vrcholech s maximální nezávislou množinou velikosti nejvýše a obsahuje Kn/2a jako minor.
• Dokažte, že každý k-spojitelný graf je (2k-1)-souvislý.
• Pro t=1,2, nalezněte nejmenší k, že každý k-souvislý graf je t-spojitelný.
• Dokažte bez použití Szemerédiho regularity lemmatu Removal Lemma pro K_1,2.
• Dokažte Removal Lemma pro obecné grafy.
• Zformulujte a dokažte Szemerédiho Regularity lemma pro orientované grafy.
• Dokažte, že vybíravost grafu není omezena žádnou funkcí barevnosti grafu. Speciálně, nalezněte bipartitní grafy s libovolně velkou vybíravostí.
• Charakterizujte souvislé grafy, jejichž vybíravost je rovna jejich maximálnímu stupni zvětšenému o jedna. (Návod: Použijte Brooksovu větu.)
• Nalezněte příklad rovinného grafu, který není 4-vybíravý.
• Nalezněte příklad rovinného grafu bez trojúhelníků, který není 3-vybíravý.
• Dokažte, že každý rovinný graf bez trojúhelníků je 4-vybíravý.
• Dokažte, že pokud G je vlastní třída grafů uzavřená na minory, pak vybíravost všech grafů v G je omezená.
• Charakterizujte 2-vybíravé grafy.
• Dokažte, že každá orientace bipartitního grafu je jaderná.
• Pomocí jaderných orientací ukažte, že každý rovinný bipartitní graf je 3-vybíravý.
• Dokažte Hales-Jewettovu větu ve verzi pro kombinatorické prostory.
• Dokažte, že pro každou konečnou množinu U množiny Z^m, každé obarvení Z^m pomocí konečně mnoha barev obsah homotetickou kopii U.
• Dokažte, že pro každé k libovolné obarvení přirozených čísel pomocí dvou barev obsahuje monochromatickou aritmetickou posloupnost délky k, jejíž diference má stejnou barvu jako tato posloupnost.