Cvičení z kombinatoriky a grafů III (ZS 2011/2012)
Cvičení se koná každé úterý od 17:20 na Malé Straně v učebně S1, stránku k přednášce najdete zde.
Konzultace
Pokud budete chtít přijít na konzultaci, napište mi e-mail (janvolec-tady_neco_chybi-jikos.cz) a domluvíme se.
Zápočet
Získání zápočtu je podmíněno aktivní účastí na cvičeních a vyřešením
alespoň třetiny úloh z každé ze tří serií domacích úkolů. Zadaní úkolů
se bude objevovat v průběhu semestru na této stránce.
Co jsme dělali?
18.10.2011
Bylo dvojcvičení.
- G je vnějškově rovinný právě tehdy když neobsahuje K_4 ani K_2,3 jako minor,
- buď H graf max. stupně 3; potom G obsahuje podrozdělení H právě tehdy když G obsahuje H jako minor,
- je-li min. stupeň G alespoň 3, potom G obsahuje K_4 jako minor,
- každý sériově-paralelní graf neobsahuje K_4 jako minor,
- pokud G graf na n vrcholech má stromovou šířku nejvýše k, pak G má nejvýše k×n hran,
- pro každé k existuje lineární algoritmus, který pro graf G stromové šířky nejvýše k rozhodne, zda G je 3-obarvitelný.
1.11.2011
- Stromová šířka mřížky m × n (m ≥ n) je rovna přesně n,
- jsou-li X a Y dva sousední uzly stromového rozkladu G takové, že jeden není podmnožinou druhého a naopak, tak potom vrcholy X ∩ Y tvoří vrcholový řez v G,
- je-li G je graf se stromové šířky k a A množina vrcholů velikosti 3k+3, potom G obsahuje vrcholový řez B velikosti nejvýše k+1 takový, že pro každou komponentu C v G \ B podgraf indukovaný C ∪ B obsahuje nejvýše 2k+2 vrcholů z A.
15.11.2011
- Vlasnost obsahovat Hamiltonovskou kružnici lze vyjádřit v monadické logice druhého řádu (MSOL),
- je-li G rovinný graf nakreslený do roviny, H jeho duální graf a T libovolná kostra G, potom duály hran G neobsažených v T tvoří kostru H,
- je-li G rovinný graf, v jeho vrchol a G'(v,r) podgraf indukovaný vrcholy ve vzdálenosti nejvýše r od vrcholu v, potom G'(v,r) má stromový rozklad šířky 3r,
- každý graf s minimálním stupněm 2^n obsahuje K_n jako minor,
- každý k-spojitelný graf je vrcholově (2k-1)-souvislý,
- odhady na nejmenší k takové, aby platilo tvrzení každý k-souvislý graf je 2-spojitelný.
22.11.2011
- Existuje 5-souvislý rovinný graf který není 2-spojovaný,
- každý 4-souvislý nerovinný graf je 2-spojovaný,
- Removal lemma pro K_1,2 (počítáním, bez použití regularity lemmatu),
- Pro každé eps > 0 a 0 < d < 1 existuje bipartitní graf se stejně velkými partitami, který má hustotu hran v intervalu (d-eps,d+eps) a zároveň netvoří eps-regulární pár.
29.11.2011
- "Crash-kurz" k pravděpodobnostní metodě + Černovova nerovnost pro binomické rozdělení,
- pro každé eps > 0 a 0 < d < 1 existuje bipartitní graf se stejně velkými partitami, který má hustotu hran v intervalu (d-eps,d+eps) a zároveň tvoří eps-regulární pár,
- liší-li se pro všechny podmožiny A'⊆A velikosti eps×n a všechny podmnožiny B'⊆ velikosti eps×n hustota hran mezi A' a B' od hustoty hran mezi A a B nejvýše o eps, potom (A,B) tvoří eps-regulární pár,
6.12.2011
- Pro každé k a d existuje n_0 a eps takové, že každá eps-regulární dvojice (A,B) s |A|=|B|>n0 a e(A,B)>d|A||B| obsahuje K_k,k jako podgraf,
- pro každé k a d existuje n_0 takové, že každý graf s n > n_0 vrcholy a alespoň dn^2 hranami obsahuje K_k,k jako podgraf,
- Removal Lemma pro úplný graf na čtyřech vrcholech (K_4).
20.12.2012
- Erdös-Stone-Simonovitsova věta o limitě maximální hustoty grafu neobsahující daný graf H jako podgraf.
3.1.2011
- pro každé k existuje bipartitní graf který není k-vybíravý,
- Brooksova věta pro vybíravost: pokud G není úplný či lichá kružnice, potom vybíravost G je nejvýše max. stupeň G,
- pro každou vlastní třidu grafů C uzavřenou na minory existuje konstanta K taková, že každý graf z C má vybíravost nejvýše K.
10.1.2012
Bylo dvojcvičení.
- Pro každé k existuje n takové, že pro libovolné obarvení čísel 1,…,n pomocí dvou barev existuje monochromatická aritmetická posloupnost délky k, jejíž barva je stejná jako barva její diference,
- Gallai-Wittova věta: pro každou konečnou množinu H v Z^i a každé obarvení Z^i konečným počtem barev existuje monochromatická homotetická kopie H,
- zobecnění Hales-Jewettovy věty na kombinatorické prostory dimenze m (aneb existuje monochromatický pattern s m různými hvězdičkami),
- neobsahuje-li orientovaný graf lichý orientovaný cyklus, potom má kernel,
- rovinné bipartitní grafy jsou 3-vybíravé,
- existuje rovinný graf, který není 4-vybíravý,
- existuje rovinný graf bez trojúhelníků, který není 3-vybíravý,
- každý rovinný graf bez trojúhelníků je 4-vybíravý.
Objevíte-li někde chybu, dejte mi, prosím, vědět.
Stránka vytvořena za pomoci programů vi, bash a perl. Poslední změna: 10.01.2012