Kombinatorická a výpočetní geometrie 2 (2020/2021)

Záznam v SISu

Distanční výuka:

Přednáška: ve středu 14:00 "v S3"

Cvičení: ve středu 15:40 "v S3" (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, zlomková Hellyho věta, barevná Carathéodoryho věta, Tverbergova věta, geometrické selekční věty.

Literatura:

[M] Hlavní zdroj: kniha J. Matoušek: Lectures on Discrete Geometry

• 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
  • [M] Kapitola 3
  • [S] pro hlubší zájemce: Andrew Suk, On the Erdos-Szekeres convex polygon problem (časopisová verze), [HNPT] A. Holmsen et al., Two extensions of the Erdos-Szekeres problem
• Půlící přímky:
  • [M] Části kapitoly 11
  • [GGT] Skriptíčka, dva chybějící důkazy
  • [Ni] Gabriel Nivasch, An Improved, Simple Construction of Many Halving Edges
• Dolní obálky a Davenport–Schinzelovy posloupnosti:
  • [M] Kapitola 7 (části 7.1-7.4)
  • [N] pro hlubší zájemce: Gabriel Nivasch, Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations (časopisová verze)
  • [P] pro hlubší zájemce: Seth Pettie, Sharp Bounds on Davenport-Schinzel Sequences of Every Order (časopisová verze)
• Průnikové vlastnosti konvexních množin a geometrické selekční věty:
  • [M] Kapitoly 8, 9

Obsah přednášek:

3.3. (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

10.3. (JK)

• Konstrukce množiny 2^{k-2} bodů bez k bodů v konvexní poloze

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

17.3. (JK)

• 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 přímek 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
  • 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})

24.3. (JK)

[Ni] nebo [GGT] 6.2

• Konstrukce pro dolní odhad h(n) >= Omega(n log n)
• 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í vrcholům prostřední úrovně v duálním arrangementu
• Nivaschova konstrukce arrangementu přímek s mnoha vrcholy prostřední úrovně: h(n) >= Omega((n/ln n) e^{(ln 4)^{1/2}(ln n)^{1/2}})
  • 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)

31.3. (JK)

• Výpočet počtů přímek a vrcholů v Nivaschově konstrukci a odhad h(n)

[M] 7.1

• Č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) (důkaz jako cvičení)

7.4. (JK)

[M] 7.1, 7.2, 7.3, [N] 1.4, [P] 1.2, 1.3

• 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
• 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)

14.4. (JK)

[M] 7.4

• 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á
• 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)

21.4. (JK)

[M] 8.1, 8.2

• zopakování znění Hellyho, Carathéodoryho a Radonovy věty
• zlomková Hellyho věta
• barevná Carathéodoryho věta

28.4. (JK)

[M] 8.3

• Tverbergova věta, varianta pro konvexní kužele

5.5 (JK)

[M] 8.3, 9.1

• Barevná Tverbergova věta (pouze znění)

• První selekční lemma, dva důkazy
• v případě n bodů v obecné poloze můžeme požadovat společný bod ve vnitřcích simplexů

19.5. (JK)

[M] 9.2

• Druhé selekční lemma
• Erdősova–Simonovitsova věta pro hypergrafy

26.5. (JK)

[M] 9.3

• Order type množiny bodů (nebo posloupnosti bodů)
• Same-type lemma
• Erdősova–Szekeresova věta pro lineárně velké podmnožiny v konvexní poloze (Positive fraction Erdős–Szekeres theorem)