《离散几何讲义(英文影印版)》旨在为读者提供一本学习离散几何的引入教程，主要内容包括凸集，凸多面体和超平面的安排；几何构型的组合复杂性；交叉模型和凸集的截面；几何ramsey型结果；有限几何空间嵌入到赋范空间等。在好多应用领域，都可以涉及到这里的很多结果和方法。目次:凸性；点格和minkowski定理；凸独立子集；事件问题；凸多面体；下包络；凸集的相交模型；几何选择定理；计数k-集；高维多面体的两个应用；高维中的体积；测度集聚和球面集；嵌入有限度量空间到赋范空间。
读者对象：数学专业的本科生、研究生和相关领域的科研人员。
preface
notation and terminology
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 ham 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 erdos-szekeres theorem
3.2 horton sets
4 incidence problems
preface
notation and terminology
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 ham 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 erdos-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 the vc-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 lovfisz 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-lindenstranss 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 ~oo-embeddings
15.7 upper bounds for euclidean embeddings
what was it about? an informal summary
hints to selected exercises
bibliography
index
书单推荐
