Winter Semester 2013/2014

Arnau Padrol, Raman Sanyal, Günter M. Ziegler It was perfect, it was rounded, symmetrical, complete, colossal!

News

• No seminar on 21.1.2014.

• No seminar on 17.12.2013.

• No seminar on 10.12.2013.

• No seminar on 12.11.2013.

• First (organizational) meeting is Tuesday, October 15, at 14:00 in the Seminar room in Arnimallee 2. Topics will be assigned there.

• There will be ONLY one meeting per week (currently Tuesdays 14-16)!

When and where

Tuesday, 14:00-16:00, Arnimallee 2 (Villa), Seminar room.
(Note that the seminar is only once a week, even if the Vorlesungsverzeichnis shows two time slots.)

What

Runde Sachen are very appealing objects and the notion of roundness is very figurative. Mathematically, however, this is very difficult to grasp and in fact there are many different notions of roundness. The goal is to explore some of the central versions of `roundness' from a convex-geometric and from a discrete-geometric perspective. In particular, we will see the interdependence of geometry and combinatorics. This is the central theme of the project A3 in the new Sonderforschungsbereich 'Discretization in Geometry and Dynamics'. The seminar builds a bridge between fundamental and classical results and ongoing research. Some topics are more challenging than others. A solid background in discrete geometry (e.g. Discrete Geometry I and/or II) is advised but no specialized knowledge is required.

A selection of topics for the seminar is this.
• A convex body is considered to be round if it is `close' to a ball. A classical result of Löwner and John states that, up to an affine transformation, every d-dimensional convex body can be sandwiched between the unit ball and the d-th dilate of the unit ball. In particular, the circumscribed ball is uniquely determined by unit `points of contact'. This has important consequences for (linear) optimization: the ellipsoid method, based on the existence of Löwner-John ellipsoids, is a polynomial-time algorithm for solving linear programms.
• For centrally-symmetric convex bodies, the dilation factor for the Löwner-John ellipsoid can be decreased to sqrt(d). Neighborliness for centrally-symmetric polytopes measures how similar it is to the facial structure of a crosspolytope. It can be shown that Löwner-John-round centrally-symmetric polytopes cannot be very neighborly. Similarly, Löwner-John roundness implies that centrally-symmetric polytopes cannot have simultaneously few vertices and few facets.
• If balls are most round objects, what are the objects at the other end of the spectrum? Among centrally-symmetric convex bodies, seems that these should be cubes and crosspolytopes. This can be measured by the Mahler volume which is conjecturally minimized by cubes. Any c.s. polytope that is rounder in this sense will need more faces. This discrete counterpart is known as the 3^d-conjecture which states that every centrally-symmetric d-polytope has to have at least as many non-empty faces as the d-cube.
• Balls are exactly the solutions to the isoperimetric problem: Balls minimize surface area for prescribed volume. The isoperiemtric quotient measures the deviation from the ball. Lindelöf showed that the isoperiemtric quotient for polytopes is minimized at polytopes circumscribed to the unit ball. Gruber studied polytopes on n facets that attain the minimium. This raises the question as to which combinatorial types of polytopes can occur and, weaker, can be circumscribed to a ball.
• The isoperimetric problem can be treated by Steiner symmetrization which replaces a convex body by one that is symmetric with respect to a chosen direction. Most notably, Steiner symmetrization retains volume while reducing surface area. Thus, Steiner symmetrization makes objects `rounder' in some sense. A discrete isoperimetric problem could relate the combinatorial complexity of a triangulated ball to that of its boundary. What would be a discrete analog of Steiner symmetrization? Shifting operations from enumerative combinatorics could be the right notion.
• Every combinatorial type of a 3-dimenesional polytope can be realized with edges tangent to the unit sphere. Surprisingly, this remains true if the sphere is replaced by a smooth and strictly convex body. This is a 3-dimensional phenomenon: in all dimensions d ≥ 4 there is a polytope that cannot be realized with all k-faces tangent to the unit sphere.

List of topics

Löwner–John roundness

When Who What References
22.10.2013 Thomas Stollin
Löwner–John ellipsoids.
A convex body is considered to be round if it is `close' to a ball. A classical result of Löwner and John states that, up to an affine transformation, every d-dimensional convex body can be sandwiched between the unit ball and the d-th dilate of the unit ball. In particular, the circumscribed ball is uniquely determined by unit `points of contact'. For centrally-symmetric convex bodies, the dilation factor for the Löwner-John ellipsoid can be decreased to sqrt(d).
29.10.2013 Olaf Parczyk / Martin Skrodzki
The ellipsoid method.
The ellipsoid method is a polynomial-time algorithm for solving linear programms. It proceeds by iteratively approximating a convex polyhedron by smaller and smaller ellipsoids and it is based on the existence of Löwner-John ellipsoids. Although this algorithm is not used in practice, it is an important theoretical tool.
5.11.2013 Olaf Parczyk / Martin Skrodzki
The ellipsoid method with a simplex.
One can mimic the strategy of the ellipsoid method with a simplex, obtaining a new algorithm for linear programming.

Centrally-symmetric convex bodies

When Who What References
19.11.2013 Christina Schulz
Neighborliness of centrally-symmetric polytopes.
Neighborliness for centrally-symmetric polytopes measures how similar it is to the facial structure of a crosspolytope. Löwner-John-round centrally-symmetric polytopes cannot be very neighborly. Indeed, if k(d,n) denotes the largest integer k such that there exists a k-neighborly centrally symmetric d-polytope with 2(n+d) vertices, then k(d,n)= Θ(d/(1 + log((d + n)/d))).
14.1.2014 Francesco Grande
Random centrally symmetric polytopes.
There are several ways to consider a random centrally symmetric polytope. One of them is a random projection of an n-dimensional crosspolytope onto R^d. When n is large and proportional to d, then these random centrally symmetric polytopes present some neighborliness with probability close to one.

Round vs Pointy

When Who What References
26.11.2013 Michael Brückner
Mahler volume.
The Mahler conjecture is a long standing open problem in convex geometry. The Mahler volume M(B) of a centrally symmetric convex body B is M(B)=vol(B)vol(B*), where B* is the polar of B. Then the conjecture states that the minimum possible Mahler volume is attained by cubes and crosspolytopes.
Kalai's 3^d conjecture.
In 1989 Gil Kalai conjectured that every d-dimensional centrally symmetric polytope has at least 3^d nonempty faces. Although it is known that the conjecture is true for d≤4 and for simplicial polytopes (thanks to Bárány and Lovász's result) it remains open for the general case.
7.1.2013 Marie-Sophie Litz
Simple centrally symmetric polytopes.★
Using topological methods, one can prove that any simple centrally symmetric d-polytope must have at least 2^d vertices.

Faces tangent to the sphere

When Who What References
28.01.2014 Hao Chen
How to cage an egg.
Every 3-dimensional polytope can be realized with all its edges tangent to a sphere. This surprising result remains true if a sphere is replaced for any convex body in R^3 who is nice enough (smooth strictly convex body). If, in addition, the boundary of C satisfies stronger smoothness conditions, the space of all such polytopes Q forms a six-dimensional manifold.
28.01.2014 Hao Chen
Hypereggs cannot be caged.
This phenomenon of 3-polytopes (existence of realizations with edges tangent to a sphere) is very special since for every pair (m,d)!=(1,3) there is a d-polytope that cannot be realized with all its m-faces tangent to a sphere.
4.02.2014 Philip Brinkmann
Inscribability and Delaunay subdivisions.★
Which combinatorial types of polytopes can be realized with all the vertices on the sphere? Via a stereographic projection, this question is equivalent to the study of the possible combinatorial types of Delaunay subdivisions.

Isoperimetric quotients

When Who What References
11.02.2014 Christoph Peters
Circumscribed polytopes.
The isoperimetric quotient of a convex body C is S(C)^d/V(C)^(d-1), where S and V represent the surface are and the volume, respectively. A classical result by Lindelöf states that among all polytopes with fixed facet normals, circumscribed polytopes attain the minimum isoperimetric quotient.

Topics marked with a ★ will be offered depending on the demand.