| tags:[ school ]
Kombinatorika a grafy III
Koncentrované znalosti z kurzu Kombinatorika a grafy III ↗ Roberta Šámala na MFF UK.
Termíny zkoušky:
24.01.2019 - Čtvrtek 10:00 S10
30.01.2019 - Středa 13:00 S6
12.02.2019 - Úterý 10:00 S10
Zkouškové příklady
Buď G graf s n vrcholy takový, že jeho hrany jsou pokryty párováními M1, M2, …, Mn. Předpokládejme, že neexistují 1 \leq i,j \leq n, pro něž existují po dvou různé vrcholy a,b,c,d, že ab je v Mi, bc v Mj, cd v Mi. Ukažte, že pak ||G|| = o(n^2).
Ukažte, že má-li graf stromovou šířku větší než 3k, pak obsahuje brambli řádu alespoň k+1. Nepoužívejte větu o dualitě, smyslem je dokázat slbší verzi jinak. Použijte postup navržený v 5. sérii cvičení.
Nechť G je 2-degenerovaný, v0 je vrchol G a L je přiřazení seznamů vrcholům G t.ž. |L(v)| \geq 3 pro v \in V(G) \setminus {v0} a |L(v0)|=1. Ukažte, že G je L-obarvitelný.
Minory
Minor – dvě definice
Třídy definované přes zakázané minory
Hadwigerova hypotéza
If all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph.
Rozklad pomocí klikových sum
Hadwigerova hypotéza pro malá k
Klika jako minor grafů s hodně hranami (a důsledek pro Hadwigerovu hypotézu)
Linkovanost (zatím jen definice)
2k-souvislost a K4k-minor implikují k-linkovanost Důsledek: f(k)-souvislost implikuje k-linkovanost, pro vhodné f. Důsledek: Průměrný stupeň g(k) implikuje dělení Kk, pro vhodné g.
Stromové rozklady: definice, základní vlastnosti. Stromová šířka, její monotonie vzhledem k minorům, tw(Kn)=n−1. Bramble.
Třída grafů omezené stromové šířky – uzavřenost na minory, popis pomocí zakázaných minorů. Důkaz věty o dualitě stromové šířky. Závěrečné ověření (že nalezený rozklad funguje) jsme nestihli. Můžete se podívat na kapitolu 12 knihy Diestel – Graph Theory (Theorem 12.3.9). Případně i nové vydání (trochu jinak formulovaný důkaz) přímo na webu autora.
Algoritmus na maximální nezávislou množinu ve stromu. Algoritmus na maximální nezávislou množinu v grafu s daným stromovým rozkladem. Informativně: hledání tw a optimálního stromového rozkladu. Stromová šířka a hra cops&robber. Informativně: graph minor theorem, Courcelle’s theorem, Grid theorem.
Regularity lemma podle knihy R. Diestela (kap. 7.4, 7.5)
Definice ε-regulární pár, ε-regulární rozklad. Znění Szemerédiho regularity lemma. (Zatím bez důkazu.) Lemma: počet vrcholů s dost velkým počtem sousedů. Lemma: pokud je H podgraf grafu regularity, je i podgraf původního grafu. Ilustrace a důkaz pro H=K3. Důkaz pro obecné H.
V náhodných grafech tvoří skoro jistě všechny dost velké množiny regulární pár. Zdroj [ZD], přednáška 11.11.2017 Aplikace Regularity lemmatu: Erdös-Stoneova věta [D], kap. 7.5 nebo [ZD], 26.10.2015 removal lemma pro trojúhelníky. [AS], kap. 17.4 (property testing triangle-freeness nebo [ZD], 26.10.2015
Property testing – algoritmy na obrovských grafech. Důkaz Regularity lemma. [AS] kap. 17.3 nebo [D], kap. 7.4.
Vybíravost (seznamové barvení) definice úvodní pozorování neomezenost pro bipartitní grafy rovinné grafy – vybíravost je alespoň 5 rovinné grafy – vybíravost je max. 5 polynomiální metoda – Chevalley-Warningova věta s nedokončeným důkazem podle poznámek Zd. Dvořáka
Polynomiální metoda
Theorem. A polynomial f of degree n over a field F has at most n roots in F.*
Proof. ↗ The results is obviously true for polynomials of degree 0 and degree 1. We assume it to be true for polynomials of degree n−1. If a is a root of f, f=(x−a)q where q has degree n−1. Since f(b)=0 if and only if a=b or q(b)=0, it follows by our inductive assumption that f has at most n roots.
Následující je převzato z přehledu Nogy Alona ↗.
Lemma. Let P(x1,…,xn) be a polynomial in n variables over an arbitrary field F. Suppose that the degree of P as a polynomial in xi is at most ti for 1 \leq i \leq n, and let Si \subsetneq F be a set of at least ti+1 distinct members of F. If P=0 for all n-typles (x1,…,xn) \in S1 x … x Sn, then P \equiv 0.
Proof. We apply inductino on n. For n=1, the lemma is proved by the previous theorem. Assuming that the lemma holds for n-1, we prove it for n (n \geq 2). Given a polynomial P(x1,…,xn) and set Si satisfying the hypothesis of the lemma, let us write P as a polynomial in xn, that is, P=\sum_{i=0}^{t_n} P_i(x_1,\dots,x_{n-1}) x_n^i, where each P_i is apolynomial with xj-degree bounded by t_j. For each fixed (n-1)-tuple (x_1,…,x_{n-1}) \in S_1 x … x S_{n-1}, the polynomial in x_n obtained from P by substituting the values of x_1,…,x_{n-1} vanishes for all x_n \in S_n, and is thus identically 0. Thus P_i(x_1,…,x_{n-1}) = 0 for all (x_1,…,x_{n-1}) \in S_1 x … x S_{n-1}. Hence, by the induction hypothesis, P_i \equiv 0 for all i, implying that P \equiv 0. This completes the induction and the proof of the lemma.
Chevalley-Warningova věta a aplikace
Nullstellensatz (spec. případ) a aplikace na vybíravost grafů
Další info v pěkném přehledu Nogy Alona ↗. (Na první stránce je i vysvětlená souvislost s Hilbertovou Nullstellensatz.) podle poznámek Zd. Dvořáka
Pakování koster