Kombinatorická a výpočetní geometrie II

LS 2017/2018, 2/2 Z, Zk. Záznam v SISu

Přednáška: středa 14:00 v S9

Cvičení: konají se ve středu 15:40 v S9 (po přednášce) podle rozvrhu na stránce cvičení.

Anotace:
Navazuje na přednášku Kombinatorická a výpočetní geometrie I. Letošní předběžný plán: konvexně nezávislé množiny, půlící přímky, složitost dolní obálky úseček a Davenport–Schinzelovy posloupnosti, věty Hellyho typu přes simpliciální komplexy, vnořitelnost. Popř. další témata.

Literatura:
(bude průbežně doplňována)

• Konvexně nezávislé množiny:
  • Kapitola 3 ve skriptech Jiřího Matouška: PS soubor pro oboustranný tisk, PDF soubor pro čtečky a tablety
  • Kapitola 3 v knize J. Matoušek: Lectures on Discrete Geometry
  • horké novinky pro zájemce: Andrew Suk, On the Erdos-Szekeres convex polygon problem (časopisová verze), A. Holmsen et al., Two extensions of the Erdos-Szekeres problem
• Půlící přímky:
  • Části kapitoly 11 v knize J. Matoušek: Lectures on Discrete Geometry
  • Skriptíčka, dva chybějící důkazy
  • Gabriel Nivasch, An Improved, Simple Construction of Many Halving Edges
• Dolní obálky a Davenport–Schinzelovy posloupnosti:
  • Kapitola 7 v knize J. Matoušek: Lectures on Discrete Geometry
  • pro hlubší zájemce: Gabriel Nivasch, Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations (časopisová verze), Seth Pettie, Sharp Bounds on Davenport-Schinzel Sequences of Every Order (časopisová verze)
• Rovinnost a Hanani-Tutteova věta:
  • Kapitoly 1.1 a 1.4 v M. Schaefer: Hanani-Tutte and Related results. K nalezení zde. (Varování: v jiném značení a s částečně jinými důkazy než na přednášce. Článek je mnohem obsažnější.)
• Simpliciální komplexy:
  • Kapitola 1 v knize J. Matoušek: Using the Borsuk-Ulam Theorem
• Vnořování simpliciálních komplexů: Varování: tato část přednášky je poskládána z článků, které používají některé pokročilejší termíny (těm se na přednášce vyhýbáme). Články jsou též v jiném značení. Raději doporučuji se spoléhat na zápisky z přednášky. Na vyžádání mohu také poskytnout naskenovanou svoji přípravu. Odkazy na příslušné články (v pořadí podle obtížnosti):
  • Apendix D v článku J. Matoušek, M. Tancer, U. Wagner: Hardness of embedding simplicial complexes in R^d.
  • Sekce 2 v článku M.H. Freedman, V. Krushkal, P. Teichner: Van Kampen's embedding obstruction is incomplete for 2-complexes in R⁴.

Obsah přednášek:

21.2. (JK)

• Erdősova–Szekeresova věta, důkaz z Ramseyovy věty, důkaz dvojitou indukcí přes misky a čepice
• Konstrukce množin bez k-misky a l-čepice
• Konstrukce množiny 2^{k-2} bodů bez k bodů v konvexní poloze

28.2. (JK)

• k-díra, existence 5-díry, neexistence 7-díry v hortonovských množinách

• Půlící přímka, půlící úsečka
• Vždy existuje aspoň n/2 půlících přímek, pro body v konvexní poloze je to přesně n/2
• Definice h(n) = maximální možný počet půlících úseček pro n bodů v obecné poloze v rovině
• Lovászův horní odhad h(n) <= O(n^{3/2}), začátek důkazu:
  • U každého bodu v úhlu proti dvěma sousedním půlícím úsečkám je přesně jedna další půlící úsečka

7.3. (JK)

• Lovászův horní odhad h(n) <= O(n^{3/2}), dokončení důkazu:
  • Každá obecná přímka protíná nejvýše n/2 půlících úseček
  • Dokončení odhadu h(n) <= O(n^{3/2}) pomocí rozkladu na pásy
• Geometrický graf půlících úseček splňuje následující identitu: součet počtu křížení a kombinačních čísel ((d(v)+1)/2 nad 2) je roven (n/2 nad 2); důkaz spojitým přesouváním bodů z konvexní polohy
• Kombinací s průsečíkovým lemmatem dostaneme horní odhad h(n) <= O(n^{4/3})
• Konstrukce pro dolní odhad h(n) >= Omega(n log n)
• Nivaschův dolní odhad h(n) >= Omega((n/ln n) e^{(ln 4)^{1/2}(ln n)^{1/2}}):
  • Speciální dualita bodů a přímek, bod p je nad přímkou l právě tehdy, když přímka p* je nad bodem l*
  • Půlící přímky odpovídají bodům prostřední úrovně v duálním arrangementu
  • Konstrukce arrangementů L_0, L_1, L_2, ... a množin vrcholů V_0, V_1, V_2, ... prostřední úrovně
  • Ověření správnosti konstrukce (V_m jsou skutečně vrcholy prostřední úrovně v arrangementu L_m)
  • ...zbývá ještě spočítat velkosti L_m a V_m a odhadnout h(n)

14.3. (JK, MT)

• Výpočet počtů přímek a vrcholů v Nivaschově konstrukci

• Kuratowského a Wagnerova věta, přehledově.
• Hanani-Tutteova věta: graf je rovinný, právě když má nakreslení takové, že každá dvojice nezávislých hran se v tomto nakreslení protíná suděkrát a každý průnik je křížení.
• PL nakreslení grafu v obecné poloze.
• Lemma: v každém PL nakreslení v obec. poloze grafu K_5 nebo K_{3,3} je počet průsečíků dvojic nezávislých hran lichý.
• Důkaz HT-věty pro případ PL nakreslení v obec. poloze (s využitím cvičení pro dělení K_5 a K_{3,3}).
• Rovinnost se dá testovat v lineárním čase (Hopcroft-Tarjan), pouze zmínka.
• Průsečíkový vektor nakreslení grafu.

21.3. (MT)

• Vektor pohybu prstu.
• Lemma: průsečíkové vektory dvou nakreslení se liší o lin. kobinaci vektorů pohybu prstu. Naopak přičteme-li k průsečíkovému vektoru nějakou lin. kombinaci vektorů pohybu prstu, dostaneme opět průsečíkový vektor nějakého nakreslení.
• Algoritmus pro testování rovinnosti pomocí lemma výše a Hanani-Tutteovy věty.

• Geometrický simpliciální komplex, polyédr.
• Abstraktní simpliciální komplex. Přechod mezi abstraktním a geometrickým simpl. komplexem.
• Poznámky: izomorfismus abstr. simpl. komplexů indukuje homeomorfismus na odpovídajících geometrických; dimenze simpl. komplexu; grafy jako 1-rozměrné simpliciální komplexy.
• Lineární zobrazení z simpliciálního komplexu do R^d.

28.3. (MT)

• Podrozdělení, po částech lineární zobrazení (PL-zobrazení), PL-zobrazení v obecné poloze.

• Topologické/PL/lineární vnoření.
• Varování: Lineární a PL vnoření se liší např. pro 2-komplexy v dimenzi 3, PL a topologická vnoření se liší např. pro 4-komplexy v dimenzi 5.
• Bryantova věta: v kodimenzi alespoň 3 PL a topologická vnoření splývají (jenom znění).
• Průsečíkové číslo nad celými čísly:
• Orientovaný k-simplex
• Průsečíkové číslo pro orientované k-simplexy v obecné poloze a ověření, že je dobře definované.
• Průsečíkové číslo v PL-zobrazení.

4.4. (MT)

• Van Kampenova obstrukce:
  • Průsečíkový vektor; vektor pohybu prstu.
  • Lemma: (i) dva průsečíkové vektory se liší o celoč. kombinaci vektorů pohybu prstu; (ii) přičtením celoč. kombinace vektorů pohybu prstu k průsečíkovému vektoru dostaneme opět průsečíkový vektor. (Důkaz pouze náznakem.)
  • Definice van Kampenovy obstrukce; její trivialita.
  • Věta o van Kampenově obstrukci: Pokud lze k-komplex vnořit do 2k prostoru, potom je obstrukce triviální. Naopak, je-li obstrukce triviální a k není 2, potom lze příslušný komplex vnořit do 2k-prostoru. (Důkaz opět náznakem.)
• Určování triviality obstrukce: krok (i), volba kanonického průsečíkového vektoru.
• Příklady k-komplexů nevnořitelných do 2k-prostoru, zobecnění grafů K₅ a K_3,3.

11.4. (MT)

• Určování triviality obstrukce: krok (ii), převod na lineární systém rovnic nad celými čísly.
• Řešení systému rovnic nad celými čísly
  • Smithova normální forma matice.
  • Řešení systému pomocí Smithovy normální formy (stačí dokonce nepožadovat podmínku s dělitelností).
  • Převod libovolné matice s celými čísly na Smithovu normální formu (pouze slabší verze bez podmínky na dělitelnost).

• Připomenutí Hellyho věty.
• Nerv systému množin, d-reprezentovatelnost simpliciálního komplexu.
• Algoritmická poznámka: rozpoznávání d-reprezentovatelnosti patří do PSPACE a je NP-těžké (bez důkazu).
• Každý rovinný graf je 2-reprezentovatelný jako speciální případ `Kissing circle theorem'. K₅ a K_3,3 jsou též 2-reprezentovatelné.
• Věta (Wegner): graf získaný z K₅ podrozdělením každé hrany jednou není 2-reprezentovatelný.
• Věta (Wegner, Pereľman): Každý k-komplex je (2k+1)-reprezentovatelný (bez důkazu).
• Zobecnění Wegnerovy věty: Barycentrické podrozdělění k-skeletu (2k+2)-simplexu není 2k-reprezentovatelné (pouze velmi hrubý náznak důkazu, využije se vlastností van Kampenovy obstrukce).

18.4. (MT)

• Křivková souvislost.
• Hellyho věta pro křivkově souvislé množiny v rovině.
• k-souvislost
• Hellyho věta pro k-souvislé množiny v R^2k.
• Zlomková Hellyho věta. Zatím jen znění, pozorování, že stačí dokazovat pro kompatní množiny, a lexikograficky nejmenší bod v kompaktní množině (jako začátek důkazu).

25.4. (MT)

• Zlomková Hellyho věta - důkaz.

• Barevná Carathéodoryho věta.
• Motivace k Tverbergově větě (dělení 16 bodů v rovině na 4 množiny).
• Tverbergova věta: (d+1)(r-1)+1 bodů v R^d lze rozdělit do r disjuktních množin tak, že konvexní obaly těchto množin mají neprázdný průnik.
• Sarkaria-Onnovo lemma. Důkaz Tverbergovy věty modulo lemma.

2.5. (JK)

• Čtyři otázky a jejich vzájemné souvislosti:
  • Jaká je maximální složitost buňky v arrangementu n úseček v rovině?
  • Jaká je maximální složitost "scény" v arrangementu n úseček, kterou vidí 1 bod?
  • Jaká je maximální složitost dolní obálky arrangementu n úseček?
  • Jaká je maximální složitost dolní obálky grafů n spojitých funkcí, z nichž každé dvě se protínají nejvýše v s bodech?
• Davenport–Schinzelova posloupnost řádu s nad n-prvkovou abecedou, maximální délka lambda_s(n)
• lambda_1(n)=n, lambda_2(n)>=2n-1
• lambda_2(n)<=2n-1
• Hrubý horní odhad lambda_s(n) <= O(sn^2)
• lambda_3(n)<=2n ln(n) + 3n
• známé odhady na lambda_s(n)
• Ackermannova funkce A(n) a hierarchie A_k(n), inverzní Ackermannova funkce alfa(n) a hierarchie alfa_k(n), různé definice

9.5. (JK)

• sigma(n) = maximální složitost dolní obálky n úseček v rovině
• Věta: sigma(n) roste superlineárně. Shorova konstrukce — S_1(m) je vějíř velikosti m, S_k(2) vznikne rozlepením S_{k-1}(2), obecný indukční krok pro konstrukci S_k(m), složitost dolní obálky S_k(m) je aspoň (k/2)*počet úseček v S_k(m)
• horní odhady na lambda_3(n): m-rozložitelná posloupnost, Psi(m,n) = maximální délka m-rozložitelné DS-posloupnosti řádu 3 nad n-prvkovou abecedou
• lambda_3(n) = Psi(2n-1,n), tj. každá DS-posloupnosti řádu 3 nad n-prvkovou abecedou je (2n-1)-rozložitelná

23.5. (JK)

• hlavní rekurze pro Psi(m,n): je-li m,n,R >= 1, m<= R, m = m_1 + m_2 + ... m_R, m_i >= 0, pak existuje rozklad n = n_1 + n_2 + ... n_R + n* takový, že Psi(m,n) <= 4m +4n* + Psi(R,n*) + suma Psi(m_i,n_i)
• Důsledek 1: Psi(m,n) <= 4m log(m) + 6n
• Důsledek 2: Psi(m,n) <= 8m log*(m) + 10n
• Důsledek k: Psi(m,n) <= 4km alfa_{k+1}(m) + (4k+2)n, nakonec zvolíme k = alfa(n)