Combinatorial and Computational Geometry 2 (2022/2023)
Martin Tancer a
Pavel Valtr
Záznam v SISu
Lecture: Friday 9:00 in S11
Exercise sessions: after the lecture at 10:40 v S5 according to the schedule on the exercise webpage.
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 (possibly shelling polytopes and the upper bound theorem).
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:
- Shellability, h-vectors, upper bound theorem
- [Z] G. M. Ziegler, Lectures on Polytopes (Chapter 8)
Topics of lectures:
17.2.,24.2.,3.3. (PV)
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
- 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,
Horton's construction of a set of size 2^k with no 7-hole, Horton set, nonexistence of a 7-hole in Horton sets
Halving lines
- Halving line, halving segment, two examples (2n points in convex position, vertices and the center of a regular 2n-1-gon)
- There are always at least n/2 halving lines
- a construction of a set of n points in general position with at least n.logn halving lines (by appropriate "doubling" of points)
31. 3. (MT)
Intersection patterns of convex sets
[M] 8.1, 8.2, 8.3
- fractional Helly's theorem
- colorful Carathéodory's theorem
- Tverberg's theorem (for the moment only statement and a very small bit towards a proof)
14. 4. (MT)
[M] 8.3 (different proof of Tverberg's theorem) 9.1
- Proof of Tverberg's theorem (via Sarkaria-Onn transform)
Geometric selection theorems
21. 4. (MT)
[M] 9.2, 9.5, [Z] 8.1
- Second selection theorem (statement only)
- Pach's selection theorem (statement only)
Shellability of polytopes
- Motivation: induction, Euler-Poincare formula, upper bound theorem
- Polytopal complexes (definitions and examples)
- Shellability of polytopal complexes (definition, examples, remarks)
28. 4. (MT)
[Z] 8.2, 8.3
- Theorem (Bruggesser, Mani): Every polytope is shellable. Proof via line shellings.
- Corollary: there is a shelling of a (boundary of a) polytope starting and finishing in prescribed facets.
- Observation/remark: Only the last facet of shelling meets the previous ones in its whole boundary.
- Corollary: Euler-Poincare formula. The proof uses also a simple inclusion-exclusion formula for reduced Euler characteristic.
h-vectors
- Descritiption of newly added faces in a shelling of simplicial complex.
- Partitionable simplicial complex. (Every shellable simplicial complex is partitionable from the description above.)
5. 5. (MT)
[Z] 8.3, 8.4 (and a small bit of 0)
- h-vector from partition of a partitionable simplicial complex.
- F-polynomial and H-polynomial. F(x) = H(x+1).
- Definition of h-vector for general simplicial complex.
- h-vector can be computed from f-vector and vice versa; for partitionable complex it does not depend on the partition and it is nonnegative.
- Dehn-Sommerville equations (for h-vectors only).
Upper bound theorem
- Cyclic polytope; Gale's eveness criterion (without proof).
- Neighborly polytope. Cyclic polytope is (floor function of) d/2-neighborly.
- Statement of the upper bound theorem (UBT) recalled.
- Perturbation lemma (without proof) that implies that it is sufficient to prove UBT for simplicial polytopes only.
- Lemma on upper bounds of h-vectors.
- Proof of UBT via the lemma, thus it remains to prove the lemma.
12. 5. (MT)
[Z] 8.4
- Finishing the proof of UBT:
- Stars and links of simplicial complexes.
- Shelling of a complex induces shelling of a link.
- Proof of the lemma from the last time using shellings and properties of h-vectors.