Kombinatorická a výpočetní geometrie 2 (2024/2025)
Combinatorial and Computational Geometry 2 (2024/2025)
Jan Kynčl, Martin Tancer, KAM
Stránka v SISu
Entry in SIS
Přednáška: středa 9:00 v S11
Lecture: Wednesdays 9:00 in S11
Cvičení: konají se ve středu v 15:40 v S10 podle rozvrhu na stránce cvičení.
Exercise sessions: Wednesdays 15:40 S10 according to the schedule on the exercise webpage.
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:
19.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
26.2. (JK)
- Konstrukce množin bez k-misky a l-čepice
- 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ě
5.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řížících se dvojic 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}}):
- Dualita bodů a nesvislých přímek, bod p je nad přímkou l právě tehdy, když přímka D(p) je nad bodem D(l)
- Půlící přímky odpovídají vrcholům prostřední úrovně v duálním arrangementu
12.3. (JK)
[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ě. 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
- 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)
19. 3. a pozdeji
Pro prednasky od (MT) budu psat zapis pouze v anglictine.
Topics of lectures:
19.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
26.2. (JK)
- Construction of point sets with no k-cup and no l-cap
- 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 general position in the plane
5.3. (JK)
- Lovász's upper bound h(n) <= O(n^{3/2})
- Around each point in the wedge opposite to two consecutive halving segments there is exactly one halving segment
- Every generic line intersects at most n/2 halving segments
- Finishing the proof of the bound h(n) <= O(n^{3/2}) using a decomposition by n^{1/2} vertical lines into parallel strips
- Geometric graph of halving segments satisfies the following identity: the sum of the number of crossing pairs and binomial coefficients ((d(v)+1)/2 choose 2) is equal to (n/2 choose 2); proof by continuous movement of points from 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}}):
- Duality of points and non-vertical lines, a point p is above a line l if and only if the line D(p) is above the point D(l)
- Halving lines correspond to vertices of middle level in the dual arrangement
12.3. (JK)
[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. 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
- 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)
19. 3. (MT)
[M] 8.1, 8.2, 8.3
Intersection patterns of convex sets and geometric selection theorems
- Fractional Helly theorem
- So far proved with beta = alpha/(d+1)
- Proof uses lexicographically minimal points and double counting
- Colorful Carathéodory theorem
- Proof by contradiction closest simplex to the origin viloating the condition may be done closer
- Tverberg's theorem
- So far statement only (proof next time).
26. 3. (MT)
[M] 8.3, 9.1, 9.2
- Proof of Tverberg's theorem (the proof in [M] is slightly different).
- Sarkaria-Onn transform
- Sarkaria-Onn lemma (and its proof)
- Proof of Tverberg's theorem via colorful Carathéodory and Sarkaria-Onn lemma
- First selection theorem (with a proof)
- Second selection theorem (without a proof)
2. 4. (MT)
- Pach's selection theorem (without a proof)
- Simplicial complexes
- Basic definitions and examples: abstract simplicial complex, vertices and faces, dimension
- Nerve of a set system, d-representable complex
- d-collapsible complexes
- Basic definitions and examples: free face, elementary d-collapse, d-collapsible complex
- d-collapsibility is preserved when taking an induced subcomplex (without a proof).
- Wegner's theorem: Every d-representable complex is d-collapsible
- Lemma: It is possible to perform an elementary d-collapse on a d-representable complex while preserving d-representability.
- Proof that Wegner's theorem follows from the lemma by induction.
- Proof of the lemma: So far identified a free face for the elementary d-collapse and proved that it is free and of dimension less than d.
9. 4. (MT)
- Wegner's theorem: Finishing the proof of the lemma: After the collapse induced by the free face we get a representable complex.
- Lemma on modification of collapses (without a proof so far).
- Optimal fractional Helly theorem
- Statement recalled.
- A key proposition (nontrivial restatement of the fractional Helly theorem; it has not been proved so far that the optimal fractional Helly follows from this).
- Remark: The key proposition is optimal
- Proof of the key proposition: Constructed certain hypergraphs and vector spaces according to the collapses. Stated three properties that imply the optional fractional Helly theorem and proved the first property. (The other two will be proved at the next lecture.)