Aplikace lineární algebry v kombinatorice, podzim 2014

Přednáší a cvičí prof. Jan Kratochvíl (honza@kam.mff.cuni.cz) a Tomáš Gavenčiak (gavento@ucw.cz). Přednáška probíhá každé úterý 12:20 v S1, cvičení navazuje 14:00 tamtéž.

Pro představu o průběhu přednášky viz LAK jaro 2013.

Zápočet

Účast na cvičení není povinná. Zápočet je za aktivní účast na části cvičení (alespoň dvou) a po dohodě se studenty i za spolupráci na přípravě skriptíček (viz níže, minimální podíl není nijak striktně zadán).

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

7. 10.Přednáška (TG)

Opakování pojmů z lineární algebry: tělesa, lineární kombinace, vektorové prostory, báze, generátor, dimenze, lineární zobrazení, matice jako pole čísel a jako zobrazení, prostory $\Im(A)$, $\Rs(A)$, $\Cs(A)$, $\Ker(A)$, hodnost matice (rank). Součin matic nezvyšuje hodnost, vlastnosti součtu matic.

První aplikace: V sudo-licho městě s $n$ lidmi je nanejvýš $n$ klubů. Důkaz pomocí matice incidence $M$ a ranku $M^{T}M$ nad $\GF(2)$. Města s kluby se vždy označují jako "velikosti průniků-velikosti klubů".

Druhá aplikace: 2-vzdálenostní množina bodů $M$ v $\R^d$ má mezi každými dvěma body jednu ze dvou daných vzdáleností. Odhad, že $|M|=O(d^2)$ pomocí nezávislých polynomů příslušejících bodům a malého generátoru tohoto prostoru polynomů.

Třetí aplikace: Obdélník $1\times\pi$ nelze pokrýt konečně mnoha disjunktními čtverci. Důkaz pomocí upravené definice plochy lineárnm zobrazením $f$ definovaném ve vektorovém prostoru $\R$ nad $\Q$ s $f(1)=1$ a $f(\pi)=-1$.

Cvičení (TG)

Odhady ranku $AB$ a $A+B$ shora i zdola. Zobrazení $x\to Ax$ je bijekce mezi $\Rs(A)$ a $\Im(A)$. Menší báze prostorů polynomů ve 2-vzdálenostní množině bodů. Nulo-nenulo města $\mod p$ pro $p$ prvočíslo. Reformulace důkazu sudo-licho měst nad $\R$ místo $\GF(2)$.

Nejmenší počet disjunktních úplných bipartitních podgrafů $K_n$, na které možné rozložit množinu hran $K_n$, je $n-1$. Aplikace ranku součtu matic.

14. 10.Virtuální přednáška samostudiem

Přednáška odpadá, ale rozmyslete si následující příklady a tvrzení:

Závislost a nezávislost $0-1$ vektorů nad různými tělesy. To, že jsou nějaké $0-1$ vektory nezávislé nad tělesem $F_1$ neznamená, že jsou nezávislé i nad $F_2$. Zamyslete se, jak se to může stát, a mezi kterými tělesy naopak implikace platí (zkuste $\GF(2)$, $\GF(p)$, $\Q$, $\R$).

Licho-sudo, sudo-sudo a sudo-licho města. Zkuste vytvořit co největší konstrukce a zamyslete se, jaký by mohl být horní odhad na počet klubů. Podobně zkuste konstruovat velké nenulo-nulo město $\mod p$ pro $p$ prvočíslo.

Zkonstruujte co největší 2-vzdálenostní množinu v $\R^d$ (s $\Omega(d^2)$ body). Zkonstruujte též co největší 2-vzdálenostní množinu na $d-1$-rozměrné (jednotkové) kouli v $\R^d$ a odhadněte shora alespoň o něco lépe než pro obecné množiny jejich velikost.

21. 10.Přednáška (JK)

Skalární součin vektorů, definice kolmosti, ortogonálního doplňku podprostoru. Dimenze ortogonálního doplňku. Ortogonální doplněk nad konečnými tělesy. Sudo-sudo města pomocí ortogonálního doplňku.

Prostor podmnožin hran grafu nad $\GF(2)$. Podprostor Eulerovských podgrafů $\mathcal{E}_G$ a jeho ortogonální doplněk prostor řezů grafu $\mathcal{B}_G$. Jejich dimenze a báze.

Aplikace: Vrcholy každého grafu lze rozdělit na dvě disjunktní množiny $V_1\cup V_2=V_G$, že $G[V_1]$ i $G[V_2]$ jsou Eulerovské podgrafy.

Cvičení (TG)

Dořešení příkladů z virtuální přednášky. Gossetovy polytopy jako konstrukce velké dvouvzdálenostní množiny (dokonce na kouli), kompaktnost a $\varepsilon$-skoro-dvouvzdálenostní množiny v $\R^d$. Nulo-nenulo města modulo $p^k$.

Množina fundamentálních kružnic vůči libovolné kostře grafu je lineárně nezávislá nad $\GF(2)$.

$L$-skoro-disjunktní systémy podmnožin: Systém $\{A_i\}_{i=1}^m$ podmnožin $\{1\dots n\}$ splňující $|A_i\cap A_j|\in L$ pro všechny $i\neq j$ má velikost $m\leq \sum_{i=0}^{|L|}{n\choose i}$. Konstrukce která nabývá tento odhad pro $L=\{0,1,\dots s-1\}$ z nanejvýš $s$-prvkových podmnožin $\{1\dots n\}$.

28. 10.Den vzniku Československa, přednáška odpadá

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

Silný / "domečkový" součin grafů $G\boxtimes H$: $V=V_G\times V_H$, $(u_1,u_2)\sim(v_1,v_2)$ právě když $(u_1=v_1 \vee u_1\sim v_1)\wedge (u_2=v_2 \vee u_2\sim v_2)$. Např.: $K_2\boxtimes K_2=K_4$.

Shannonova kapacita grafu $\Theta(G)=\sup_{i\geq 1}(\alpha(G^{\boxtimes i})^{1/i}$. Její aplikace pro kódy v grafech. Lovászova funkce $\vartheta(G)$ a ortonormální reprezentace grafu v $\R^n$, viz [Mat 16]. Věta $\Theta(G)\leq\vartheta(G)$ s důkazem. Aplikace na $\Theta(G)=\sqrt{5}$. Tenzorový součin a jeho vlastnosti.

Věta $\Theta(G+H)\geq \Theta(G)+\Theta(H)$ a ukázka grafu, pro který neplatí rovnost, pomocí funkcionální ortogonální reprezentace $\mathcal F$ pro $G$ a $H$. Věta $\Theta(G)\leq\dim \mathcal{F}$. Viz [Mat33].

Cvičení (TG)

Nezávislá množina v $C_5^{\boxtimes 5}$ a $\Theta(C_5)\geq \sqrt{5}$. Vlastnosti tenzorovéoh součinu. Vztahy $\alpha(G)\leq\Theta(G)\leq\vartheta(G)\leq\chi(\bar{G})=\bar{\chi}(G)$ a těsnost pro perfektní grafy. Okrajová lemmata z přednášky.

11. 11.Přednáška (JK)

Vlastní čísla grafů, charakteristický polynom grafu $p_G(x) = \mathrm{det}(x I - A)$, základní vlastnosti vl. čísel a vektorů. Silně regulární a Moorovy grafy, nutné podmínky pro jejich existenci.

Cvičení (TG)

Jaké je spektrum orientovaného acyklického grafu (DAG)? Jaký vliv mají orient. hrany neležící v žádném orient. cyklu na spektrum grafu? Jaké jsou vlastní čísla orientovaného grafu skládajícího se z několika disjunktních orient. kružnic (v závislosti na jejich délce)?

Neorientovaný graf se stupněm $\leq k$ má všechny vl. čísla mezi $-k$ a $+k$. Pro $A$ mat. sousednosti $G$ je $A^k_{xy}$ počet sledů délky právě $k$ z $x$ do $y$. $A^2_{xx}$ je stupeň x, $\mathrm{tr}(A^2)/2$ je počet hran $G$, $\mathrm{tr}(A^3)/6$ je počet trojúhelníků v $G$.

Jaké je spektrum a vl. vektory grafů $K_n$, $K_{m,n}$ a cyklu $C_n$?

18. 11.Přednáška (JK)

Vlastní čísla a jejich proplétání vůči podmatici a dalším operacím.

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

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

Vztahy barevnosti a nezávislé množiny grafu a spektra.

Cvičení (TG)

Podmínky existence silně regulárních grafů (přehledem).

Friendship theorem a jeho důkaz: Pokud mají v $G$ každé dva vrcholy $u$, $v$ právě jednoho společného souseda, pak v $G$ existuje univerzální vrchol. Důkaz přes silnou regularitu $G$ a spor s existencí takového regulárního grafu (například vl. čísly $A^2$).

Pro $d$-regulární grafy platí věta $\alpha(G)\leq\frac{n \lambda_n}{\lambda_n-d}$, důkaz volbou nezávislé $S\subseteq V$ a $x=n\mathbb{1}_S-\alpha\mathbb{1}$, použití triviální formy Raileigh principu.

Vlastní čísla a vektory $C_n$. Cvičením, že $\mathrm{tr}(A)=\sum_{i=1}^{n} \lambda_i$.

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

Proplétání vlastních čísel matic $A$ a $SAS^*$ když $SS*=I$. Aplikace na další vztahy nezávislosti, barevnosti a spektra. Formulace a aplikace věty o kvocientu matice (rozdělení na bloky a nahrazení bloku sumou / počet řádků bloku).

Cvičení (TG)

Důkaz věty o kvocientu matice, aplikace podobnosti matic. Regularita kvocientu a těsnost proplétání. Dokončení některých cvičení a případů z přednášky. $\chi(G)\leq 1+\lambda_1$. Spektrum cesty $P_n$.

2. 12.Přednáška (TG)

Náhodné procesy, Markovovské řetězce (MC), konečnost, distribuce $\varrho$ a stochastická matice přechodu $P$, invariance vůči času, reprezentace orientovaným grafem, dosažitelnost, silná souvislost a ireducibilita. Stabilní distribuce $\pi$ a její unikátnost na ireducibilních MC. Cyklicita stavu a acyklické MC.

Symetrické markovovské řetězce a procházky na (vážených) grafech, stabilní distribuce $\pi_v=\deg(v)/(\sum_{u\in V}\deg(u))$. Konvergence procházky v acyklickém MC k stabilní distribuci a důkaz pomocí rozkladu distribuce na vlastní vektory.

MC procházky na (váženém) konečném souvislém grafu $G$ z distribuce $\varrho$ splňuje: $$||\rho P^t-\pi||_1\leq \mu^t\sqrt{n}$$ pro $\mu=\max(\lambda_2,-\lambda_n)$.

Definice hranové, (vnější) vrcholové, spektrální expanze a spectral gap pro $d$-regulární grafy [Wikipedia]. Chegerova nerovnost a Expander mixing lemma (bez důkazu). Spektrální expanze náhodných $d$-regulárních grafů je skoro jistě nanejvýš $2\sqrt{d-1}+O(1)$ (bez důkazu).

Pohádka o aplikacích expandérů, Markov chain Monte carlo, konstrukce expandérů, zvyšování expanze.

Cvičení (TG)

Vlastnocti MC (reducibilita, cyklicita a rozklad, invariance k času), vztah matice $P$ a $A$ pro graf, vztah normy $||x||_2$ a $||x||_1$.

9. 12.Přednáška (TG)

Motivace a základní pojmy kódů. Definice $(n, m, d)_q$-kódu: $n$ je délka kódových slov nad abecedou velikosti $q$, $m$ je délka vstupních slov nad stejnou abecedou nebo $m=\log_q(M)$ pro $M$ počet kódových slov, $d$ je nejmenší Hammingova vzdálenost kódových slov. Kód se vzdáleností $d$ opravuje $t=\lfloor\frac{d-1}{2}\rfloor$ chyb.

Základní kódy a trocha historie: triviální kód (identita), $k$-opakovací kód, paritní bit, kód 2-of-5 (10 možností, jak nastavit právě 2 bity z 5ti), Hammingův $(7,4,3)_2$-kód. Jejich parametry.

Sphere packing bound (Hamming bound) a Sphere covering bound pro velikost největšího kódu $M$ pro dané $n$, $d$ a $q$: $$\frac{q^n}{\sum_{i=0}^{d-1}\binom{n}{i}(q-1)^i}\leq M \leq \frac{q^n}{\sum_{i=0}^{t}\binom{n}{i}(q-1)^i}$$

Perfektní kódy jsou ty, které dosahují sphere packing bound.

Krátká odbočka do vztahu minimální vzdálenosti a chování na zašumněném kanále, srovnání nejhoršího případu (kde se hodí min. vzdálenost) a průměrného případu (kde je důležité rozložení kódových slov). Povídání o technice Polar codes. Článek s nejpokročilejšími kódy: Erdal Arikan: Channel polarization [arXiv] [handout]

Lineární kódy, generující matice $G$ a kontrolní matice $H$. Kóduje se kombinací řádků $G$: $c=x^T G$, kód se ověřuje $Hc=0$. Lemma, že min. vzdálenost kódu se rovná min. Hammingově vzdálenosti nenulového vektoru od 0. Generující matice a vlastnosti obecných Hammingových kódů [Wiki].

Cvičení (TG)

Další vlastnosti kódů z úvodu, pravděpodobnost odhalení chyby na zašumněném kanále, parametry. Perfektnost zmiňovaných kódů.

Lemma o vztahu $G$ a $H$ ve standartním tvaru. Pokud $G=\left(I_m | A\right)$, pak $H=\left(-A^T | I_{n-m} \right)$.

Golayův binární kód [Wiki] a jeho vlastnosti a perfektnost jeho zkrácení o 1 bit.

16. 12.Přednáška (JK)

Perfektní kódy, Lloydova věta

Cvičení (JK)

6. 1.Přednáška (JK)

Podmínky existence perfektních kódů, charakterizace existence pro abecedy velikosti mocniny prvočísla.

Cvičení (TG)

Domlouvání skriptíček, zkoušek, společné přípravy, ..., a úlohy:

Najděte graf, jehož všechny kartezské mocniny jsou vzdálenostně regulární.

Dokažte, že $n$-tá kartezská mocnina úplného bipartitního grafu $K_{a,b}$ obsahuje $1$-perfektní kód jen v~případě $n=1$ a ($a=1$ nebo $b=1$).

Skriptíčka

Láďa Láska a Honza Musílek začali k přednášce LAK 2013 psát skriptíčka převážně pro osobní potřebu. Dalsí studenti LAKu je v roce 2014/2015 rozšířili a upravili, aby z nich mohla časem vzniknout více méně oficiální skripta k LAKu i jen tak pro zajímavost.

Pokud si vezmete část skriptíček - ať už kapitolu, sekci nebo jen větu a její důkaz - pomůžete nám přiblížit se k tomu a navíc budete mít všichni na konci semestru lepší studijní materiály. Možná se dočkáme i vydání v KAM-sériích, v tom případě za větší přispění nabízíme i spoluautorství.

GITový repozitář najdete na githubu. Pokud tam máte účet, dám vám přístup pro zápis. Pokud nechcete spolupracovat GITem, pošlete mi patch nebo prostě upravený soubor (i s tím, z jakého souboru či verze jste úpravy prováděli).

Pokud chcete, můžete sekce samozřejmě i přejmenovávat, rozdělovat, spojovat či přečíslovat. Soubory, jak jsou teď, zkuste prosím spíše zachovat, přesypeme je nějak podle změn sekcí až bude většina částí doupravena. Pokud byste chtěli nějak změnit či pridat globální makra a pod., určitě je to možné, jen mi o tom napište email.

kol. autorů: Lineární algebra v kombinatorice Hodně přepracovaná a o dost kompletnější skripta [PDF z 25. 9. 2015] (stále nehotová).

L. Láska, J. Musílek: Lineární algebra v kombinatorice Původní, velmi hrubá verze[PDF před úpravami]

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.

[MS] MacWilliams, Sloane: Theory of error correcting codes [online PDF] - klasická kniha o perfektních kódech.

Jaj