Hjem

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.