Aplikace lineární algebry v kombinatorice, jaro 2013

Přednáška probíhá každé pondělí 10:40 v S4, cvičení po přednášce 12:20 tamtéž. Přednáší a cvičí prof. Jan Kratochvíl (honza@kam.mff.cuni.cz) a Tomáš Gavenčiak (gavento@ucw.cz).

Zápočet

Účast na cvičení není povinná. Zápočet je za aktivní účast na části cvičení (alespoň 2).

Obsah přednášky a cvičení

25. 2.Přednáška (JK)

Použití lineární nezávislosti: sudo-licho města (pojmenování měst je vždy průniky-velikosti). Nulo-nenulo města modulo prvočíslo a modulo $p_1 p_2$.

Skoro-disjunktní systémy podmnožin (velikost průniků právě 1, též Fisherova nerovnost).

Dvouvzdálenostní množiny bodů v $\mathbb{R}^n$, totéž na sféře $S_{n-1}$.

Cvičení (JK)

Nulo-nenulo města modulo $p_1p_2$ a další cvičení.

4. 3.Přednáška (JK)

Skalární součin, ortogonální doplněk a použití dimenze. Řešení sys. lin. rovností, $\dim \Ker(A) + \dim \Im(A) = n$, dimenze ortog. doplňku, $\dim M + \dim M^\perp \leq n$ (rovnost pokud pro každé $x\neq 0$ $\langle x, x\rangle\neq0$), sudo-sudo města.

Prostor $\Eul_G$ eulerovských podgrafů dimenze $m-n+1$, prostor řezů $\Cut_G$ dimenze $n-1$, $\Eul_G=\Cut_G^\perp$. Pro každý graf existuje $V=V_1\cupdot V_2$, že $G[V_1]$ i $G[V_2]$ jsou eulerovské.

Konstrukce pro kubický dolní odhad Ramseyova čísla.

Cvičení (TG)

(Ne)závisost soustavy 0,1-vektorů nad různými tělesy, $\GF(p)$ vs $\GF(p^k)$.

Přibližně 2-vzdálenostní množiny a kompaktnost.

Systém podmnožin s velikostmi průniků v $L$ má velikost $O(n^{|L|})$.

Systém elementárních kruznic nad danou kostrou je báze $\Eul_G$.

11. 3.Přednáška (TG)

Úvod do kódů v grafech, rozlišitelná slova, silný součin $G\boxtimes H$.

Shannonova kapacita grafu $\Theta(G)$, $\Theta(C_5)\geq\sqrt{5}$.

Ortonormální reprezentace grafu, Lovászova funkce $\vartheta(G)$, určení $\vartheta(C_5)$.

Tenzory a tenzorový součin, skalární součin tenzorů.

Věta $\Theta(G)\leq\vartheta(G)$ a důsledek $\Theta(C_5)=\sqrt{5}$.

Cvičení (TG)

Odhady Shannonovy kapacity různých $C_n$.

Vztah $\Theta(G)\leq\chi(\overline{G})$ a $\vartheta(G)\leq\chi(\overline{G})$.

Shannonova kapacita perfektních grafů.

$\langle a\otimes b, c\otimes d\rangle = \langle a, c\rangle\langle b, d\rangle$

18. 3.Přednáška (TG)

Funkcionální reprezentace $\mathcal{F}$ grafu $G$ a její dimenze, $\Theta(G)\leq\dim\mathcal{F}$.

Shannonova kapacita $G+H$ a existence $G$, že $\Theta(G+\overline{G})\gt\Theta(G)+\Theta(\overline{G})$

Ortonormální reprezentace malé dimenze jako spec. případ fun. repr.

Cvičení (TG)

Ortog. repr. $G$ v $\R^d$ v obecné poloze a lokálně obecné poloze

V: $G$ má o. r. v $\R^d$ v ob. pol. $\iff$ $G$ má o. r. v $\R^d$ v lok. ob. pol. $\iff$ $G$ je $(|G|-d)$-souvislý (snažší části důkazu).

Nechť $\dmin G = \min_{\mathcal{F} \mathrm{ortog. repr.} G}\dim\mathcal{F}$, pak $\dmin(G\boxtimes H)\leq\dmin G\dmin H$.

$\vartheta(G)\leq\dmin G$ (nedokončeno).

$\Theta(G+H)\geq\Theta(G)+\Theta(H)$ (nedokončeno).

25. 3.Přednáška (JK)

Vlastní čísla a vektory grafu, úvod a proč jsou reálná.

Moorovy grafy.

Cvičení (JK)

Vlastní čísla úplneho bipartitiního grafu $K_{a,b}$.

Vlastní čísla kruznice $C_n$.

1. 4.Velikonoční pondělí

8. 4.Přednáška odpadá

Cvičení (Vítek Jelínek)

$G$ nemá hrany právě když $G$ má všechna vl. čísla nulová.

Stopa matice $\tr(A)$ (součet diagonály) je součet vlastních čísel.

Vztah $\tr(A^k)$ a počtu uzavřených sledů délky $k$; $G$ má $\tr(A^3)/6$ trojúhelníků.

Spektrum $K_{1,n}$.

Spektrum hyperkrychle.

15. 4.Přednáška (JK)

Raileighův princip: pro matici $A$ s vl. čísly $\lambda_i$ a přísl. vektory $x_i$ platí:

$u^T A u \geq \lambda_k u^T u$ pro $u\in\langle x_1\dots x_k \rangle$,

$u^T A u \leq \lambda_k u^T u$ pro $u\in\langle x_k\dots x_n \rangle$.

V obou případech rovnost implikuje, že $u$ je vlastní vektor.

Proplétání vlastních čísel principiální podmatice (a tedy i podgrafu).

Cvičení (TG)

$\lambda_1 \leq \Delta(G)$.

$\lambda_1 \geq \bar{d}(G)$.

Spektrum $P_n$ (pomocí spektra $C_{2n+2}$)

22. 4.Přednáška (TG)

Opakování Raileigh principle.

Proplétání při násobení maticí: Buď $A$ čtvercová symetrická, $S$ taková, že $S^T S=I$, $B:=S^T A S$, pak vl. čísla $B$ proplétají vlastní čísla $A$. Pokud je někde proplétání těsné a $x$ je odpovídající vl. vektor $B$, je $Sx$ odpovídající vl. vektor $A$.

Kvocient matice: pro lib. rozdělení matice na bloky se čtvercovými bloky na diagonále nahradíme bloky jejich průměrem (vzniklá matice má jedno číslo za každý blok).

Pokud $B$ je kvocientem $A$, pak vl. čísla $B$ proplétají vl. čísla $A$.

Cvičení (TG)

Pro $d$-regulární grafy platí $\alpha(G)\leq n\frac{-\lambda_n}{\lambda_1-\lambda_n}$.

Toto ale neplatí pro obecne grafy (např. hvězdy).

Pro $d$-regulární grafy platí $\chi(G)\geq 1-\frac{\lambda_1}{\lambda_n}$ (důsledek z výše).

Toto platí stejně i pro obecné grafy (důkaz podobně jako při proplétání kvocientu).

$\chi(G)\leq \lambda_1 + 1$

29. 4.Přednáška (TG)

Náhodné procházky na grafu, matice přechodu $P_G=D_G^{-1}A_G$, změna distribuce $\rho$ po kroku procházky na $P_G\rho$.

$N_G=D_G^{-1/2}A_GD_G^{-1/2}$ je symetrická a podobná $P_G$, takže $P_G$ má reálna vl. čísla. Spec. případ pro regulární grafy.

Rozšíření na hranově vážené (multi)grafy se smyčkami. Situace pro orientované grafy.

Definice Markovova řetězce (MC), MC je reverzibilní právě když je odvozen z neorient. grafu.

Libovolná distribuce na vrcholech souvislého $G$ procházkou konverguje právě když $G$ není bipartitní. Stabilní distribuce $\pi$.

Rychlost konvergence ke stabilní distribuci z libovolné $\varrho$ je $|P_G^k\varrho - \pi|_1 \leq \sqrt{n}\max^k\{\lambda_2,-\lambda_n\}$.

Cvičení (TG)

Jak procházkou konverguje libovolná distribuce na vrcholech bipartitního grafu.

Jak vypadá vývoj distribuce na obecném MC a jaká je tam nutná podmínka konvergence.

Různé definice dobře mixované distribuce.

Jak rychle se mixuje distribuce na $C_n$.

6. 5.Dvojpřednáška (JK)

$t$-perfektní kódy, $q$ vel. abecedy, $n$ délka slova.

Lloydova věta (podmínky existence $t$-perfektního kódu).

...

13. 5.Přednáška (TG)

Vrcholová expanze $h_v(G)=\min_{S\subseteq V}|N(S)|/|S|$ a hranová expanze $h(G)=\min_{S\subseteq V}|E(S,\overline{S})|/|S|$ (vždy pro $|S|\leq n/2$ nebo $|S|\leq n/d$.

Dále většinou pro $d$-regulární grafy. Vztah $h_v(G)\leq h(G) \leq d h_v(G)$. Rodina $d$-regulárních expandérů.

Spektrální expanze $d-\lambda_2$ versus spectral gap $d-\lambda$, kde $\lambda=\max\{\lambda_2, -\lambda_n\}$. Rozdíly pro (skoro) bipartitní grafy.

$h(G)\geq (d-\lambda_2)/2$ s důkazem, $h(G)\leq\sqrt{d(d-\lambda_2)}$ bez důkazu.

Expander mixing lemma: $$\forall S,T\subseteq V, S\cap T=\emptyset: |e(S,T)-d|S||T|/n|\leq\lambda\sqrt{|S||T|}.$$

Konstrukce bez důkazů. Náhodné d-regulární grafy jsou skoro určitě dobré expandéry ($\lambda\leq 2\sqrt{d+1}+o(1)$). Iterace vzdálenostní mocniny grafu (zvyšuje expanzi) a zig-zag součinu (zmenšuje stupeň) pro zvýšení expanze a zachování řídkosti.

Aplikace bez důkazů. Zvyšování přesnosti náhodných algoritmů málo dalšími bity až k derandomizaci (nástin). Unoformní samplování objektů náhodnou procházkou na expandéru nad prostorem. Markov chain Monte Carlo metoda počítání kolik objektů z rodiny má hledanou vlastnost.

Půlpřednáška (JK)

$t$-perfektní kód v Hammingovské metrice - $t$-okolíčka kódu tvoří rozklad prostoru.

Pro $q=p^r$ existují t-perf. kóddy pouze pro $t=1$ (libovolné $q$), $t=2$ ($q=3, n=11$) a $t=3$ ($q=2, n=23$). Z toho důkazy: neexistence pro $t=2, q=2$.

...

20. 5.Přednáška ani cvičení není

3. 6.Náhradní přednáška zrušena

Zdroje

[BF] L. Babai, P. Frankl: Linear algebra methods in combinatorics - dobrý úvod do lin. alg. metody. Původní zdroj pro první část přednášky, mnoho různých příkladů.

[Juk] S. Jukna: Extremal Combinatorics: With Applications in Computer Science [online PDF] - Part III je dobře dostupná alternativa k [BF].

[Mat16] J. Matoušek: Šestnáct miniatur [online PS] a [Mat33] J. Matoušek: Thirty three miniatues [online PS] - velmi pěkně popsaná sudo/licho města, základ samoopravných kódů, pokrývání bip. podgrafy, Shannonova kapacita $C_5$, Shannonova kapacita sjednocení grafů.

[BH] A. E. Brouwer, W. H. Haemers: Spectra of graphs [online PDF] - úvod do vlastních čísel grafů, odvození vl. čísel a vektorů pro různé třídy grafů.

[Hae] W. H. Haemers: Interlacing Eigenvalues and Graphs [online PDF] - stručný úvod do proplétání vlastních čísel a jeho aplikace na $\alpha(G)$ a $\chi(G)$.

[Fox] J. Fox: Lecture notes MAT307, part 22: Eigenvalues and expanders [online PDF] - úvod do expanze a důkaz vztahu hranové a spektrální expanze.

[SS] T. Sauerwald, H. Sun: Spectral Graph Theory and Applications, Lecture 3: Expander Mixing Lemma [online PDF] - pěkný důkaz Expander mixing lemma.

[DH] C. Dwork, G. Helleloid: Lecture notes CS369E, Lecture 7: Expander Constructions [online PDF] - konstrukce expandérů, zig-zag součin a jeho vlastnosti.

Jaj