Kombinatorická a výpočetní geometrie II (2019/2020)
Combinatorial and Computational Geometry II (2019/2020)
Jan Kynčl, KAM
Záznam v SISu
Entry in SIS
Přednáška: úterý 15:40 v S1 (začínáme 25.2.)
Lecture: Tuesdays 15:40 in S1 (we start on 25.2.)
Cvičení: konají se v úterý 17:20 v S1 (po přednášce) podle rozvrhu na stránce cvičení.
První cvičení je v plánu 25.2.
Exercise sessions: after the lecture at 17:20 v S1 according to the schedule on the exercise webpage.
The first exercise is planned on 25.2.
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, další témata.
Annotation:
A continuation of the lecture Combinatorial and Computational Geometry I.
A preliminary plan: convexly independent subsets, halving lines, complexity of the lower envelope of segments and Davenport–Schinzel sequences, fractional Helly theorem, colorful Caratheodory theorem, Tverberg theorem, other topics.
Literatura:
(bude průbežně doplňována)
[M] Hlavní zdroj: kniha J. Matoušek: Lectures on Discrete Geometry
- Konvexně nezávislé množiny:
- Půlící přímky:
- Dolní obálky a Davenport–Schinzelovy posloupnosti:
- Průnikové vlastnosti konvexních množin a geometrické selekční věty:
Literature:
(will be updated during the semester)
[M] Main resource: the book J. Matoušek: Lectures on Discrete Geometry
- Convexly independent subsets:
- Halving lines:
- Lower envelopes and Davenport–Schinzel sequences:
- Intersection patterns of convex sets and geometric selection theorems:
Obsah přednášek:
25.2. (JK)
Konvexně nezávislé podmnožiny v rovině
- 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
3.3. (JK)
- Konstrukce množiny 2^{k-2} bodů bez k bodů v konvexní poloze
Konvexní díry v rovině
- k-díra, existence 5-díry, neexistence 7-díry v hortonovských množinách
Půlící přímky
- 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ě
10.3. (JK)
- 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})
- 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í vrcholům prostřední úrovně v duálním arrangementu
- Myšlenka konstrukce arrangementu rekurzivním nahrazováním přímek svazky přímek, z vrcholu prostřední úrovně vznikne mřížka, přidá se nová přímka podél její diagonály
17.3. (samostatné studium)
[Ni] nebo [GGT] 6.2
- Nivaschova konstrukce arrangementu přímek s mnoha vrcholy prostřední úrovně
- 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)
- Výpočet počtů přímek a vrcholů v Nivaschově konstrukci a odhad h(n)
24.3. (samostatné studium)
Dolní obálky a Davenport–Schinzelovy posloupnosti
[M] 7.1, 7.3, [N] 1.4, [P] 1.2, 1.3
- Č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 (důkaz jako cvičení)
- hrubý horní odhad lambda_s(n) <= O(sn^2) (důkaz jako cvičení)
- 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
31.3. (samostatné studium)
[M] 7.2
- 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)
7.4. (samostatné studium)
[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)
14.4. (samostatné studium)
Průnikové vlastnosti konvexních množin
[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
21.4. (samostatné studium)
[M] 8.3
- Tverbergova věta, varianta pro konvexní kužele
- Barevná Tverbergova věta (pouze znění)
28.4. (samostatné studium)
Geometrické selekční věty
[M] 9.1, 9.2
- 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ů
- Druhé selekční lemma (znění)
5.5. (samostatné studium)
[M] 9.2
- Druhé selekční lemma (důkaz)
- Erdősova–Simonovitsova věta pro hypergrafy
12.5. (samostatné studium)
[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)
19.5. (samostatné studium pro zájemce)
[S], [HNPT] Theorem 2.4 + Proof of Theorem 1.3
- Sukův horní odhad 2^{n+o(n)} v Erdősově–Szekeresově větě, přesnější analýza důkazu a výpočet o(n) (Holmsen et al.)
Topics of lectures:
25.2. (JK)
Convexly independent subsets in the plane
- Erdős–Szekeres theorem, proof from Ramsey's theorem, proof by double induction using cups and caps
- Construction of point sets with no k-cup and no l-cap
3.3. (JK)
- Construction of a set of 2^{k-2} points with no k points in convex position
Convex holes in the plane
- k-hole, existence of a 5-hole, nonexistence of a 7-hole in Horton sets
Halving lines
- Halving line, halving segment
- There are always at least n/2 halving lines, for n points in convex position exactly n/2
- Definition h(n) = maximum number of halving lines for n points in convex position in the plane
10.3. (JK)
- Lovász's upper bound h(n) <= O(n^{3/2})
- For each point, in the angle opposite to two consecutive halving segments there is exactly one other halving segment
- Every line intersects at most n/2 halving segments
- Finishing the proof that h(n) <= O(n^{3/2}) using decomposition by n^{1/2} vertical lines
- Geometric graph of halving segments satisfies the following identity: the sum of the number of crossings and binomial coefficients ((d(v)+1)/2 nad 2) is equal to (n/2 choose 2); proof by continuous movement of points from the convex position
- Combining with the crossing lemma we get the upper bound h(n) <= O(n^{4/3})
- Construction for the lower bound h(n) >= Omega(n log n)
- Nivasch's lower bound h(n) >= Omega((n/ln n) e^{(ln 4)^{1/2}(ln n)^{1/2}}):
- Special duality of points and lines, a point p is above a line l if and only if the line p* is above the point l*
- Halving lines correspond to the vertices of the middle level in the dual arrangement
- Idea of the construction of the arrangement by recursive replacement of lines by bundles of lines, a vertex of middle level is replaced by a grid, a new line along the diagonal of the grid is added
17.3. (self-study)
[Ni] or [GGT] 6.2
- Nivasch's construction of the arrangement of lines with many vertices of middle level
- Construction of arrangements L_0, L_1, L_2, ... and point sets V_0, V_1, V_2, ... of middle level
- Verification of correctness of the construction (V_m are indeed middle-level vertices in the arrangement L_m)
- Computation of the numbers of lines and vertices in Nivasch's construction and estimation of h(n)
24.3. (self-study)
Lower envelopes and Davenport–Schinzel sequences
[M] 7.1, 7.3, [N] 1.4, [P] 1.2, 1.3
- Four questions and connections between them:
- What is the maximum possible complexity of a cell in an arrangement of n segments in the plane?
- What is the maximum possible complexity of a "scene" in an arrangement of n segments visible from a given point?
- What is the maximum possible complexity of the lower envelope of an arrangement of n segments?
- What is the maximum possible complexity of the lower envelope of an arrangement of n graphs of continuous functions, every pair of which intersect in at most s points?
- Davenport–Schinzel sequence of order s over an n-element alphabet, maximum length lambda_s(n)
- lambda_1(n)=n, lambda_2(n)>=2n-1
- lambda_2(n)<=2n-1 (proof as exercise)
- rough upper bound lambda_s(n) <= O(sn^2) (proof as exercise)
- lambda_3(n)<=2n ln(n) + 3n
- known bounds on lambda_s(n)
- Ackermann function A(n) and the hierarchy A_k(n), inverse Ackermann function alpha(n) and the hierarchy alpha_k(n), various definitions
31.3. (self-study)
[M] 7.2
- sigma(n) = maximum complexity of the lower envelope of n segments in the plane
- Theorem: sigma(n) grows superlinearly. Shor's construction — S_1(m) is a fan of size m, S_k(2) is created by splitting S_{k-1}(2), general induction step for constructing S_k(m), complexity of the lower envelope of S_k(m) is at least (k/2)*number of segments in S_k(m)
7.4. (self-study)
[M] 7.4
- upper bounds on lambda_3(n): m-decomposable sequence, Psi(m,n) = maximum length of an m-decomposable DS-sequence of order 3 over an n-element alphabet
- lambda_3(n) = Psi(2n-1,n), that is, every DS-sequence of order 3 over an n-element alphabet is (2n-1)-decomposable
- main recursion for Psi(m,n): if m,n,R >= 1, m<= R, m = m_1 + m_2 + ... + m_R, m_i >= 0, then there is a partition n = n_1 + n_2 + ... + n_R + n* such that Psi(m,n) <= 4m +4n* + Psi(R,n*) + sum Psi(m_i,n_i)
- Corollary 1: Psi(m,n) <= 4m log(m) + 6n
- Corollary 2: Psi(m,n) <= 8m log*(m) + 10n
- Corollary k: Psi(m,n) <= 4km alpha_{k+1}(m) + (4k+2)n, finally we choose k = alpha(n)
14.4. (self-study)
Intersection patterns of convex sets
[M] 8.1, 8.2
- recalling the statements of Helly's, Carathéodory's and Radon's theorem
- fractional Helly's theorem
- colorful Carathéodory's theorem
21.4. (self-study)
[M] 8.3
- Tverberg's theorem, variant for convex cones
- colored Tverberg's theorem (only statement)
28.4. (self-study)
Geometric selection theorems
[M] 9.1, 9.2
- First selection lemma, two proofs
- for n points in general position we can require a common point in the interiors of the simplices
- Second selection lemma (statement)
5.5. (self-study)
[M] 9.2
- proof of the second selection lemma
- Erdős–Simonovits theorem for hypergraphs
12.5. (self-study)
[M] 9.3
- Order type of a point set (or a sequence of points)
- Same-type lemma
- Positive fraction Erdős–Szekeres theorem
19.5. (optional self-study)
[S], [HNPT] Theorem 2.4 + Proof of Theorem 1.3
- Suk's upper bound 2^{n+o(n)} in the Erdős–Szekeres theorem, more precise analysis of the proof and computation of o(n) (by Holmsen et al.)