Kombinatorická a výpočetní geometrie II

(Jan Kynčl, Martin Tancer, KAM)

LS 2015/2016, 2/2 Z, Zk

Přednáška: Pondělí 10:40 v S8, začínáme 29.2.

Cvičení se bude konat podle rozvrhu na stránce cvičení, nejspíš v pondělí od 9:00 v S8 (před přednáškou).

Zkoušky:

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
  • NOVÉ: Andrew Suk, On the Erdos-Szekeres convex polygon 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)
• Erdősův problém různých vzdáleností:
  • Blog Terrence Taa (shruntí postupu Gutha a Katze, obsahuje mnoho zjednodušení a drobné nepřesnosti)
  • Článek od Gutha a Katze (s kompletním důkazem vylepšeného odhadu, ale těžko čitelný)
• Průnikové vzory konvexních množin a selekční věty:
  • Kapitola 8 a část kapitoly 9 v knize J. Matoušek: Lectures on Discrete Geometry

Obsah přednášek

29.2. (JK)

• Erdős–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

7.3. (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}):
  • 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
  • Důsledek: každá obecná přímka protíná nejvýše n/2 půlících úseček

14.3. (JK)

• Dokončení odhadu h(n) <= O(n^{3/2})
• 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) >= O(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ě

21.3. (JK)

• Správnost Nivaschovy konstrukce, výpočet počtů přímek a vrcholů

• Tři otázky: Jaká je maximální složitost buňky v arrangementu n úseček? 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? Vzájemné souvislosti
• 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

4.4. (JK)

• lambda_2(n)<=2n-1
• lambda_3(n)<=2n ln(n) + 3n
• známé odhady na lambda_s(n)
• Ackermannova funkce, inverzní Ackermannova funkce alfa(n), různé definice
• sigma(n) = maximální složitost dolní obálky n úseček v rovině
• Věta: sigma(n) roste superlineárně. Začátek důkazu (Shorova konstrukce) — S_1(m) je vějíř velikosti m, S_k(2) vznikne rozlepením S_{k-1}(2)

11.4. (JK)

• dokončení Shorovy konstrukce: 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)
• hlavní rekurze: 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)

18.4. (MT)

• Erdősův problém různých vzdáleností. Zmínka o horním odhadu pomocí bodů v mřížce. Dolní odhad od Gutha a Katze, Omega(n/log n). (V následujících přednáškách si ukážeme důležité kroky důkazu).
• Elekes–Sharirův přístup, parametrizace rotací, rotace z x do y tvoří přímku l_(x->y) při vhodné parametrizaci.
• Lemma o čtveřicích (pořádný důkaz bude cvičení). Náznak, proč je důležité, pokud věta Gutha a Katze neplatí, tak máme Omega(n^3 log n) incidencí mezi přímkami l_(x->y).
• Průsečíky/incidence přímek v R^3. Příklady, kdy n^2 přímek může mít více než Theta(n^3 log n) incidencí:
  • mnoho přímek prochází týmž bodem nebo
  • mnoho přímek leží v téže rovině nebo
  • mnoho přímek leží v tomtéž hyperbolickém paraboloidu či jednodílném hyperboloidu (souhrnně regulu).
• Jiný popis regulu.
• Guth–Katzova věta o přímkách v R^3 (výše zmíněné protipříklady jsou esenciálně jediné).
• Lemma ověřující předpokladů věty o přímkách, pokud je aplikovaná na přímky l_(x->y) pocházející z množiny n bodů. (Část důkazu bude cvičení a část důkazu pouze náznakem.)

25.4. (MT)

• Důkaz Guth–Katzova odhadu pro počet různých vzdálenstí pomocí věty o přímkách.
• Zjemnění věty o přímkách - věta o počtu bodů v mnoha přímkách: pokud máme asi n^2 přímek v R^3 takových že každá rovina či regulus obsahují nejvýše O(n) z těchto přímek, potom je nejvýše O(n^3/k^2) bodů, jimiž prochází alespoň k z těchto přímek. Důkaz, že tato věta implikuje větu o přímkách.
• Polynomy více proměnných nad R; nulová množina Z(p) polynomu p, reducibilní/ireducibilní polynom, dimenze prostoru polynomů stupně nejvýše k v m proměnných je binom(m+k,k).
• Tvrzení o existenci nulujícího polynomu: pro zadanou množinu Y v R^m s méně než binom(m+k,k) body platí, že existuje polynom p stupně nejvýše m takový, že Y je podmnožina Z(p).
• Tvrzení o polynomu nulujícím se na přímce: pokud je polynom stupně k nulový v k+1 bodech nějaké přímky, potom je nulový ve všech bodech této přímky.
• Velmi hrubý náznak postupu, jak dokázat větu o počtu bodů v mnoha přímkách pro k=2.

2. 5. (MT)

• Věta o sendviči pro otevřené množiny (bez dk.). Diskrétní věta o sendviči.
• Diskrétní polynomiální věta o sendviči.
• Dělicí polynom. Věta o dělicím polynomu.
• Připomenutí Szemerédi–Trotterovy věty. Lemma pro slabý odhad počtu incidencí I(B,L) <= lambda + beta^2.

9. 5. (MT)

• Důkaz Szemerédi–Trotterovy věty metodou dělicího polynomu.
• Důsledek, slabší odhad na počet bodů, co jsou alespoň v k přímkách.
• Náznak důkazu o počtu bodů v mnoha přímkách pro k alespoň 3. Podrobně vyřešena část, kdy alespoň polovina bodů ze znění nepatří do nulové množiny dělicího polynomu.
• Zlomková Hellyho věta (zatím jen znění).

16. 5. (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) a Tverbergova věta.
• Příprava před důkazem, vektory w_i a tenozorový součin.

23. 5. (MT)

• Sarkaria-Onnovo lemma a důkaz Tverbergovy věty.
• 1. selekční věta.
• 2. selekční věta a Pachova selekční věta (neformálně, bez důkazu, nebude se zkoušet).