Convex hulls of random sets have been of a constant interest for those working in probability theory, geometry, and combinatorics. This small workshop aims to reflect a significant recent progress in the area and bring together the experts working on the subject.
The workshop will start with the lecture overviewing the field to be followed by regular research talks. The event is organized by Vladislav Vysotsky, who should be contacted for any questions or inquiries.
Update: The slides are now available, just click on the titles.
Schedule
10:00 – 11:30: Matthias Reitzner — Random polytopes: limit theorems
11:40 – 12:40: Vladislav Vysotsky — Large deviations of convex hulls of planar random walks
Lunch
14:10 – 15:10: Imre Barany — Random points and lattice points in convex bodies
15:10 – 16:10: Andrew Wade — Convex hulls of planar random walks
Coffee break
16:40 – 17:40: Zakhar Kabluchko — Convex hulls of random walks and Weyl chambers
Abstracts
Matthias Reitzner — Random polytopes: limit theorems
Abstract: Let eta be the points of a Poisson point process of intensity s on a convex body K and denote by K_s the convex hull of these points. We are interested in properties of K_s as s tends to infinity: expectations, variances, limit theorems and large deviations for functionals of K_s.
Vladislav Vysotsky — Large deviations of convex hulls of planar random walks
Abstract: We give logarithmic asymptotic bounds for large deviations probabilities for perimeter of the convex hull of a planar random walk. These bounds are sharp for a wide class of distributions of increments that includes Gaussian distributions and shifted or linearly transformed rotationally invariant distributions. For such random walks, large deviations of the perimeter are attained by the trajectories that asymptotically align into line segments. These results on the perimeter are easily extended to mean width of convex hulls of random walks in higher dimensions. Our method also allows to find the logarithmic asymptotics of large deviations probabilities for area of the convex hull of planar random walks with rotationally invariant distributions of increments. This is a joint work with Arseniy Akopyan (IST Austria).
Imre Barany — Random points and lattice points in convex bodies
Abstract: Assume K is a convex body in R^d and X is a (large) finite subset of K. How many convex polytopes are there whose vertices belong to X? Is there a typical shape of such polytopes? How well does the maximal such polytope (which is actually the convex hull of X) approximate K? In this lecture I will talk about these questions mainly in two cases. The first is when X is a random sample of n uniform, independent points from K. In this case motivation comes from Sylvester’s famous four-point problem and from the theory of random polytopes. The second case is when X is the set of lattice points contained in K and the questions come from integer programming and geometry of numbers. Surprisingly (or not so surprisingly), the answers in the two cases are rather similar.
Andrew Wade — Convex hulls of planar random walks
Abstract: On each of n unsteady steps, a drunken gardener drops a seed. Once the flowers have bloomed, what is the minimum length of fencing required to enclose the garden? What is its area? I will describe recent work on the convex hull of planar random walk, concerned in particular with the large-n asymptotics of its perimeter length and area. We provide variance asymptotics and distributional limit theorems. Of the four combinations of the two quantities (perimeter and area) in the two regimes (zero drift or non-zero drift for the steps of the walk), one limit is Gaussian; three are not.
This talk is mostly based on joint work with Chang Xu (Strathclyde); I’ll also mention ongoing work with Ostap Hryniv and James McRedmond (Durham).
Zakhar Kabluchko — Convex hulls of random walks and Weyl chambers
Abstract: Consider a d-dimensional random walk S_1, … ,S_n whose increments are i.i.d. random vectors having a centrally symmetric density. We prove a formula for the probability that the convex hull of this random walk contains the origin. This so-called absorption probability is related to the number of Weyl chambers of type B_n intersected by a random linear subspace and to the conic intrinsic volumes of a Weyl chamber. Similar results can be obtained for the convex hull of a random bridge, which uses analogous connections with Weyl chambers of type A_n. This is joint work with Vladislav Vysotsky and Dmitry Zaporozhets.