Random Points and Lattice Points in Convex Bodies

Abstract

"Nachdiplomvorlesung"

Content

Let K be a convex body in R^d, i.e., a convex compact set with nonempty interior. Further, let X_n be a set of n points from K. Usually, X_n is either a random sample of n uniform, independent points from K, or X_n is the intersection of K with L, where L is a d-dimensional lattice in R^d. In both cases, K_n, the convex hull of X_n 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 K_n approximates K. When X_n is a random sample, K_n is called a random polytope. We will determine the expectation of the number of vertices of K_n and of Vol(K\K_n). 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 X_n comes from a lattice L, K_n 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.

Resources