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