slama.dev

Kombinatorika a Grafy II

poznámky poznamky Icon · 1. 3. 2021 · 🇨🇿 · dostupné v PDF · [upravit]

Úvodní informace

Tato stránka obsahuje moje poznámky z přednášky Martina Kouteckého z akademického roku 2020/2021 (MFF UK). Pokud by byla někde chyba/nejasnost, nebo byste rádi něco přidali, tak stránku můžete upravit pull requestem (případně mi dejte vědět na mail).

1. přednáška

Největší párování

Definice: Párování v G=(V,E)G = \left(V, E\right) je M⊆EM \subseteq E t. ž. ∀v∈V∃≤1\forall v \in V \exists \le 1 hrana e∈M:v∈ee \in M: v \in e

Definice (volný vrchol) (vzhledem k MM) je vrchol, kterého se nedotýká žádná hrana párování.

Definice (střídavá cesta) (vzhledem k MM) je cesta, na které se střídají hrany v párování a hrany mimo párování: u0,…,uku_0, \ldots, u_k, kde každá sudá/lichá hrana je v MM, lichá/sudá není v MM

Tvrzení: Nechť G=(V,E)G = \left(V, E\right) je graf, MM párování v GG. Pak GG obsahuje VSC (vzhledem k MM), právě když MM není největší párování v GG.

Definice (květ): lichá „střídavá“ kružnice s vrcholem v1v_1, ke kterému přiléhají dvě hrany ∉M\not\in M Definice (stonek): střídavá cesta z v1v_1 (i nulové) délky končící volným vrcholem (dál od květu)

Definice (kytka): květ + stonek

Definice (kontrakce hrany): Nechť G=(V,E)G = \left(V, E\right) je neorientovaný graf a e={u,v}e = \left\{u, v\right\} jeho hrana. Zápis G.eG . e označuje graf vzniklý z GG kontrakcí („smrštěním“) hrany ee do jednoho vrcholu:

Tvrzení: Nechť CC je květ v grafu GG. Potom párování MM v GG je maximální, právě když M∖E(C)M \setminus E(C) je maximální párování v grafu G.CG . C, tj. s květem CC zkontrahovaným do jediného vrcholu. Navíc pokud znám VSC pro M.CM . C, tak v poly. čase najdu VSC pro MM v GG.

Důkaz: Tady je sketchy důkaz, tady je míň sketchy důkaz.

Algoritmus (Edmondsův „zahradní/blossom“): vstupem je graf GG a jeho libovolné párování MM, třeba prázdné. Výstupem je párování M′M', které je alespoň o 11 větší, než MM, případně MM pokud bylo maximální.

Tvrzení: Edmondsův algoritmus spuštěný na GG a MM doběhne v čase O(n⋅(n+m))\mathcal{O}(n \cdot (n + m)) a najde párování M′M' alespoň o 11 hranu větší než MM, případně oznámí, že MM je největší ⇒\Rightarrow nejlepší párování lze nalézt v čase O(n2(n+m))\mathcal{O}(n^2 (n + m)).

Důkaz: nejvýše nn-krát se vždy zrekurzíme s tím, že při každém rekurzení prohledáme celý graf (O(n+m)\mathcal{O}(n + m)). Tohle celé opakujeme nejvýše dokud nejsou všechny vrcholy zpárované, tedy nn-krát.

2. přednáška

Definice (perfektní párování): Párování MM je perfektní, pokud neexistuje v GG žádný volný vrchol.

Tutteova věta

Definice (Tutteova podmínka): ∀S⊆V:odd(G−S)≤∣S∣\forall S \subseteq V: \mathrm{odd}(G - S) \le |S|

Věta (Tutteova věta): GG má perfektní párování   ⟺  \iff platí Tutteova podmínka.

Důkaz: ⇒\Rightarrow obměna: neplatí TP ⇒\Rightarrow není PP. Nechť ∃S⊆V\exists S \subseteq V t. ž. odd(G−S)>∣S∣\mathrm{odd(G - S)} > |S|. V perfektním párování se alespoň 11 vrchol z každé liché komponenty musí spárovat s nějakým z SS, ale těch není dostatek.

⇐\Leftarrow nechť GG splňuje Tutteovu podmínku. ∣V∣|V| je sudá (nastavíme SS prázdnou). Dokážeme, že GG má PP indukcí podle počtu nehran.

Nechť S={v∈V ∣ deg⁡(v)=n−1}={v∣v je spojenyˊ se vsˇemi vrcholy}S = \left\{v \in V\ |\ \deg(v) = n - 1\right\} = \left\{v \mid \text{$v$ je spojený se všemi vrcholy} \right\}

Indukujeme dvakrát: G1=G+e1G_1 = G + e_1 a G2=G+e2G_2 = G + e_2 díky předchozímu pozorování splňují TP a spolu s IP ⇒∃\Rightarrow \exists PP M1,M2M_1, M_2 v G1,G2G_1, G_2

Těžší případ: e1∈M1,e2∈M2,H=(V,M1∪M2)e_1 \in M_1, e_2 \in M_2, H = (V, M_1 \cup M_2)

Věta (Petersen): každý 33-regulární 22-souvislý (vrcholově i hranově, pro 3-regulární grafy je to to samé; alternativně můžeme říct graf bez mostů a artikulací) graf má PP.

Důkaz: Nechť G=(V,E)G = (V, E) je 33-regulární a 22-souvislý. Chci ukázat, že GG splňuje TP. Předpokládejme danou S⊆VS \subseteq V.

  1. každá komponenta G−SG - S je v GG spojena aspoň dvěma hranami s SS
    • je 22-souvislý, nemáme mosty
  2. dokážeme, že každá lichá komponenta G−SG - S je s SS spojena lichým počtem hran:
    • nechť LL je lichá komponenta G−SG - S; pak: ∑x∈V(L)deg⁡G(x)=3−reg.3∣V(L)∣⏟licheˊ cˇıˊslo=2(# hran vedoucıˊch uvnitrˇ L)⏟sudeˊ cˇıˊslo+1(# hran vedoucıˊch uvnitrˇ L)⏟musıˊ byˊt licheˊ\sum_{x \in V(L)}\deg_G(x) \overset{3-\text{reg.}}{=} \underbrace{3|V(L)|}_{\text{liché číslo}} = \underbrace{2 (\text{\# hran vedoucích uvnitř $L$})}_{\text{sudé číslo}} + \underbrace{1 (\text{\# hran vedoucích uvnitř $L$})}_{\text{musí být liché}}

∣S∣≥odd(G−S)|S| \ge \mathrm{odd}(G - S), tedy TP platí a graf má perfektní párování.

3. přednáška

Tutte v2.0

Lemma (o kontrahovatelné hraně = LoKH): Nechť GG je vrcholově 33-souvislý různý od K4K_4. Potom GG obsahuje hranu t. ž. G∖eG \setminus e je 3-souvislý.

Důkaz: Sporem – nechť GG je 3-souvislý ale neexistuje žádná hrana, která jde zkontrahovat. Tedy ∀e∈E:G∖e\forall e \in E: G \setminus e není 33-souvislý.

Lemma (pomocné): ∀e={x,y}∃ze∈V∖{x,y}\forall e = \left\{x, y\right\} \exists z_e \in V \setminus \left\{x, y\right\} t. ž. {x,y,ze}\left\{x, y, z_e\right\} tvoří vrcholový řez v G, navíc každý z {x,y,ze}\left\{x, y, z_e\right\} má alespoň jednoho souseda v každé komponentě G∖{x,y,ze}G \setminus \left\{x, y, z_e\right\}.

Důkaz (způsob z přednášky): Vím, že G∖eG \setminus e není 33-souvislý, tedy má vrcholový řez velikosti 22. Nechť vev_e je vrchol vzniklý kontrakcí e={x,y}e = \left\{x, y\right\}. Řez velikosti 22 obsahuje vev_e, jinak by to byl řez už pro GG (obsahoval by vrcholy z původního grafu, které nekontrahujeme).

Označme řez ve,zev_e, z_e. Po rozkontrahování vidíme, že ∀{x,y,ze}\forall \left\{x, y, z_e\right\} musí mít souseda v každé komponentě (jinak spor s 3-souvislostí). Tedy zez_e je hledaný vrchol.

Důkaz (moje intuice): Pokud by neplatilo (existovala by taková hrana), tak máme hranu, přes kterou kontrahujeme. Jelikož pro tu hranu platí, že neexistuje zz, které spolu s jejími vrcholy tvoří řez, tak bude graf i po kontrakci 33-souvislý.

Pro důkaz původního lemmatu si zvolím e={x,y}∈Ee = \left\{x, y \right\} \in E a zez_e z pomocného tvrzení tak, aby nejmenší komponenta G−z,y,zeG - z, y, z_e byla co nejmenší (co do počtu vrcholů).

Protože zez_e má souseda ve všech komponentách, má nějakého souseda u∈C,f={ze,u}u \in C, f = \left\{z_e, u\right\} (kde CC je naše nejmenší komponenta). Pomocné tvrzení pro ff dá nějaký zf∈Vz_f \in V t. ž. {ze,zf,u}\left\{z_e, z_f, u\right\} je vrcholový řez GG. Chceme dokázat, že G−ze,zf,uG - z_e, z_f, u má menší komponentu než CC.

Nechť DD je komponenta G−ze,zf,uG - z_e, z_f, u neobsahující x,yx, y. Existuje, protože x,yx, y jsou spojené a graf se rozpadne alespoň na 22 komponenty. Tvrdím, že D⊆C∖{u}D \subseteq C \setminus \left\{u\right\}, protože DD nemůže obsahovat ze,zf,uz_e, z_f, u (vrcholy řezu), x,yx, y (z definice DD), ale uu má nějakého souseda v DD (podle pomocného tvrzení, uu má sousedy ve všech komponentách řezu), takže v DD ještě něco zbyde. Navíc ho tam mělo uu i předtím, takže opravdu D⊆C∖{u}D \subseteq C \setminus \left\{u\right\}. Tedy ∣D∣<∣C∣|D| < |C|, což je spor s minimalitou.

Věta (Tutteova charakterizace 3-souvislých grafů): Graf GG je 3-souvislý   ⟺  \iff existuje posloupnost K4≅G0,G1,…,Gn≅GK_4 \cong G_0, G_1, \ldots, G_n \cong G t. ž. ∀i∈[n],Gi−1\forall i \in [n], G_{i - 1} vznikne z GiG_i kontrakcí hrany, navíc GiG_i má všechny vrcholy stupně ≥3\ge 3.

Důkaz: ⇒\Rightarrow Induktivní aplikace lemmatu o kontrahovatelné hraně.

⇐\Leftarrow Mějme G0,…,GnG_0, \ldots, G_n dle předpokladu. Chceme, že Gn≅GG_n \cong G je 3-souvislý. Indukcí:

Obměnou nechť GiG_i má vrcholový řez velikosti 2, označme ho R={x,y}R = \left\{x,y\right\}. Pak každá komponenta Gi−RG_i - R má alespoň 2 vrcholy (osamocený vrchol zz mohl sousedit jen s řezem, ale ten je velikosti 2, což je spor se stupněm vrcholů ≥3\ge 3 pro vv).

Pak ale Gi−1G_{i - 1} nebyl 3-souvislý, rozborem toho, kde vznikla hrana:

Minory

Definice (minor): Nechť H,GH, G jsou grafy. Pak HH je minor GG (nebo že GG obsahuje HH jako minor), značíme H⪯GH \preceq G, pokud HH lze získat z GG posloupností mazání vrcholů, mazání hran nebo kontrakcí hran.

Věta (Kuratowského): GG rovinný   ⟺  \iff neobsahuje dělení K5K_5 ani K3,3K_{3, 3}

Věta (Kuratowski 1930, Warner 1937): Následující jsou ekvivalentní:

  1. GG je rovinný
  2. GG neobsahuje dělení K5K_5 ani K3,3K_{3, 3} jako podgraf
  3. GG neobsahuje K5K_5 ani K3,3K_{3, 3} jako minor.

Důkaz:

Pokračování v další přednášce…

4. přednáška

Označme CC kružnici ohraničující stěnu G′′\mathcal{G}'', v níž ležel (v G′\mathcal{G}' vrchol vev_e) – musí to být kružnice, protože v rovinném nakreslení každého 22-souvislého grafu je každá stěna kružnice.

3 případy:

Kreslení grafů na plochy

Definice: Nechť X⊆Rn,Y⊆RmX \subseteq \mathbb{R}^n, Y \subseteq \mathbb{R}^m. Potom homeomorfismus z XX na YY je funkce f:X↦Yf: X \mapsto Y, která je spojitá, bijekce a f−1f^{-1} je spojitá. X,YX, Y jsou homeomorfní (X≅YX \cong Y) pokud mezi nimi existuje homeomorfismus.

Definice (plocha): kompaktní (uzavřená, omezená), souvislá (např. oblouková – každé dva body můžu propojit obloukem), 22-rozměrná varieta bez hranice (dostatečně malé okolí každého bodu je homeomorfní otevřenému okolí v R2\mathbb{R}^2).

Operace s plochami, přes které umíme všechny zkonstruovat:

Pro g∈{0,1,…}g \in \left\{0, 1, \ldots\right\} nechť ∑g\sum_g značí plochu zvniklou ze sféry přidáním gg uší, tak říkáme, že ∑g\sum g je orientovatelná plocha rodu gg.

Pro g∈{1,2,…}g \in \left\{1, 2, \ldots\right\} nechť ∏g\prod_g značí plochu zvniklou ze sféry přidáním gg křížítek, tak říkáme, že ∏g\prod g je neorientovatelná plocha rodu gg.

Fakt: Každá plocha je homeomorfní právě jedné z posloupností ∑0,∏1,∑1,∏2,…\sum_0, \prod_1, \sum_1, \prod_2,\ldots

Fakt: Přidám-li ke sféře (=Σ0= \Sigma_0) k≥0k \ge 0 uší a l≥1l \ge 1 křížítek, vznikne neorientovatelná plocha homeomorfní ∏2k+l\prod_{2k + l} (≈\approx „přidání dvou křížítek je jako přidání ucha,“ pokud už tam bylo ≥1\ge 1 křížítko)

5. přednáška

Definice (nakreslení grafu): G=(V,E)G = (V, E) na plochu Γ\Gamma je zobrazení φ\varphi t. ž.:

Definice (stěna nakreslení): souvislá komponenta Γ∖((⋃e∈Eφ(e))∪(⋃x∈Vφ(x)))\Gamma \setminus \left(\left(\bigcup_{e \in E}^{\varphi(e)}\right) \cup \left(\bigcup_{x \in V}^{\varphi(x)}\right)\right)

Definice (buňkové nakreslení): každá stěna je homeomorfní otevřenému kruhu v R2\mathbb{R}^2.

Připomenutí: G=(V,E)G = (V, E) souvislý ⇒\Rightarrow v každém rovinném nakreslení platí ∣V∣−∣E∣+S=2|V| - |E| + S = 2

Definice (Eulerova charakteristika plochy): charakteristika plochy Γ\Gamma je

X(Γ)={2−gΓ≅∏(g≥1)2−2gΓ≅∑(g≥0) =2−# krˇıˊzˇıˊtek−2⋅# usˇıˊ \begin{aligned} \Chi(\Gamma) &= \begin{cases} 2 - g & \Gamma \cong \prod (g \ge 1) \\ 2 - 2g & \Gamma \cong \sum (g \ge 0) \end{cases} \\ \ &= 2 - \text{\# křížítek} - 2 \cdot \text{\# uší} \end{aligned}

Věta (zobecněná Eulerova formule): Nechť máme nakreslení grafu G=(V,E)G = (V, E) na ploše Γ\Gamma, které má SS stěn. Pak ∣V∣−∣E∣+∣S∣≥X(Γ)|V| - |E| + |S| \ge \Chi(\Gamma). Pokud je buňkové, tak dokonce ∣V∣−∣E∣+∣S∣=X(Γ)|V| - |E| + |S| = \Chi(\Gamma).

Důkaz (rovnosti): idea je indukce podle rodu Γ\Gamma

Mějme buňkové nakreslení G=(V,E)G = (V, E) na Γ≅Πg\Gamma \cong \Pi_g

Nechť KK je křížítko na Γ\Gamma, x1,…,xkx_1, \ldots, x_k jsou body KK (ne nutně vrcholy grafu), kde hrany GG kříží KK

Vytvoříme G′G' přidáním dvou dělících vrcholů na každou hranu křížící KK těsně vedle x1,…,xkx_1, \ldots, x_k („před a za křížítkem“). Děláme to proto, že jedna hrana by mohla procházet křížítkem na více místech a bylo by to pak dost rozbitý.

Vytvoříme G′′G'' přidaním cest délky 22 k sousedním vrcholům z předchozího kroku. Vznikne tím kružnice CC obcházející KK.

Vytvoříme G′′′G''' odebráním všeho uvnitř CC.

L(G′′′)=X(Πg−1)=X(Γ)+1∣dle IPL(G''') = \Chi(\Pi_{g - 1}) = \Chi(\Gamma) + 1 \qquad \mid \text{dle IP} L(G′′′)−1=L(G′′)=L(G′)=L(G)∣z vyˊpocˇtuL(G''') - 1 = L(G'') = L(G') = L(G) \qquad \mid \text{z výpočtu}

Tedy X(Γ)=L(G)\Chi(\Gamma) = L(G)

Důsledek: Každý graf GG nakreslitelný na plochu Γ\Gamma splní ∣E∣≤3∣V∣−3X(Γ)|E| \le 3|V| - 3\Chi(\Gamma), pokud ∣V∣≥4|V| \ge 4

Tvrzení: Nechť Γ\Gamma je plocha, Γ≠Σ0\Gamma \neq \Sigma_0, nechť GG je graf nakreslený na Γ\Gamma, potom GG obsahuje vrchol stupně ≤⌊5+49−24X(Γ)2⌋\le \left\lfloor \frac{5 + \sqrt{49 - 24\Chi(\Gamma)}}{2} \right\rfloor

Důkaz: Mějme GG podle předpokladu. Opět značíme v(G),e(G)v(G), e(G) jako počet vrcholů a hran. Rozlišíme 33 případy:

Důsledek (Heawoodova formule, 1890): Pokud Γ≇∑0\Gamma \not\cong \sum_0, tak každý graf nakreslitelny na Γ\Gamma je nejvýš H(Γ)=1+⌊5+49−24X(Γ)2⌋=⌊7+49−24X(Γ)2⌋H(\Gamma) = 1 + \left\lfloor \frac{5 + \sqrt{49 - 24 \Chi(\Gamma)}}{2} \right\rfloor = \left\lfloor \frac{7 + \sqrt{49 - 24 \Chi(\Gamma)}}{2} \right\rfloor-obarvitelný

6. přednáška

Vrcholové barvení

Definice: GG je dd-degenerovaný ≡\equiv každý podgraf HH grafu GG má δ(H)≤d\delta(H) \le d

Definice (eliminační pořadí): Alternativní definice dd-degenerovanosti: graf je dd-degenerovaný   ⟺  ∃\iff \exists pořadí vrcholů (eliminační) v1,…vnv_1, \ldots v_n t. ž. ∀i:Gi:=G−{v1,…,vi}:δ(Gi)≤d\forall i: G_i := G - \left\{v_1, \ldots, v_i\right\}: \delta(G_i) \le d a vi−1v_{i - 1} má ≤d\le d sousedů v GiG_i

(👀): GG je Δ(G)\Delta(G)-degenerovaný (triviálně) ⇒X(G)≤Δ(G)+1\Rightarrow \Chi(G) \le \Delta(G) + 1 (z pozorování výše)

Lemma: GG souvislý graf a δ(G)<Δ(G)\delta(G) < \Delta(G), pak X(G)≤Δ(G)\Chi(G) \le \Delta(G)

Důkaz: Tvrdím, že GG je (Δ(G)−1\Delta(G) - 1)-degenerovaný. Volme HH neprázdný podgraf GG a dokazujeme, že v HH existuje vv stupně ≤Δ(G)−1\le \Delta(G) - 1

Věta (Brooks, 1941): Nechť GG je souvislý graf který není úplný a není lichá kružnice. Pak X(G)≤Δ(G)\Chi(G) \le \Delta(G)

Důkaz: nechť X=X(G),Δ=Δ(G)\Chi = \Chi(G), \Delta = \Delta(G) a navíc předpokládám, že GG je Δ\Delta-regulární (jinak viz předchozí lemma.

  1. kV(G)=1k_V(G) = 1
    • máme artikulaci, vrchol artikulace vv měl souseda v obou částech grafu, proto deg⁡G1(v),deg⁡G2(V)<Δ\deg_{G_1}(v), \deg_{G_2}(V) < \Delta
    • podle lemmatu (G1G_1 a G2G_2 nejsou regulární) lze G1G_1 i G2G_2 Δ\Delta-obarvit a stačí přepermutovat barvy, aby měl v obou obarveních stejnou
  2. kV(G)=2k_V(G) = 2
    • dobré případy (lze slepit)
      • b1(x)=b1(y)b_1(x) = b_1(y) a b2(x)=b2(y)b_2(x) = b_2(y)
      • b1(x)≠b1(y)b_1(x) \neq b_1(y) a b2(x)≠b2(y)b_2(x) \neq b_2(y)
    • těžší případ – na jedné straně stejné, na druhé různé
      • b1(x)=b1(y)b_1(x) = b_1(y) a b2(x)≠b2(y)b_2(x) \neq b_2(y)
        • pokud deg⁡G1(x)\deg_{G_1}(x) nebo deg⁡G1(y)≤Δ−2\deg_{G_1}(y) \le \Delta - 2, tak po přidání hrany půjde použít lemma a vrcholy budou mít různou barvu a máme dobrý případ
          • nemůže se stát, že by např. druhý měl deg⁡G1=Δ\deg_{G_1} = \Delta, protože musí vidět i do druhé komponenty
        • nebo deg⁡G1(x)=deg⁡G1(y)=Δ−1\deg_{G_1}(x) = \deg_{G_1}(y) = \Delta - 1
          • pak musí deg⁡G2(x)=deg⁡G2(y)=1\deg_{G_2}(x) = \deg_{G_2}(y) = 1 (stupeň je celkově Δ\Delta)
          • z předpokladu máme k použití alespoň 33 barvy, přebarvím jimi xx a yy a máme dobrý případ
  1. kV(G)≥3k_V(G) \ge 3 – použiji lemma o třešničce (souvislý graf, který není klika, obsahuje třešničku)
    • seřadím vrcholy jako v1=x,v2=y,…,vn=zv_1 = x, v_2 = y, \ldots, v_n = z tak, aby ∀vi:3≤i≤n−1\forall v_i: 3 \le i \le n - 1 měl alespoň jednoho souseda napravo a barvím (hladově):
      • umíme získat jako BFS vrstvy od zz, kromě xx a yy
      • 33-souvislost využívám k tomu, že i po odstranění xx a yy graf bude stále nějakou kostru mít a bude tedy stále souvislý
      • b(x)=b(y)=1b(x) = b(y) = 1
      • b(v3)…b(v_3)\ldots má ≥1\ge 1 neobarveného souseda ⇒\Rightarrow je nějaká nepoužitá z Δ\Delta barev
      • …\ldots
      • b(vn)…b(v_n)\ldots všichni sousedé už obarvení, ale dva sousedé (x,yx, y) mají stejnou barvu, tedy zz vidí ≤Δ−1\le \Delta - 1 barev a jedna je volná

Pár poznámek

Hadwigerova domněnka: Kt̸⪯mGK_t \not\preceq_m G (není minor)⇒X(G)<t \Rightarrow \Chi(G) < t

Tvrzení: GG nakreslitelný na Kleinovu láhev ⇒G\Rightarrow G je 66-obarvitelný.

Důkaz: Z Eulerovy formule plyne, že platí jedno z následujících:

Hranové obarvení

Definice: b:E↦Bb: E \mapsto B (barvy) t. ž. ∀e≠f∈E,e∩f≠∅⇒b(e)≠b(f)\forall e \neq f \in E, e \cap f \neq \emptyset \Rightarrow b(e) \neq b(f). Hranová barevnost GG (“chromatic index”) X′(G)\Chi'(G) je min. počet barev pro hranové barvení GG.

7. přednáška

Věta (Vizing, 1964): Pro každý graf GG platí, že Δ(G)≤X′(G)≤Δ(G)+1\Delta(G) \le \Chi'(G) \le \Delta(G) + 1

Perfektní grafy

Věta (Slabá věta o perfektních grafech, 1972): GG je perfektní   ⟺  \iff Gˉ\bar{G} je perfektní.

8. přednáška

Chordální grafy

Definice (chordální graf): Graf je chordální, pokud neobsahuje Ck,k≥4C_k, k \ge 4 jako in. podgraf.

Definice: Nechť x,yx, y dva nesousední vrcholy GG. RR je x-yx{\text -}y-řez, pokud je to řez takový, že x,yx, y patří do různých komponent G∖RG \setminus R.

Tvrzení: GG je chordální   ⟺  \iff pro každé dva nesousední vrcholy x,y∈V,x≠yx, y \in V, x \neq y existuje x-yx{\text -}y-řez, který je klika.

Důkaz: ⇐\Leftarrow nechť GG není chordální, tedy obsahuje indukovanou kružnici C4C_4. Uvážíme-li dva její nesousední vrcholy, tak jakýkoliv řez musí obsahovat vrcholy z horní a dolní cesty mezi xx a yy. Ty nesousedí, tedy řez nebude klika.

⇒\Rightarrow nechť GG je chordální, x,yx, y nesousední. Nechť RR je x-yx{\text -}y-řez s co nejméně vrcholy. Tvrdím, že RR tvoří kliku.

Pro spor: RR není klika ⇒\Rightarrow obsahuje u,vu, v nesousedy. Protože RR je nejmenší, má uu i vv sousedy na obou stranách. Jelikož jsou to komponenty souvislosti, tak tam bude existovat cesta. Vezmu nejkratší cesty Px,PyP_x, P_y v komponentách GxG_x, GyG_y. Vrcholy Px,PyP_x, P_y nesousedí (jinak by RR nebyl řez), Px−u−Py−vP_x-u-P_y-v tvoří indukovaný cyklus.

Definice: Vrchol xx je v grafu GG simpliciální, pokud jeho sousedství NG(x)N_G(x) tvoří kliku GG.

Věta: Každý chordální graf (kromě prázdného) obsahuje simpliciální vrchol.

Věta: Každý chordální graf je buď úplný, nebo obsahuje dva nesousední simpliciální vrcholy.

Důkaz: indukcí podle ∣V(G)∣|V(G)|

Definice (PES): Perfektní eliminační schéma (PES) grafu GG je pořadí vrcholů v1,…,vnv_1, \ldots, v_n t. ž. ∀i∈[n]\forall i \in [n] platí, že leví sousedé viv_i (={vj∣j<i,vjvi∈E}= \left\{v_j \mid j < i, v_jv_i \in E\right\}) tvoří kliku.

Věta: G je chordální   ⟺  \iff G má PES.

Důkaz: ⇐\Leftarrow obměnou nechť GG není chordální a má tedy indukovanou kružnici velikosti alespoň 44. Pro spor nechť máme PES. Nejlevější vrchol špatné kružnice v PES nemá souseda na této kružnici, což je spor s definicí PES.

⇒\Rightarrow nechť GG je chordální. Má tedy simpliciální vrchol vnv_n. Jeho sousedé tvoří kliku a G−vnG - v_n je opět chordální (indukovaný graf chordálního je opět chordální) a opakujeme, čímž vznikne PES pro GG.

Důsledek: pro daný graf GG lze v polynomiálním čase rozhodnout, zda je chordální.

Důkaz: Trháme simpliciální vrcholy, které chordální graf musí vždy mít – ty umíme v polynomiálním čase najít otestováním všech sousedů. Pokud simpliciální vrchol v nějakém bodě nenajdeme, tak graf chordální být nemohl.

Důsledek: chordální grafy jsou perfektní.

Důkaz: Je-li graf GG chordální, pak má PES, pomocí kterého ho umíme obarvit tak, aby měl nejvýše ω(G)\omega(G). Jelikož je navíc každý indukovaný podgraf chordálního grafu také chordální, tak platí i pro indukované podgrafy, což potřebujeme pro perfektnost.

Definice: GG je hamiltonovský, pokud má kružnici na nn vrcholech (jako podgraf).

Věta (Bondyho-Chvátalova): Nechť GG je graf na n≥3n \ge 3 vrcholech. Nechť x,yx,y jsou nesousedé t. ž. deg⁡G(x)+deg⁡G(y)≥n\deg_G(x) + \deg_G(y) \ge n. Nechť G+=(V,E∪{xy})G^+ = (V, E \cup \left\{xy\right\}). Pak GG je hamiltonovský   ⟺  \iff G+G^+ je hamiltonovský.

Důkaz: ⇒\Rightarrow jasné

⇐\Leftarrow nechť CC je hamiltonovská kružnice G+G^+ a x,yx,y vrcholy splňující podmínku.

Věta (Dirac): GG graf na n≥3n \ge 3 vrcholech s min. stupněm ≥n/2\ge n/2 je hamiltonovský.

Důkaz: Z Bondy-Chvátalovy věty doplníme na KnK_n, který je hamiltonovský.

9. přednáška

Tutteův polynom

Definice (multigraf) G=(V,E)G = (V, E) kde VV jsou vrcholy a EE multimnožina prvků z V∪(V2)V \cup \binom{V}{2}

Definice (most): hrana e∈Ee \in E je most, v multigrafu GG, pokud G−eG - e má více komponent než GG

Definice (hodnost/rank) EE je r(E):=∣V∣−k(G)r(E) := |V| - k(G)

Důkaz: Chceme dokázat, že FF neobsahuje cykly a že r(E)=r(F)r(E) = r(F). Víme, že k(G)=k(F)k(G) = k(F).

Postupné přidávání hran z FF (právě tohle zaručuje, že nemáme cykly):

Spojením dostáváme r(F)=∣F∣=∣V∣−k(F)=∣V∣−k(G)=r(E)r(F) = |F| = |V| - k(F) = |V| - k(G) = r(E).

Důkaz (alternativní): Pokud je rank ∣V∣−1|V| - 1, tak je graf souvislý a přesně to odpovídá počtu hran jeho kostry. Pokud má 22 komponenty souvislosti, tak bude mít ∣V∣−2|V| - 2 hran, protože jednu hranu z kostry odebereme a graf tím roztrhneme. Pro více komponent souvislosti opakujeme a tedy r(E)=∣V∣−k(G)r(E) = |V| - k(G)

Definice (nulita) EE je n(E):=∣E∣−r(E)n(E) := |E| - r(E)

Příklad: G=(V,E)G = (V, E)

změna r(E)r(E) n(E)n(E)
přidání hrany bez změny počtu komponent r(E)r(E) n(E)+1n(E) + 1
přidání hrany se změnou počtu komponent r(E)+1r(E) + 1 n(E)n(E)

Definice (Tutteův polynom) multigrafu G=(V,E)G = (V, E) je polynom proměnných x,yx, y definovaný jako TG(x,y):=∑F⊆E(x−1)r(E)−r(F)⋅(y−1)n(F)T_G(x, y) := \sum_{F \subseteq E} (x - 1)^{r(E) - r(F)} \cdot (y - 1)^{n(F)}

Tvrzení: pro GG souvislý je TG(1,1)T_G(1, 1) počet koster GG

Důkaz: Dosadím do polynomu a získám 0r(E)−r(F)0n(F)0^{r(E) - r(F)} 0^{n(F)}. Vím, že x0≡1x^0 \equiv 1, tedy výraz bude počet FF takových, že r(E)=r(F)r(E) = r(F) a n(F)=0n(F) = 0.

Tvrzení: Nechť G1=(V1,E1),G2=(V2,G2)G_1 = (V_1, E_1), G_2 = (V_2, G_2) jsou multigrafy, t. ž. ∣V1∩V2∣≤1|V_1 \cap V_2| \le 1, ∣E1∩E2∣=0|E_1 \cap E_2| = 0 (protínají se nejvýše v jednom vrcholu a v žádné hraně). Definujeme G=(V,E)G = (V, E), kde V=V1∪V2V = V_1 \cup V_2 a E=E1∪E2E = E_1 \cup E_2. Potom TG(x,y)=TG1(x,y)⋅TG2(x,y)T_G(x, y) = T_{G_1}(x, y) \cdot T_{G_2}(x, y)

Důkaz: V definici kvantifikuji přes podmnožiny hran. Ty ale můžu vždy rozdělit na disjunktní sjednocení podle E1E_1 a E2E_2. Navíc:

Pak rozepíšu: TG(x,y)=∑F⊆E(x−1)r(E)−r(F)(y−1)n(F)=∑F1⊆E1∑F2⊆E2(x−1)r(E1∪E2)−r(F1∪F2)(y−1)n(F1∪F2)=∑F1⊆E1∑F2⊆E2(x−1)r(E1)−r(F1)+r(E2)−r(F2)(y−1)n(F1)+n(F2)=∑F1⊆E1∑F2⊆E2(x−1)r(E1)−r(F1)(x−1)r(E2)−r(F2)(y−1)n(F1)(y−1)n(F2)=∑F1⊆E1(x−1)r(E1)−r(F1)(y−1)n(F1)(∑F2⊆E2(x−1)r(E2)−r(F2)(y−1)n(F2))=TG1(x,y)⋅TG2(x,y) \begin{aligned} T_G(x, y) &= \sum_{F \subseteq E} (x - 1)^{r(E) - r(F)} (y - 1)^{n(F)} \\ &= \sum_{F_1 \subseteq E_1} \sum_{F_2 \subseteq E_2} (x - 1)^{r(E_1 \cup E_2) - r(F_1 \cup F_2)} (y - 1)^{n(F_1 \cup F_2)} \\ &= \sum_{F_1 \subseteq E_1} \sum_{F_2 \subseteq E_2} (x - 1)^{r(E_1) - r(F_1) + r(E_2) - r(F_2)} (y - 1)^{n(F_1) +n(F_2) } \\ &= \sum_{F_1 \subseteq E_1} \sum_{F_2 \subseteq E_2} (x - 1)^{r(E_1) - r(F_1)} (x - 1)^{r(E_2) - r(F_2)} (y - 1)^{n(F_1)} (y - 1)^{n(F_2)} \\ &= \sum_{F_1 \subseteq E_1} (x - 1)^{r(E_1) - r(F_1)}(y - 1)^{n(F_1)} \left(\sum_{F_2 \subseteq E_2} (x - 1)^{r(E_2) - r(F_2)} (y - 1)^{n(F_2)}\right) \\ &= T_{G_1}(x, y) \cdot T_{G_2}(x, y) \\ \end{aligned}

Důsledek: dva grafy se stejným Tutteovým polynomem nemusí být stejné.

Věta: Nechť G=(V,E)G = (V, E) je multigraf. Potom TG(x,y)T_G(x, y) je jednoznačně určen rekurencemi:

E=∅E = \emptyset TG(x,y)=1T_G(x, y) = 1
most ee TG(x,y)=x⋅TG−e(x,y)=x⋅TG∖e(x,y)T_G(x, y) = x \cdot T_{G - e}(x, y)= x \cdot T_{G \setminus e}(x, y)
  poslední rovnost: z důsledku výše
smyčka ee TG(x,y)=y⋅TG−e(x,y)=y⋅TG∖e(x,y)T_G(x, y) = y \cdot T_{G - e}(x, y) = y \cdot T_{G \setminus e}(x, y)
  poslední rovnost: odstranění smyčky je to stejné jako její kontrakce
jindy TG(x,y)=TG−e(x,y)+TG∖e(x,y)T_G(x, y) = T_{G - e}(x, y) + T_{G \setminus e}(x, y)

Důkaz: Pro E=∅E = \emptyset jasné, jinak rozdělíme:

TG(x,y)=∑F⊆E,e∉F(x−1)r(E)−r(F)⋅(y−1)n(F)⏟s1+∑F⊆E,e∈F(x−1)r(E)−r(F)⋅(y−1)n(F)⏟s2T_G(x, y) = \underbrace{\sum_{F \subseteq E, e \not\in F} (x - 1)^{r(E) - r(F)} \cdot (y - 1)^{n(F)}}_{s_1} + \underbrace{\sum_{F \subseteq E, e \in F} (x - 1)^{r(E) - r(F)} \cdot (y - 1)^{n(F)}}_{s_2}

Stačí dokázat následující (a dosazení do výrazu výše):

  1. pokud ee není most, tak s1=TG−e(x,y)s_1 = T_{G - e}(x, y)
    • ee není most, jeho odebráním se rank nezmění, tedy r(E)=r(E∖{x})r(E) = r(E \setminus \left\{x\right\})
  2. pokud ee je most, tak s1=(x−1)⋅TG−e(x,y)s_1 = (x - 1) \cdot T_{G - e}(x, y)
    • ee je most, jeho odebráním se rank zmenší o 11, tedy r(E)=r(E∖{x})+1r(E) = r(E \setminus \left\{x\right\}) + 1
  3. pokud ee není smyčka, tak s2=TG∖e(x,y)s_2 = T_{G \setminus e}(x, y)
    • ee není smyčka, kontrakce však zachová zbylé hrany (jsme v multigrafu) jako smyčky a nulita se tedy nezmění (jelikož, pokud to chápu správně, se spojením vlastně zmenší jak počet hran, tak vrcholů)
  4. pokud ee je smyčka, tak s2=(y−1)⋅TG∖e(x,y)s_2 = (y - 1) \cdot T_{G \setminus e}(x, y)
    • ee je smyčka, kontrakcí se nulita zmenší o 11, tedy

Poté pro větu stačí následující:

Definice (chromatický polynom) multigrafu G=(V,E)G = (V, E) je funkce chG(b):N0↦N0\mathrm{ch}_G(b): \mathbb{N}_0 \mapsto \mathbb{N}_0, kde pro b∈N0b \in \mathbb{N}_0 je chG(b):=\mathrm{ch}_G(b) := počet dobrých obarvení (posunutí udělá nové obarvení) GG pomocí barev {1,…,b}\left\{1, \ldots, b\right\}.

Věta: Pro každý multigraf G=(V,E)G = (V, E) platí chG(b)=(−1)∣V∣+k(G)⋅bk(G)⋅TG(1−b,0)\mathrm{ch}_G(b) = \left(-1\right)^{|V| + k(G)} \cdot b^{k(G)} \cdot T_G(1 - b, 0)

10. přednáška

Formální mocniné řady

Definice: Pro posloupnost reálných čísel a0,a1,…a_0, a_1, \ldots je formální mocninná řada (FMŘ) zápis tvaru a0+a1x1+a2x2+…=∑i=0∞aixia_0 + a_1x^1 + a_2x^2 + \ldots = \sum_{i = 0}^{\infty} a_i x^i

Fakt: R⟦x⟧\mathbb{R}\llbracket x \rrbracket tvoří (komutativní) okruh (máme +,⋅,0,1+, \cdot, 0, 1)

Fakt: R⟦x⟧\mathbb{R}\llbracket x \rrbracket tvoří vektorový postor (násobení konstantou je FMŘ pro a0=ca_0 = c)

Definice (převrácená hodnota): FMŘ A(x)A(x) je taková FMŘ, že A(x)⋅B(x)=1A(x) \cdot B(x) = 1

Tvrzení: Nechť A(x)=∑n=0∞anxnA(x) = \sum_{n = 0}^{\infty} a_n x^n je FMŘ. Potom 1A(x)\frac{1}{A(x)} existuje, právě když a0≠0a_0 \neq 0 (a pak je jednoznačně určena).

Důkaz: Hledejme inverz. Rozepsáním A(x)⋅B(x)=1+0x+0x2+…A(x) \cdot B(x) = 1 + 0x + 0x^2 + \ldots nám dává soustavu takovýchto rovnic, které mají jednoznačné řešení:

a0b0=1b0=1a0a0b1+a1b0=0b1=1a0(−a1b0)a0b2+a1b1+a2b0=0b2=1a0(−a1b1−a2b2)      ⋮ \begin{aligned} a_0 b_0 = 1 &\qquad b_0 = \frac{1}{a_0} \\ a_0 b_1 + a_1b_0 = 0 &\qquad b_1 = \frac{1}{a_0}(-a_1 b_0)\\ a_0 b_2 + a_1b_1 + a_2b_0 = 0 &\qquad b_2 = \frac{1}{a_0} (-a_1 b_1 - a_2b_2) \\ &\;\;\;\vdots \\ \end{aligned}

Definice (složení): A(x)=∑anxn,B(x)=∑bnxnA(x) = \sum a_nx^n, B(x) = \sum b_nx^n jsou FMŘ. Složení je A(B(x))=a0B(x)0+a1B(x)1+…A(B(x)) = a_0B(x)^0 + a_1B(x)^1 + \ldots. Obecně je problém to zadefinovat, potřeboval bych znát hodnotu součtu, ale jde to, když:

  1. A(x)A(x) je polynom (≡∃n0∈N\equiv \exists n_0 \in \mathbb{N} t. ž. ∀n≥n0:an=0\forall n \ge n_0: a_n = 0) a0B(x)0+a1B(x)1+a2B(x)2+…+an0B(x)n0+…⏟=0a_0 B(x)^0 + a_1B(x)^1 + a_2B(x)^2 + \ldots + \underbrace{a_{n_0}B(x)^{n_0} + \ldots}_{= 0}
  2. b0=0b_0 = 0
    • chci ukázat, že součet [xn]A(B(x))=[xn]a0B(x)0+[xn]a1B(x)1+…\left[x^n\right]A(B(x)) = \left[x^n\right]a_0B(x)^0 + \left[x^n\right]a_1B(x)^1 + \ldots je konečný
      • [x0]B(x)=b0=0\left[x^0\right]B(x) = b_0 = 0
      • B(x)=xB~(x)B(x) = x \tilde{B}(x) pro B~(x)\tilde{B}(x) FMŘ
      • B(x)k=xkB~(x)kB(x)^k = x^k \tilde{B}(x)^k, koeficient u xk−1,xk−2,…,x0x^{k - 1}, x^{k - 2}, \ldots, x^0 je nulový, tedy všechny koeficienty [xk]A(B(x))\left[x^k\right] A(B(x)) pro k>nk > n jsou nulové

Definice (derivace) FMŘ A(x)A(x) značená ddxA(x)=∑an+1(n+1)xn=a1+2a2x+3a3x3+…\frac{d}{dx}A(x) = \sum a_{n + 1}(n + 1)x^n = a_1 + 2a_2x + 3a_3x^3 + \ldots

Příklad: Můžu mít také FMŘ více proměnných, např. A(x,y)=∑n≥0,m≥0an,m⋅xn⋅ym∈R⟦x,y⟧A(x, y) = \sum_{n \ge 0, m \ge 0} a_{n, m} \cdot x^n \cdot y^m \in \mathbb{R}\llbracket x, y \rrbracket

Obyčejné vyvořující funkce

Definice (OVF): Nechť A\mathcal{A} je množina, jejíž každý prvek α∈A\alpha \in \mathcal{A} má definovanou velikost ∣α∣∈N0|\alpha| \in \mathbb{N}_0, předpokládáme že ∀n∈N0\forall n \in \mathbb{N}_0 je v A\mathcal{A} konečně mnoho prvků velikosti nn.

Potom obyčejná vytvořující funkce pro A\mathcal{A} je FMŘ OVF(A)=∑n≥0anxn\mathrm{OVF}(\mathcal{A}) = \sum_{n \ge 0} a_n x^n

Příklad: Jídla (J=P∪H\mathcal{J} = \mathcal{P} \cup \mathcal{H}):

11. přednáška

Exponenciální vytvořující funkce

Chci dojít k L(x)L(x), což bude vytvořující funkce pro počet lesů na nn vrcholech, pomocí S(x)S(x) vytvořující funkce pro počet stromů na nn vrcholech.

Nechť sns_n je počet stromů na vrcholech {1,…,n}\left\{1, \ldots, n\right\} S(x)=∑n≥0sn⋅xnn!∈R⟦x⟧S(x) = \sum_{n \ge 0} s_n \cdot \frac{x^n}{n!} \qquad \in \mathbb{R}\llbracket x \rrbracket

Nechť knk_n je počet kružnic na vrcholech {1,…,n}\left\{1, \ldots, n\right\} K(x)=∑n≥0kn⋅xnn!K(x) = \sum_{n \ge 0} k_n \cdot \frac{x^n}{n!}

Definujeme A(x)=S(x)⋅K(x)A(x) = S(x) \cdot K(x) a a0,a1,…a_0, a_1, \ldots tak, aby A(x)=∑n≥0an⋅xnn!A(x) = \sum_{n \ge 0} a_n \cdot \frac{x^n}{n!}

Potom platí, že an=∑j=0n(nj)⋅sj⋅kn−ja_n = \sum_{j = 0}^{n} \binom{n}{j} \cdot s_j \cdot k_{n - j}, tedy an=a_n = počet grafů na nn vrcholech mající dvě komponenty souvislosti, z nichž jedna je strom a druhá kružnice: [xn](S(x)⋅K(x))=∑j=0n([xj]S(x))⋅([xn−j]K(x))=∑j=0nsjj!⋅kn−j(n−j)!=∑j=0nn!j!(n−j)!⋅1n!⋅sjkn−j=1n!∑j=0n(nj)sjkn−j=[xn]A(x) \begin{aligned} \left[x^n\right]\left(S(x) \cdot K(x)\right) &= \sum_{j = 0}^{n} \left(\left[x^j\right] S(x)\right) \cdot \left(\left[x^{n - j}\right] K(x)\right) \\ &= \sum_{j = 0}^{n} \frac{s_j}{j!} \cdot \frac{k_{n - j}}{(n - j)!} \\ &= \sum_{j = 0}^{n} \frac{n!}{j!(n - j)!} \cdot \frac{1}{n!} \cdot s_j k_{n - j} \\ &= \frac{1}{n!}\sum_{j = 0}^{n} \binom{n}{j} s_j k_{n - j} \\ &= \left[x^n\right] A(x) \end{aligned}

Definujeme B(x)=S(x)2B(x) = S(x)^2 a b0,b1,…b_0, b_1, \ldots tak, aby B(x)=∑n≥0bn⋅xnn!B(x) = \sum_{n \ge 0} b_n \cdot \frac{x^n}{n!}

Dále definujeme hromadu dalších věcí:

Konečně vyjádříme L(x)=1+S(x)+S2(x)2!+…=∑n≥0Sn(x)n!=exp(S(x))=eS(x)L(x) = 1 + S(x) + \frac{S^2(x)}{2!} + \ldots = \sum_{n \ge 0} \frac{S^n(x)}{n!} = \mathrm{exp}(S(x)) = e^{S(x)}

V následujících definicích a pozorováních je takovýhle text odkaz na to, co si pod tím představovat v rámci minulého příkladu.

Definice (EVF): Mějme množinu A\mathcal{A} (všechny konečné stromy s očíslovanými vrcholy), předpokládejme:

  1. každý prvek α∈A\alpha \in \mathcal{A} (nějaký strom) má množinu vrcholů (vrcholů) V(α)⊆N,V(α)V(\alpha) \subseteq \mathbb{N}, V(\alpha) konečná
  2. pro každou konečnou V⊆NV \subseteq \mathbb{N} existuje konečně mnoho α∈A\alpha \in \mathcal{A} t. ž. V(α)=VV(\alpha) = V
    • (existuje konečné množství stromů)
  3. pro dvě konečné množiny V,W⊆NV, W \subseteq \mathbb{N} t. ž. ∣V∣=∣W∣|V| = |W| platí, že počet α∈A\alpha \in \mathcal{A} t. ž. V(α)=VV(\alpha) = V je stejný jako α∈A\alpha \in \mathcal{A} t. ž. V(α)=WV(\alpha) = W (co do počtu, záleží jen na velikosti množiny vrcholů)
    • (dvě stejně velké množiny vrcholů mají stejný počet stromů)

Potom exponenciální vytvořující funkce pro A\mathcal{A} je EVF(A)=∑n≥0anxnn!\mathrm{EVF(\mathcal{A})} = \sum_{n \ge 0} a_n \frac{x^n}{n!}kde an=# α∈A t. zˇ. V(α)={1,…,n}a_n = \#\ \alpha \in \mathcal{A} \text{ t. ž. } V(\alpha) = \left\{1, \ldots, n\right\}

(👀): Nechť A(x)A(x) je EVF(A),B(x)=EVF(B)\mathrm{EVF(\mathcal{A})}, B(x) = \mathrm{EVF}(\mathcal{B}), potom:

  1. pokud A,B\mathcal{A}, \mathcal{B} jsou disjunktní (příklad výše), pak A(x)+B(x)A(x) + B(x) je EVF(A∪B)\mathrm{EVF}(\mathcal{A} \cup \mathcal{B})
    • stejné jako u OFV\mathrm{OFV}, protože [xn](A(x)+B(x))=ann!+bnn!=an+bnn!\left[x^n\right] \left(A(x) + B(x)\right) = \frac{a_n}{n!} + \frac{b_n}{n!} = \frac{a_n + b_n}{n!}
  2. A(x)⋅B(x)=∑cnxnn!A(x) \cdot B(x) = \sum c_n \frac{x^n}{n!}, kde cnc_n je počet uspořádaných dvojic (α,β)\left(\alpha, \beta\right) t.ž. α∈A,β∈B,V(α)∪V(β)={1,…,n}\alpha \in \mathcal{A}, \beta \in \mathcal{B}, V(\alpha) \cup V(\beta) = \left\{1, \ldots, n\right\} (tvoří rozklad)
  3. Ak(x)=∑dnxnn!A^k(x) = \sum d_n \frac{x^n}{n!}, kde dnd_n je počet uspořádaných kk-tic (α1,…,αk)(\alpha_1, \ldots, \alpha_k), kde α1,…,αk∈A t.zˇ. V(α1)∪…∪V(αk)={1,…,n}⋆\alpha_1, \ldots, \alpha_k \in \mathcal{A} \text{ t.ž. } V(\alpha_1) \cup \ldots \cup V(\alpha_k) = \left\{1, \ldots, n\right\} \qquad \star
  4. pokud V(α)≠∅,∀α∈AV(\alpha) \neq \emptyset, \forall \alpha \in \mathcal{A}, pak Ak(x)k!=∑enxnn!\frac{A^k(x)}{k!} = \sum e_n \frac{x^n}{n!}kde ene_n je počet kk-prvkových množin splňujících ⋆\star
  5. pokud ∀α∈A:V(α)≠∅\forall \alpha \in \mathcal{A}: V(\alpha) \neq \emptyset, pak exp(A(x))=eA(x)=1+A(x)+A2(x)2+…=∑n≥0fnxnn!\mathrm{exp}(\mathcal{A}(x)) = e^{A(x)} = 1 + A(x) + \frac{A^2(x)}{2} + \ldots = \sum_{n \ge 0} f_n \frac{x^n}{n!} kde fnf_n je počet množin {α1,…,αk}⊆A\left\{\alpha_1, \ldots, \alpha_k\right\} \subseteq \mathcal{A}, kde V(α1)∪…∪V(αk)={1,…,n}V(\alpha_1) \cup \ldots \cup V(\alpha_{k}) = \left\{1, \ldots, n\right\}

Groupy a Burnside

Definice (akce grupy): nechť AA je množina, nechť Γ\Gamma je grupa, 1Γ1_\Gamma její neutrální prvek. Potom akce grupy Γ\Gamma na množině AA je binární operace ⋅:Γ×A↦A\cdot: \Gamma \times A \mapsto A t.ž.

  1. ∀x∈A:1Γ⋅x=x\forall x \in A: 1_\Gamma \cdot x = x
  2. ∀γ,δ∈Γ,∀x∈A:γ⋅(δ⋅x)=(γδ)⋅x\forall \gamma, \delta \in \Gamma, \forall x \in A: \gamma \cdot (\delta \cdot x) = (\gamma \delta) \cdot x
    • pozor, ⋅\cdot a γδ\gamma\delta jsou jiné operace

(👀): Pokud γ∈Γ,γ−1\gamma \in \Gamma, \gamma^{-1} je inverzní prvek k γ\gamma, potom ∀x,y∈A:γ⋅x=y  ⟺  γ−1⋅y=x\forall x, y \in A: \gamma \cdot x = y \iff \gamma^{-1} \cdot y = x

Důsledek: ∀p∈Γ:\forall p \in \Gamma: zobrazení x↦p⋅xx \mapsto p \cdot x je bijekce A⟷AA \longleftrightarrow A

12. přednáška

Definice (množina pevných bodů) γ∈Γ\gamma \in \Gamma, značená Fix(γ)={x∈A∣γx=x}\mathrm{Fix}(\gamma) = \left\{x \in A \mid \gamma x = x\right\}

Definice (stabilizátor) prvku x∈Ax \in A je Stab(x)={γ∈Γ∣γx=x}\mathrm{Stab}(x) = \left\{\gamma \in \Gamma \mid \gamma x = x\right\}

(👀): γ∈Γ,x∈A:γ∈Stab(x)  ⟺  x∈Fix(γ)  ⟺  γx=x\gamma \in \Gamma, x \in A: \gamma \in \mathrm{Stab}(x) \iff x \in \mathrm{Fix}(\gamma) \iff \gamma x = x

(👀): Stab(x)\mathrm{Stab}(x) je podgrupa Γ\Gamma

Prvky x,y∈Ax, y \in A jsou ekvivalentní (značím x∼Γyx \sim_{\Gamma} y), pokud ∃γ∈Γ\exists \gamma \in \Gamma t.ž. γx=y\gamma x = y

Definice (orbita) obsahující prvek x∈Ax \in A je množina [x]Γ={y∈A∣x∼Γy}={γx∣γ∈Γ}\left[x\right]_{\Gamma} = \left\{y \in A \mid x \sim_\Gamma y\right\} = \left\{\gamma x \mid \gamma \in \Gamma\right\} možinu orbit značíme A/ΓA / \Gamma.

Příklad: Koláčky (mák, tvaroh, povidla).

K={abcd∣a,b,c,d∈{T,M,P}}∣K∣=34=81\mathcal{K} = \left\{\boxed{a{b\atop c} d} \mid a, b, c, d \in \left\{T, M, P\right\}\right\} \qquad |\mathcal{K}| = 3^4 = 81

Γ={otocˇenıˊ o naˊsobky 90° mod 360°}={0°,90°,180°,270°}\Gamma = \left\{\text{otočení o násobky 90$\degree$ mod 360$\degree$}\right\} = \left\{0\degree, 90\degree, 180\degree, 270\degree \right\}

Lemma (o orbitě stabilizátoru): Nechť Γ\Gamma je konečná grupa s akcí na množině AA. Potom ∀x∈A:∣Stab(x)∣⋅∣[x]∣=∣Γ∣\forall x \in A: |\mathrm{Stab(x)}| \cdot |\left[x\right]| = |\Gamma|

Důkaz: Nechť množina Map(x,y)\mathrm{Map}(x, y) je množina akcí aa, pro které a⋅x=ya \cdot x = y. Pro akce σ∈Map(x,y)\sigma \in \mathrm{Map}(x, y) pomocí σaσ−1\sigma a \sigma^{-1} lze definovat bijekci mezi Map(x,x)\mathrm{Map}(x, x). Poté ∀x∈A,∣Γ∣=∑y∈[x]∣Map(x,y)∣=∑y∈[x]∣Stab(x)∣=∣[x]∣∣Stab(x)∣\forall x \in A, |\Gamma| = \sum_{y \in [x]} |\mathrm{Map}(x, y)| = \sum_{y \in [x]} |\mathrm{Stab}(x)| = |[x]| |\mathrm{Stab}(x)|

Věta (Burnsideovo lemma): Nechť Γ\Gamma je konečná grupa s akcí na AA

  1. (jednoduchá) pokud AA je konečná, pak ∣A/Γ∣=1∣Γ∣∑γ∈Γ∣Fix(γ)∣|A / \Gamma| = \frac{1}{|\Gamma|} \sum_{\gamma \in \Gamma} |\mathrm{Fix}(\gamma)| == počet orbit je roven „průměrnému počtu pervných bodů“
  2. Nechť každá orbita o∈A/Γo \in A / \Gamma má přiřazenou váhu w(o)w(o). Potom ∑o∈A/Γw(o)=1∣Γ∣∑γ∈Γ∑x∈Fix(γ)w([x])\sum_{o \in A/\Gamma} w(o) = \frac{1}{|\Gamma|} \sum_{\gamma \in \Gamma} \sum_{x \in \mathrm{Fix}(\gamma)} w([x])

Důkaz: (2)⇒(1)(2) \Rightarrow (1), když jsou váhy 11.

(2)(2) – dvojím počítáním s:=∑(γ,x)∈Γ×A,γx=xw([x])s := \sum_{\left(\gamma, x\right) \in \Gamma \times A, \gamma x = x} w([x])

s=∑γ∈Γ∑x∈Fix(γ)w([x])z definices = \sum_{\gamma \in \Gamma} \sum_{x \in \mathrm{Fix}(\gamma)} w([x]) \qquad \text{z definice}

s=∑x∈A∑γ∈Stab(x)w([x])pocˇıˊtaˊnıˊ obraˊceneˇ, prˇes Stab=∑o∈A/Γ∑x∈o∑γ∈Stab(x)w(o)w([x]) zaˊvisıˊ pouze na vaˊze orbity=∑o∈A/Γ∑x∈o∣Stab(x)∣w(o)vnitrˇnıˊ suma zaˊvisıˊ na Stab(x)=∑o∈A/Γ∑x∈o∣Γ∣∣o∣w(o)lemma o orbiteˇ a stabilizaˊtoru=∑o∈A/Γ∣o∣∣Γ∣∣o∣w(o)obsah sumy zaˊvisıˊ na velikosti orbity=∣Γ∣∑o∈A/Γw(o) \begin{aligned} s &= \sum_{x \in A} \sum_{\gamma \in \mathrm{Stab}(x)} w([x]) \qquad \text{počítání obráceně, přes $\mathrm{Stab}$} \\ &= \sum_{o \in A / \Gamma} \sum_{x \in o} \sum_{\gamma \in \mathrm{Stab}(x)} w(o) \qquad w([x])\text{ závisí pouze na váze orbity}\\ &= \sum_{o \in A / \Gamma} \sum_{x \in o} |\mathrm{Stab}(x)| w(o) \qquad \text{vnitřní suma závisí na $\mathrm{Stab}(x)$} \\ &= \sum_{o \in A / \Gamma} \sum_{x \in o} \frac{|\Gamma|}{|o|} w(o) \qquad \text{lemma o orbitě a stabilizátoru} \\ &= \sum_{o \in A / \Gamma} |o| \frac{|\Gamma|}{|o|} w(o) \qquad \text{obsah sumy závisí na velikosti orbity} \\ &= |\Gamma| \sum_{o \in A / \Gamma} w(o) \\ \end{aligned}

Poté první a druhý způsob dám do rovnosti, vydělím velikostí grupy a hotovo.

Příklad: Koláčky na steroidech: množina koláčků R\mathcal{R}, v každé části nezáporný počet rozinek, akce jsou stejné.

Pro k∈N0,ak=k \in \mathbb{N}_0, a_k = počet orbit, jejichž koláčky mají celkem kk rozinek. Cíl je získat vzorec pro A(x)=∑n≥0anxnA(x) = \sum_{n \ge 0} a_n x^n

Použijeme obecnější Burnsideovo lemma. Chceme, aby A(x)=∑o∈A/Γw(o)=1∣Γ∣∑γ∈Γ∑x∈Fix(γ)w([x])A(x) = \sum_{o \in A/\Gamma} w(o) = \frac{1}{|\Gamma|} \sum_{\gamma \in \Gamma} \sum_{x \in \mathrm{Fix}(\gamma)} w([x])

Váhu orbity s kk rozinkami nastavíme na xkx^k. Pro q∈Rq \in \mathcal{R} označím r(q)r(q) počet rozinek v qq, w([q])=xr(q)w([q]) = x^{r(q)}.

γ\gamma 1Γ1_\Gamma 90°90\degree, 270°270\degree 180°180\degree
Fix(γ)\mathrm{Fix}(\gamma) R\mathcal{R} všude je stejný počet rozinek protější strany mají stejný počet rozinek
∑q∈Fix(γ)w([q])\sum_{q \in \mathrm{Fix}(\gamma)} w([q]) (11−x)4\left(\frac{1}{1 - x}\right)^4 11−x4\frac{1}{1 - x^4} (11−x2)2\left(\frac{1}{1 - x^2}\right)^2

Vytvořující funkce z tabulky jsme odvodili následně:

∑q∈Fix(γ)=R=∑q∈Rxr(q)=∑(a,b,c,d)∈N04xa+b+c+d=(∑a∈N0xa)4=(11−x)4\sum_{q \in \mathrm{Fix}(\gamma) = \mathcal{R}} = \sum_{q \in \mathcal{R}} x^{r(q)} = \sum_{(a, b, c, d) \in \mathbb{N}_0^4} x^{a + b + c + d} = \left(\sum_{a \in \mathbb{N}_0} x^a\right)^4 = \left(\frac{1}{1 - x}\right)^4 ∑q∈Fix(γ)={(a,a,a,a)∣a∈N0}=∑a∈N0x4a=11−x4\sum_{q \in \mathrm{Fix}(\gamma) = \left\{(a, a, a, a) \mid a \in \mathbb{N}_0\right\}} = \sum_{a \in \mathbb{N}_0} x^{4a} = \frac{1}{1 - x^4} ∑q∈Fix(γ)={(a,b,a,b)∣a,b∈N0}=(∑a∈N0x2a)(∑b∈N0x2b)=(11−x2)2\sum_{q \in \mathrm{Fix}(\gamma) = \left\{(a, b, a, b) \mid a, b \in \mathbb{N}_0\right\}} = \left(\sum_{a \in \mathbb{N}_0} x^{2a}\right) \left(\sum_{b \in \mathbb{N}_0} x^{2b}\right) = \left(\frac{1}{1 - x^2}\right)^2

Tedy dostáváme, že A(x)=14((11−x)4+2(11−x4)+(11−x2)2)A(x) = \frac{1}{4} \left(\left(\frac{1}{1 - x}\right)^4 + 2 \left(\frac{1}{1-x^4}\right) + \left(\frac{1}{1 - x^2}\right)^2\right)

13. přednáška

Extremální teorie

Definice: pro graf HH označím ex(n,H)\mathrm{ex}(n, H) největší mm t.ž. existuje graf GG s nn vrcholy, mm hranami a neobsahující HH jako podgraf.

Definice: k,n∈Nk, n \in \mathbb{N}, označme Tk(n)T_k(n) úplný kk-partitní graf na nn vrcholech, jehož všechny partity mají velikost ⌊nk⌋\left\lfloor \frac{n}{k} \right\rfloor nebo ⌈nk⌉\left\lceil \frac{n}{k} \right\rceil. Nechť tk(n)=∣E(Tk(n))∣t_k(n) = |E(T_k(n))|

(👀): ∀r∈N,r≥2:ex(n,Kr)≥tr−1(n)\forall r \in \mathbb{N}, r \ge 2: \mathrm{ex}(n, K_r) \ge t_{r - 1}(n), protože Tr−1(n)T_{r - 1}(n) neobsahuje KrK_r (z každé partity si klika vezme ≤1\le 1 vrchol, tedy nejvýše r−1r - 1)

Lemma (1): Každý kk-partitní graf na nn vrcholech má nanejvýš tk(n)t_{k}(n) hran.

Důkaz: Nechť G=(V,E)G = (V, E) je kk-partitní, P1,…,PkP_1, \ldots, P_k jsou jeho partity. Navíc ∣P1∣≤∣P2∣≤…≤∣Pk∣|P_1| \le |P_2| \le \ldots \le |P_k|

Lemma (2): Nechť G=(V,E)G = (V, E) je graf neobsahující KrK_r jako podgraf. Potom ∃H=(V,EH)\exists H = (V, E_H) (r−1)(r-1)-partitní t.ž. deg⁡G(x)≤deg⁡H(x)\deg_G(x) \le \deg_H(x) (a tudíž ∣E(G)∣≤∣E(H)∣|E(G)| \le |E(H)|)

Důkaz: indukcí podle rr

Nechť x∈V(G)x \in V(G) je vrchol max. stupně v GG

Ověříme ∀x∈V:deg⁡G(x)≤deg⁡H(x)\forall x \in V: \deg_G(x) \le \deg_H(x)

  1. y∈V∖S:deg⁡H(y)=∣S∣=deg⁡H(x)=deg⁡G(x)≥deg⁡G(y)y \in V \setminus S: \deg_H(y) = |S| = \deg_H(x) = \deg_G(x) \ge \deg_G(y) (xx je vrchol s největším stupněm)
  2. y∈S:deg⁡H(y)=deg⁡HS(y)+∣V∖S∣≥IPdeg⁡GS(y)+∣V∖S∣≥deg⁡G(y)y \in S: \deg_H(y) = \deg_{H_S}(y) + |V \setminus S| \overset{\mathrm{IP}}{\ge} \deg_{G_S}(y) + |V \setminus S| \ge \deg_G(y)
    • rozdělili jsme to na dva případy podle toho, co vidí uvnitř a co vně SS
    • poslední nerovnost plyne z toho, že yy v GG vidí sousedy v GSG_S + nanejvýš všechny z V∖SV \setminus S

Věta (Turán, 1941): ∀r≥2:ex(n,Kr)=tr−1(n)\forall r \ge 2: \mathrm{ex}(n, K_r) = t_{r - 1}(n)

Důkaz: Vezmu GG nějaký graf bez KrK_r.

Spojení odhadů dává rovnost.

Poznámka: tk(n)=k−1k(n2)+O(n)=k−12kn2+O(n)t_k(n) = \frac{k-1}{k} \binom{n}{2} + \mathcal{O}(n) = \frac{k - 1}{2k} n^2 + \mathcal{O}(n)

Pro minory

Definice: pro graf H:ex⪯(n,H)H: \mathrm{ex}_\preceq(n, H) je maximalní počet hran grafu GG na nn vrcholech bez HH jako minoru.

(👀): ex(n,H)≥ex⪯(n,H)\mathrm{ex}(n, H) \ge \mathrm{ex}_\preceq(n, H), protože graf bez HH-minoru nemá ani HH-podgraf

(👀): ex⪯(n,K3)=n−1\mathrm{ex}_\preceq(n, K_3) = n - 1 (dostávám stromy!)

Věta: ∀r≥3∃cr>0:∀n:ex⪯(n,Kr)<cr⋅n\forall r \ge 3 \exists c_r > 0: \forall n: \mathrm{ex}_\preceq(n, K_r) < c_r \cdot n

Důkaz: dokážeme pro cr=2r−3c_r = 2^{r - 3}, indukcí dle rr

Pomocné tvrzení: ∀{x,y}=e∈E\forall \left\{x, y\right\} = e \in E platí ∣N(x)∩N(y)∣≥cr|N(x) \cap N(y)| \ge c_r

Důkaz: Vezmu G′=G.eG' = G.e

Odečtem nerovností máme ∣E∣−∣E′∣>cr|E| - |E'| > c_r. Navíc ∣E∣−∣E′∣=1+∣N(x)∩N(y)∣|E| - |E'| = 1 + |N(x) \cap N(y)| (zanikají hrany do společných sousedů a navíc hrana ee), dosazením dostáváme hledanou nerovnost.

K důkazu původního vyberu x∈V(G)x \in V(G), S=NG(x),GS=G[S]S = N_G(x), G_S = G\left[S\right].

Poznámka: odhad byl dost hrubý, věta platí dokonce pro cr=O(r⋅log⁡rc_r = \mathcal{O}(r \cdot \sqrt{\log r})

Pronikající systémy množin

Definice: kk-uniformní hypergraf je dvojice (V,E)(V, E), kde E⊆(Vk)E \subseteq \binom{V}{k}

(👀): rozebereme několik případů:

Věta (Erdös-Ko-Rado, 196*): ∀k,n∈N:n≥2k⇒f(k,n)=(n−1k−1)\forall k, n \in \mathbb{N}: n \ge 2k \Rightarrow f(k, n) = \binom{n - 1}{k - 1}

Důkaz: dokazujeme dva odhady:

Definice: cyklické pořadí {1,…,n}\left\{1, \ldots, n\right\} je nějaká 11-cyklová permutace {1,…,n}\left\{1, \ldots, n\right\}

(👀): intervalů daného pořadí CC je nn

(👀): cyklických pořadí je (n−1)!(n - 1)!

(👀): pokud e={a1,…,ak}e = \left\{a_1, \ldots, a_k\right\} je vůči CC interval, pak ∃≤k−1\exists \le k - 1 dalších hran e′e' t.ž. jsou intervaly vůči CC

Důkaz: Může nastat vždy právě jeden z následujících případů, protože z předpokladu je EE pronikající systém množin (a e′e' s e′′e'' by byly disjunktní):

Dvojic je tedy nejvýše r−1r - 1.

Důkaz věty bude dvojí počítání (e,C)(e, C) t.ž. e∈E,ce \in E, c cyklické pořadí a ee tvoří v CC interval.

  1. vezmu ee a chci tvořit cyklické pořadí t.ž. ee tvoří interval: ee zpermutuji k!k! způsoby a V∖eV \setminus e zpermutuji (n−k)!(n - k)! způsoby, pro každou hranu, tedy #(e,C)=∣E∣⋅k!⋅(n−k)!\# (e, C) = |E| \cdot k! \cdot (n - k)!
  2. vezmu CC: těch je (n−1)!(n - 1)!
    • podle pozorování je ee tvořících interval nanejvýš kk, tedy #(e,C)≤k⋅(n−1)!\# (e, C) \le k \cdot (n - 1)!

Spojením dostávám ∣E∣≤(n−1k−1)|E| \le \binom{n - 1}{k - 1}

Zdroje/materiály

Poděkování

  1. Chceme ukázat, že obsahuje-li graf K5K_5 nebo K3,3K_{3,3} jako minor, obsahuje i dělení nějakého z těchto grafů jako podgraf. Uvažme nejdřív obecně graf GG obsahující jak podgraf dělení H′H' grafu HH. H′H' dostaneme z GG posloupností mazání vrcholů a mazání hran. HH pak dostaneme z H′H' posloupností operací inverzních k dělení hran, což jsou právě kontrakce hran, při nichž má výsledný vrchol stejný stupeň, jako jeden z kontrahovaných vrcholů (a zároveň nekontrahujeme vrchol stupně 1, což je ale to samé jako mazání). Všimněme si, že tento speciální tvar má mimo jiné každá kontrakce, při níž nevznikne větší stupeň než 3. Co kdyby tedy GG obsahoval minor KK a navíc Δ(K)≤3\Delta(K) \leq 3? Od GG ke KK se můžeme dostat posloupností mazání vrcholů, mazání hran a kontrakcí hran. Všimněme si ale, že nikdy nemusíme použít kontrakci, při které vznikne větší stupeň než 3, protože vzniklý vrchol musí být stejně následně smazán. To můžeme nahlédnout i tak, že v posloupnosti operací se mohou operace libovolně předbíhat (pokud je přitom patřičně pozměníme), a tedy všechny kontrakce si můžeme nechat nakonec. Z předchozích pozorování vidíme, že minory maximálního stupně nejvýše 3 a dělení jako podgrafy jsou generované stejnými typy operací a tedy speciálně obsahuje-li graf K3,3K_{3,3} jako minor, obsahuje i nějaké jeho dělení jako podgraf. Zbytek důkazu pro K5K_5 je lepší s obrázkem a lze najít na tomhle odkazu (Lemma 4.4.2). ↩