petrmanek / cs-notes Goto Github PK

r(k,l) = binom (k+l-2) choose (k-1)
viz http://mj.ucw.cz/papers/ramsey.pdf

• co jsem koukal, medvěd nám definoval ušaté lemma jako ekvivalenci mezi 3 tvrzeními - G je 2-souvislý, G lze postavit z kružnice pomocí uší a G lze postavit z K3 operacemi G+e a G%e. Důkaz 1=>2 tam máš, zbytek je triviální - jde spíš o to, jestli chceš být compatible
• větu 6.13 (2-souvislost implikuje více, než V koster), nám medvěd nedával
• Cayleho dokazoval přes PoVyKoSy - speciální orientované stromy, tak že ex u: deg_out(u) = 0 a pro vsechna v z V{u} je deg_out(v) = 1. Ukazal vztah mezi poctem stromu na n vrcholech a poctem techto stromu a pak tyhle stromy spocital
• chybi veta K(G) = K(G-e) + K(G%e) ((1))
• chybi laplaceova matice G (q_ii = deg(i), q_ij = -1 iff {i,j} in E), kirchoffova veta + dukaz (kappa = det(Q_11)) - dokazoval ji pro multigrafy, indukci podle hran, 1. krok - nesouvisly graf, matice bude singularni, 2. krok, vezmes grafy podle ((1)), ty maji mene hran a spojis to
• dale ukazoval pocet koster verije ( vejir = wheel bez jedne hrany, je tedy "nedokonceny" na okrajy) - pomoci ((1)) prijdes na to, ze plati rekurence V_n = V_n-1 + W_n-1 a W_n-1 = V_n-1 + W_n-2... z toho vytvorku a vyjde F_2n (Fib)
• Ramsey - ukazoval dolni odhad Ramseyova cisla, t.z. R(k,k) >= 2^(k/2) --- pravdepodobnosti metoda, vezmes graf s nahodnym obarvenim, P[je k-klika] = 2^-(k/2), to samy s druhou klikou, pak pouzijes P(A u B) <= P(A) + P(B) -> P[ex. co chceme] = (n choose k) * 2 * 2^-(k/2) a chces ukazat, kdy je to mensi nez jedna, vyjde prave n < 2^(k/2)

-- Dukaz T(n) = \lfloor n^2 / 4 \rfloor

1. Horní odhad - $T(n) \geq \left\lfloor \frac{n^2}{4} \right\rfloor$
   a) pro n sudé - použijeme $K_{\frac{n}{2}, \frac{n}{2}}$
   b) pro n liché $n = 2k+1$, použijeme $K_{k+1, k}$ - nahlédneme, že $|E| = k(k+1)$. Chceme $\left\lfloor \frac{n^2}{4} \right\rfloor = \left\lfloor \frac{4k^2 + 4k + 1}{4} \right\rfloor = k^2 + k = k(k+1)$
2. Dolní odhad - indukcí dle $n$, krok bude $n \rightarrow n+2$
   Mějme $G$ na $n+2$ vrcholech, chceme ukázat, že $|E| \leq \frac{(n+2)^2}{4}$ Vezměme libovolnou ${u,v} \in E$. Použijeme IP na graf $G'(V',E') = G(V \backslash {u,v}, E[V'])$. Víme, že $|V'| = n$, $|E'| \leq \frac{n^2}{4}$. Počet hran mezi vrcholem $u$ a zbytkem grafu si označím jako $N_u$, odbodně s $v$. Víme dále, že $|E| = |E'| + N_u + N_v + 1$. Stačí nahlédnout, že $N_u + N_v \leq n$. Sporem, kdyby nebylo, existuje vrchol $p$ takový, že ${p,u} \in E \land {p,v} \in E$. To by ale znamenalo, že máme trojúhelník, což je spor s předpokladem.

-- Dukaz T(n) = \lfloor n^2 / 4 \rfloor

1. Horní odhad - $T(n) \geq \left\lfloor \frac{n^2}{4} \right\rfloor$
   a) pro n sudé - použijeme $K_{\frac{n}{2}, \frac{n}{2}}$
   b) pro n liché $n = 2k+1$, použijeme $K_{k+1, k}$ - nahlédneme, že $|E| = k(k+1)$. Chceme $\left\lfloor \frac{n^2}{4} \right\rfloor = \left\lfloor \frac{4k^2 + 4k + 1}{4} \right\rfloor = k^2 + k = k(k+1)$
2. Dolní odhad - indukcí dle $n$, krok bude $n \rightarrow n+2$
   Mějme $G$ na $n+2$ vrcholech, chceme ukázat, že $|E| \leq \frac{(n+2)^2}{4}$ Vezměme libovolnou ${u,v} \in E$. Použijeme IP na graf $G'(V',E') = G(V \backslash {u,v}, E[V'])$. Víme, že $|V'| = n$, $|E'| \leq \frac{n^2}{4}$. Počet hran mezi vrcholem $u$ a zbytkem grafu si označím jako $N_u$, odbodně s $v$. Víme dále, že $|E| = |E'| + N_u + N_v + 1$. Stačí nahlédnout, že $N_u + N_v \leq n$. Sporem, kdyby nebylo, existuje vrchol $p$ takový, že ${p,u} \in E \land {p,v} \in E$. To by ale znamenalo, že máme trojúhelník, což je spor s předpokladem.

ještě nám ukazoval, že graf s maximálním počtem hran bez trojúhelníku je právě K_n/2,n/2 - důkaz = zamyslet se nad důkazem té rovnosti
poznamka k predchozi - T(n) oznacoval jako max pocet hran v grafu s n vrcholy bez K3
-- a tedy Důkaz $|E(G)| \leq \frac{1}{2} \left( n^\frac{3}{2} + n \right)
vezměme si množinu $M$, což je množina cest $P_2 \subset G$ mezi 3 vrcholy, označíme si je $(u, v, w)$.
Nahlédneme, že pro libovolnou dvojici ${u, w}$ existuje nejvýše jedno $v$, jinak bychom dostali $C_4$, tedy $|M| \leq \binom{n}{2}$.
Dále nahlédneme, že pro $v$ lze zvolit ${u, w}$ jako libovolné sousedy $v$, $|M| = \sum_{v \in V} \binom{\mathrm{deg}(v)}{2}$.
Pokud budou tedy $d_1, \dots, d_n$ stupně vrcholů, bude platit, že $\frac{\sum_{i=1}^n (d_i-1)^2}{2} \leq \sum_{i=1}^{n} \binom{d_i}{2} \leq \binom{n}{2}. Nás zajímá max. $|E| = \frac{1}{2} \sum_{i=1}^n d_i$. Využitím Cauchy-Schwarzovi nerovnosti víme, že
$$ \sum_{i=1}^n (d_i - 1) \leq \sqrt{\sum_{i=1}^n (d_i - 1)^2} \sqrt{\sum_{i=1}^n} \leq \sqrt{n^2} \sqrt{n} \leq n^{\frac{3}{2}}$$
$$|E| \leq \frac{1}{2} \left( n^{\frac{3}{2}} + n \right)$$
$n$ se vyskytuje protože počítáme s $d_i - 1$.

-- tenhle důkaz je ošklivý, tak si ho radši ještě projdi, Medvěd nám ho dával takhle. Ten už se mi narozdíl od předchozího nelíbí.

• chybi veta K(G) = K(G-e) + K(G%e) ((1))
• chybi laplaceova matice G (q_ii = deg(i), q_ij = -1 iff {i,j} in E), kirchoffova veta + dukaz (kappa = det(Q_11)) - dokazoval ji pro multigrafy, indukci podle hran, 1. krok - nesouvisly graf, matice bude singularni, 2. krok, vezmes grafy podle ((1)), ty maji mene hran a spojis to
• dale ukazoval pocet koster verije ( vejir = wheel bez jedne hrany, je tedy "nedokonceny" na okrajy) - pomoci ((1)) prijdes na to, ze plati rekurence V_n = V_n-1 + W_n-1 a W_n-1 = V_n-1 + W_n-2... z toho vytvorku a vyjde F_2n (Fib)

Ekvivalence:

• G je 2-souvislý
• G lze postavit z kružnice pomocí uší
• G lze postavit z K3 operacemi G+e a G%e

PoVyKoSy - speciální orientované stromy, tak že ex u: deg_out(u) = 0 a pro vsechna v z V{u} je deg_out(v) = 1. V dukazu MJ ukazal vztah mezi poctem stromu na n vrcholech a poctem techto stromu a pak tyhle stromy spocital

Ramsey - ukazoval dolni odhad Ramseyova cisla, t.z. R(k,k) >= 2^(k/2) --- pravdepodobnosti metoda, vezmes graf s nahodnym obarvenim, P[je k-klika] = 2^-(k/2), to samy s druhou klikou, pak pouzijes P(A u B) <= P(A) + P(B) -> P[ex. co chceme] = (n choose k) * 2 * 2^-(k/2) a chces ukazat, kdy je to mensi nez jedna, vyjde prave n < 2^(k/2)

V důkazu jsou použity opačné odhady, je třeba ho opravit.