Lectures on Discrete Geometry

1 Convexity.- 1.1 Linear and Affine Subspaces, General Position.- 1.2 Convex Sets, Convex Combinations, Separation.- 1.3 Radon’s Lemma and Helly’s Theorem.- 1.4 Centerpoint and Harn Sandwich.- 2 Lattices and Minkowski’s Theorem.- 2.1 Minkowski’s Theorem.- 2.2 General Lattices.- 2.3 An Application in Number Theory.- 3 Convex Independent Subsets.- 3.1 The Erd?s-Szekeres Theorem.- 3.2 Horton Sets.- 4 Incidence Problems.- 4.1 Formulation.- 4.2 Lower Bounds: Incidences and Unit Distances.- 4.3 Point-Line Incidences via Crossing Numbers.- 4.4 Distinct Distances via Crossing Numbers.- 4.5 Point-Line Incidences via Cuttings.- 4.6 A Weaker Cutting Lemma.- 4.7 The Cutting Lemma: A Tight Bound.- 5 Convex Polytopes.- 5.1 Geometric Duality.- 5.2 H-Polytopes and V-Polytopes.- 5.3 Faces of a Convex Polytope.- 5.4 Many Faces: The Cyclic Polytopes.- 5.5 The Upper Bound Theorem.- 5.6 The Gale Transform.- 5.7 Voronoi Diagrams.- 6 Number of Faces in Arrangements.- 6.1 Arrangements of Hyperplanes.- 6.2 Arrangements of Other Geometric Objects.- 6.3 Number of Vertices of Level at Most k.- 6.4 The Zone Theorem.- 6.5 The Cutting Lemma Revisited.- 7 Lower Envelopes.- 7.1 Segments and Davenport-Schinzel Sequences.- 7.2 Segments: Superlinear Complexity of the Lower Envelope.- 7.3 More on Davenport-Schinzel Sequences.- 7.4 Towards the Tight Upper Bound for Segments.- 7.5 Up to Higher Dimension: Triangles in Space.- 7.6 Curves in the Plane.- 7.7 Algebraic Surface Patches.- 8 Intersection Patterns of Convex Sets.- 8.1 The Fractional Helly Theorem.- 8.2 The Colorful Carathéodory Theorem.- 8.3 Tverberg’s Theorem.- 9 Geometric Selection Theorems.- 9.1 A Point in Many Simplices: The First Selection Lemma.- 9.2 The Second Selection Lemma.- 9.3 Order Types and the Same-Type Lemma.- 9.4 A Hypergraph Regularity Lemma.- 9.5 A Positive-Fraction Selection Lemma.- 10 Transversals and Epsilon Nets.- 10.1 General Preliminaries: Transversals and Matchings.- 10.2 Epsilon Nets and VC-Dimension.- 10.3 Bounding theVC-Dimension and Applications.- 10.4 Weak Epsilon Nets for Convex Sets.- 10.5 The Hadwiger-Debrunner (p, q)-Problem.- 10.6 A (p, q)-Theorem for Hyperplane Transversals.- 11 Attempts to Count k-Sets.- 11.1 Definitions and First Estimates.- 11.2 Sets with Many Halving Edges.- 11.3 The Lovász Lemma and Upper Bounds in All Dimensions.- 11.4 A Better Upper Bound in the Plane.- 12 Two Applications of High-Dimensional Polytopes.- 12.1 The Weak Perfect Graph Conjecture.- 12.2 The Brunn-Minkowski Inequality.- 12.3 Sorting Partially Ordered Sets.- 13 Volumes in High Dimension.- 13.1 Volumes, Paradoxes of High Dimension, and Nets.- 13.2 Hardness of Volume Approximation.- 13.3 Constructing Polytopes of Large Volume.- 13.4 Approximating Convex Bodies by Ellipsoids.- 14 Measure Concentration and Almost Spherical Sections.- 14.1 Measure Concentration on the Sphere.- 14.2 Isoperimetric Inequalities and More on Concentration.- 14.3 Concentration of Lipschitz Functions.- 14.4 Almost Spherical Sections:The First Steps.- 14.5 Many Faces of Symmetric Polytopes.- 14.6 Dvoretzky’s Theorem.- 15 Embedding Finite Metric Spaces into Normed Spaces.- 15.1 Introduction: Approximate Embeddings.- 15.2 The Johnson-Lindenstrauss Flattening Lemma.- 15.3 Lower Bounds By Counting.- 15.4 A Lower Bound for the Hamming Cube.- 15.5 A Tight Lower Bound via Expanders.- 15.6 Upper Bounds for ??-Embeddings.- 15.7 Upper Bounds for Euclidean Embeddings.- What Was It About? An Informal Summary.- Hints to Selected Exercises.