Combinatorial and Computational Geometry 2 (2022/2023)

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:
  • Chapter 3 in the lecture notes by Jiří Matoušek: a PS file for two-page printing, a PDF file for readers and tablets.
  • [M] Chapter 3
  • [S] for interested readers: Andrew Suk, On the Erdos-Szekeres convex polygon problem (journal version), [HNPT] A. Holmsen et al., Two extensions of the Erdos-Szekeres problem
• Halving lines:
  • [M] Parts of Chapter 11
  • [GGT] Lecture notes, two missing proofs
  • [Ni] Gabriel Nivasch, An Improved, Simple Construction of Many Halving Edges
• Lower envelopes and Davenport–Schinzel sequences:
  • [M] Chapter 7 (sections 7.1-7.4)
  • [N] for interested readers: Gabriel Nivasch, Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations (journal version)
  • [P] for interested readers: Seth Pettie, Sharp Bounds on Davenport-Schinzel Sequences of Every Order (journal version)
• Intersection patterns of convex sets and geometric selection theorems:
  • [M] Chapters 8, 9
• 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)

• 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

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

[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

• First selection theorem

21. 4. (MT)

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

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

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

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