离散几何讲义PDF电子书下载

1 Convexity 1

1.1 Linear and Affine Subspaces,General Position 1

1.2 Convex Sets,Convex Combinations,Separation 5

1.3 Radon's Lemma and Helly's Theorem 9

1.4 Centerpoint and Ham Sandwich 14

2 Lattices and Minkowski's Theorem 17

2.1 Minkowski's Theorem 17

2.2 General Lattices 21

2.3 An Application in Number Theory 27

3 Convex Independent Subsets 29

3.1 The Erd？s-Szekeres Theorem 30

3.2 Horton Sets 34

4 Incidence Problems 41

4.1 Formulation 41

4.2 Lower Bounds:Incidences and Unit Distances 51

4.3 Point-Line Incidences via Crossing Numbers 54

4.4 Distinct Distances via Crossing Numbers 59

4.5 Point-Line Incidences via Cuttings 64

4.6 A Weaker Cutting Lemma 70

4.7 The Cutting Lemma:A Tight Bound 73

5 Convex Polytopes 77

5.1 Geometric Duality 78

5.2 H-Polytopes and V-Polytopes 82

5.3 Faces of a Convex Polytope 86

5.4 Many Faces:The Cyclic Polytopes 96

5.5 The Upper Bound Theorem 100

5.6 The Gale Transform 107

5.7 Voronoi Diagrams 115

6 Number of Faces in Arrangements 125

6.1 Arrangements of Hyperplanes 126

6.2 Arrangements of Other Geometric Objects 130

6.3 Number of Vertices of Level at Most k 140

6.4 The Zone Theorem 146

6.5 The Cutting Lemma Revisited 152

7 Lower Envelopes 165

7.1 Segments and Davenport-Schinzel Sequences 165

7.2 Segments:Superlinear Complexity of the Lower Envelope 169

7.3 More on Davenport-Schinzel Sequences 173

7.4 Towards the Tight Upper Bound for Segments 178

7.5 Up to Higher Dimension:Triangles in Space 182

7.6 Curves in the Plane 186

7.7 Algebraic Surface Patches 189

8 Intersection Patterns of Convex Sets 195

8.1 The Fractional Helly Theorem 195

8.2 The Colorful Carathéodory Theorem 198

8.3 Tverberg's Theorem 200

9 Geometric Selection Theorems 207

9.1 A Point in Many Simplices:The First Selection Lemma 207

9.2 The Second Selection Lemma 210

9.3 Order Types and the Same-Type Lemma 215

9.4 A Hypergraph Regularity Lemma 223

9.5 A Positive-Fraction Selection Lemma 228

10 Transversals and Epsilon Nets 231

10.1 General Preliminaries:Transversals and Matchings 231

10.2 Epsilon Nets and VC-Dimension 237

10.3 Bounding the VC-Dimension and Applications 243

10.4 Weak Epsilon Nets for Convex Sets 251

10.5 The Hadwiger-Debrunner(p,q)-Problem 255

10.6 A(p,q)-Theorem for Hyperplane Transversals 259

11 Attempts to Count k-Sets 265

11.1 Definitions and First Estimates 265

11.2 Sets with Many Halving Edges 273

11.3 The Lovász Lemma and Upper Bounds in All Dimensions 277

11.4 A Better Upper Bound in the Plane 283

12 Two Applications of High-Dimensional Polytopes 289

12.1 The Weak Perfect Graph Conjecture 290

12.2 The Brunn-Minkowski Inequality 296

12.3 Sorting Partially Ordered Sets 302

13 Volumes in High Dimension 311

13.1 Volumes,Paradoxes of High Dimension,and Nets 311

13.2 Hardness of Volume Approximation 315

13.3 Constructing Polytopes of Large Volume 322

13.4 Approximating Convex Bodies by Ellipsoids 324

14 Measure Concentration and Almost Spherical Sections 329

14.1 Measure Concentration on the Sphere 330

14.2 Isoperimetric Inequalities and More on Concentration 333

14.3 Concentration of Lipschitz Functions 337

14.4 Almost Spherical Sections:The First Steps 341

14.5 Many Faces of Symmetric Polytopes 347

14.6 Dvoretzky's Theorem 348

15 Embedding Finite Metric Spaces into Normed Spaces 355

15.1 Introduction:Approximate Embeddings 355

15.2 The Johnson-Lindenstrauss Flattening Lemma 358

15.3 Lower Bounds By Counting 362

15.4 A Lower Bound for the Hamming Cube 369

15.5 A Tight Lower Bound via Expanders 373

15.6 Upper Bounds for ？∞-Embeddings 385

15.7 Upper Bounds for Euclidean Embeddings 389

What Was It About?An Informal Summary 401

Hints to Selected Exercises 409

Bibliography 417

Index 459