Abstract. Let K ⊂ Rd be a convex body, i.e., a convex compact set with nonempty interior. Further, let Xn ⊂ K be a set of n points from K. Usually, Xn is either a random sample of n uniform, independent points from K, or Xn=K ⊂ L, where L is a d-dimensional lattice in Rd. In both cases, Kn, the convex hull of Xn is a convex polytope. Starting with J. Sylvester's famous four-point problem in 1864, there has been a lot of research to understand various properties of this polytope, for instance number of vertices, facets, or how well Kn approximates K.
When Xn is a random sample, Kn is called a random polytope. We will determine the expectation of the number of vertices of Kn and of Vol (K \Kn). Recent progress in this area has resulted in central limit theorems and concentration inequalities for random polytopes.
In the proofs methods from convex geometry and probability theory are used. One particularly successful technique is that of Macbeath regions and minimal caps, and the so called economic cap covering theorem. This will be described in detail and its power will be illustrated with several applications.
When Xn comes from a lattice L, Kn is a lattice polytope. The integer convex hull, which is a central object in integer programming, is one instance of such a lattice polytope. We will give bounds on the number of vertices, and the missed volume. A randomized version of the integer convex hull will also be considered. The proof method is again convex geometry, economic cap coverings, and geometry of numbers.
The course will include some other related material, like random 0-1 polytopes, limit shape of convex lattice polygons, and new developments around Sylvester's four point question.
List of contents:
- Macbeath regions, minimal caps, and the floating body,
- The economic cap covering theorem and applications,
- Random polytopes: expectations and limit theorems,
- Sylvester's four point problem,
- The integer convex hull, and its randomised version,
- The number of convex lattice polytopes,
- 0-1 polytopes with many facets.
Zeit: Mi 13-15
Ort: HG G 43
Beginn: 27. Februar
M. Struwe