A03
Geometric Constraints for Polytopes

Exploring the Subtle Interplay of Geometry and Combinatorics

Polytopes are solid bodies bounded by flat facets. Alternatively, they can be described as the convex hull of their vertices. Thus a polytope can be presented by information on two aspects, a geometric one: "What are the coordinates of the vertices" and a combinatorial one: "Which vertex is incident to which face". There are many interrelations between these two levels: Combinatorial requirements enforce restrictions on the geometry, and vice versa. A03 studies aspects of this interplay.

Mission-

Polytopes, the convex hulls of finitely many vertices, are a subject of mathematical study since antiquity. The Platonic solids were the culmination point of antique Greek mathematics: They are polytopes admitting a particularly high type of symmetry. While the cube, the tetrahedron and the octahedron can be realized with full symmetry using integer coordinates, this is impossible for the icosahedron and the dodecahedron. Realizing them with full symmetry requires the use of a sqrt(5) in the coordinate field. Here two combinatorial requirements, namely the type of a polytope (being a dodecahedron) and the requirement to realize it symmetrically, create structural constraints on the geometric realization of the polytope (the coordinates cannot be rational). Starting in dimension four there are combinatorial types of polytopes that (even without symmetry requirements) cannot be realized with integers as coordinates. Another characteristic property shared by all the Platonic solids is that they can be represented with all their vertices on a sphere. Not every polytope has such a realization, and it is still a challenging question to decide which polytopes do.

It is a central topic in research project A03 to study the various types of interplay of combinatorial properties of polytopes (face lattice, symmetry, etc) and their geometric properties (coordinates, shapes, etc). Questions like:

  • "Which integer realizable polytope with n vertices requires the largest integer coordinates?",
  • "What is the most compact way to describe a specific realization of a polytope?",
  • "Does the 'roundness' of a polytope have influence on its combinatorial type?",
  • "Which combinatorial types of polytopes can be inscribed in a sphere?"

are of great interest and still widely open. It is even necessary to define the right concepts of 'complexity' and 'roundness' to speak about these problems in proper mathematical terms. Attacking these fundamental problems is at the core of A03.

Scientific Details+

The focus of this project is on the interaction between the combinatorics of convex polytopes (face numbers, face lattice, combinatorial type, graph, diameter of the graph) and geometric properties (such as inscribability or various notions of "roundness").

The interaction between combinatorics and geometry is in both directions; thus the two parallel strands of this project are to treat the combinatorial variety of polytopes under geometric restrictions (Geometry → Combinatorics) and, in the other direction, the geometric construction of polytopes with specific combinatorial qualities (Combinatorics → Geometry). Each direction is fueled by selected open problems and conjectures. Both the selection of these problems and the research strategies are guided by Discrete Differential Geometry intuition, e.g., on discrete notions of curvature and on discrete integrable systems.

Geometry → Combinatorics

Roundness, f -vectors, and diameter. Major research questions in polytope theory, such as the f -vector problem and the Hirsch conjecture, concern purely combinatorial parameters such as face numbers and graph-theoretic diameter. Nevertheless, deep genuinely geometric insights and constructions have led to major results, such as the so-called g-Theorem and the first counterexamples to the Hirsch conjecture.

There are various, partially conflicting, types of intuition that lead one to consider/treat polytopes as being "round": In particular, we focus on round polytopes as studied by Borgwardt (facets tangent to sphere), as suggested by Löwner-John and used by Barvinok (bounded in-radius/circum-radius ratio), and discrete notions of local curvature (that, for example, restrict volumes of normal cones or dihedral angles). These notions are to be further explored and compared, as intuition suggests that forced "roundness" should substantially constrain the combinatorics. We investigate both face numbers (f-vector) and diameter bounds with respect to various notions of "roundness."

In order to evaluate the influence of geometry on the combinatorics, we will thus study to what extent geometry restricts combinatorics. That is, do "round" polytopes have restricted f-vectors? Can discrete curvature conditions be used to bound diameters?

Projective uniqueness and combinatorial types. A polytope P is projectively unique if any combinatorially equivalent polytope is an image of P under an (admissible) projective transformation. Projectively unique polytopes - and more generally, polytopes with low-dimensional realization spaces - are hard to come by. A long-standing conjecture of Shephard and McMullen claims that there are only finitely many such polytopes in fixed dimension. Projective uniqueness exhibits a particular local-to-global structure in that local geometric choices force the global geometry via the combinatorics. This phenomenon, which borders real algebraic geometry as well as classical incidence geometry and discrete integrability, is poorly understood. We expect that modern construction techniques for polytopes combined with intuition and techniques from discrete integrability will lead to new examples and eventually a (negative) resolution of the Shephard-McMullen conjecture in all dimensions d>3. (In the moment, we know that it is false for d>68).

Combinatorics → Geometry

Coding and complexity. We  investigate the correlation between the combinatorial and coding complexity of polytopes. Again, there is no canonical choice of measuring the coding complexity. Apart from the (traditional) bit-complexity of rational/integral vertex coordinates we will focus on Euclidean complexity, i.e., the Euclidean length of the ordered collection of vertices considered as a single integer vector of size n x d. This perspective enables the use of lattice-theoretic methods (shortest lattice vectors) and methods from real algebraic geometry. For the class of 3-dimensional polytopes, the best bounds on the bit-complexity so far have been obtained via equilibrium-stress networks. We are trying to substantially sharpen these methods and bounds.

Combinatorial complexity measures for algebraic realizations. Starting in dimension 4 there are polytopes that do cannot be realized with rational vertex coordinates. For such special polytopes a different measure of coding complexity is needed. We are thus conducting a thorough study using Lovász' notion of "real number boxes" [Lov86a], that is, oracles for algebraic numbers based on minimal polynomials. In this setting, the coding complexity is given by bit complexity of the minimal polynomial. We  study both edge-tangent 3-polytopes and non-rational 4-polytopes in this set-up. These investigations are foundational, and will hopefully open up a whole new area of study.

Publications+

Papers
Reflection groups, arrangements, and invariant real varieties

Authors: Friedl, Tobias and Riener, Cordian and Sanyal, Raman
Note: preprint
Date: Feb 2016

A universality theorem for projectively unique polytopes and a conjecture of Shephard

Authors: Adiprasito, Karim and Padrol, Arnau
Journal: Israel J. Math., 211:239-255
Date: 2016
Download: arXiv

Simple polytopes without small separators

Authors: Loiskekoski, Lauri and Ziegler, Günter M.
Note: Preprint
Date: Oct 2015
Download: arXiv

Hyperplane mass partitions via relative Equivariant Obstruction Theory

Authors: Blagojevic, Pavle V. M. and Frick, Florian and Haase, Albert and Ziegler, Günter M.
Note: preprint
Date: Sep 2015
Download: arXiv

Realizability and inscribability for some simplicial spheres and matroid polytopes

Author: Firsching, Moritz
Note: Preprint
Date: Aug 2015
Download: arXiv

Scribability Problems for Polytopes

Authors: Chen, Hao and Padrol, Arnau
Note: Preprint
Date: Aug 2015
Download: arXiv

A flag vector of a 3-sphere that is not the flag vector of a 4-polytope

Authors: Brinkmann, Philip and Ziegler, Günter M.
Note: Preprint
Date: Jun 2015
Download: arXiv

The universality theorem for neighborly polytopes

Authors: Adiprasito, Karim and Padrol, Arnau
Journal: Combinatorica
Note: accepted, preprint at arxiv
Date: Feb 2015
Download: arXiv

Combinatorial positivity of translation-invariant valuations and a discrete Hadwiger theorem

Authors: Jochemko, Katharina and Sanyal, Raman
Note: preprint
Date: 2015

Dyck path triangulations and extendability

Authors: Ceballos, Cesar and Padrol, Arnau and Sarmiento, Camilo
Journal: Journal of Combinatorial Theory, Series A, 131(0):187-208
Date: 2015
Download: external arXiv

Enumeration of neighborly polytopes and oriented matroids

Authors: Miyata, Hiroyuki and Padrol, Arnau
Journal: Experimental Math., 24:489-505
Date: 2015
DOI: 10.1080/10586458.2015.1015084
Download: external arXiv

Many projectively unique polytopes

Author: Karim Adiprasito, Günter M. Ziegler
Journal: Inventiones math., 199:581-652
Date: 2015
DOI: 10.1007/s00222-014-0519-y
Download: external arXiv

The degree of point configurations: Ehrhart theory, Tverberg points and almost neighborly polytopes

Authors: Nill, Benjamin and Padrol, Arnau
Journal: European Journal of Combinatorics (special issue in honour of Michel Las Vergnas), 50:159–179
Date: 2015
Download: arXiv

Universality theorems for inscribed polytopes and Delaunay triangulations

Authors: Adiprasito, Karim and Padrol, Arnau and Theran, Louis
Journal: Discrete Comput. Geom., 54:412-431
Date: 2015
Download: arXiv

Theta rank, levelness, and matroid minors

Authors: Grande, Francesco and Sanyal, Raman
Note: preprint
Date: Aug 2014
Download: arXiv

Relative Stanley-Reisner theory and Upper Bound Theorems for Minkowski sums

Authors: Adiprasito, Karim and Sanyal, Raman
Note: preprint
Date: May 2014
Download: arXiv

Polygons as slices of higher-dimensional polytopes

Authors: Padrol, Arnau and Pfeifle, Julian
Note: Preprint
Date: Apr 2014
Download: arXiv

Delaunay triangulations with disconnected realization spaces

Authors: Padrol, Arnau and Theran, Louis
In Proceedings: 30th Annual Symposium on Computational Geometry, SOCG'14, Kyoto, Japan, June 08 - 11, 2014, {ACM}
Date: 2014
DOI: 10.1145/2582112.2582119
ISBN: 978-1-4503-2594-3
Download: external

Many neighborly inscribed polytopes and Delaunay triangulations

Authors: Gonska, Bernd and Padrol, Arnau
Journal: DMTCS Proceedings, pages 161-168
In Proceedings: 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
Date: 2014
Download: external

Tight and non-tight topological Tverberg type theorems

Authors: Blagojevic, Pavle V. M. and Frick, Florian and Matschke, Benjamin and Ziegler, Günter M.
Journal: Oberwolfach Reports, 11(3):2284-2287
Date: 2014
Download: internal

Tverberg plus constraints

Authors: Blagojevic, Pavle V. M. and Frick, Florian and Ziegler, Günter M.
Journal: Bulletin of the London Mathematical Society, 46:953-967
Note: Extended Abstract: Oberwolfach Reports, 11(1):14-16, 2014
Date: 2014
DOI: 10.1112/blms/bdu049
Download: external arXiv

Many neighborly polytopes and oriented matroids.

Author: Padrol, Arnau
Journal: Discrete Comput. Geom., 50(4):865--902
Date: Dec 2013
DOI: 10.1007/s00454-013-9544-7
Download: external arXiv

Neighborly inscribed polytopes and Delaunay triangulations

Authors: Gonska, Bernd and Padrol, Arnau
Note: Preprint
Date: Aug 2013
Download: arXiv

On highly regular embeddings

Authors: Blagojevic, Pavle V. M. and Lück, Wolfgang and Ziegler, Günter M.
Note: Preprint, 19 pages; Transactions Amer. Math. Soc. to appear, Extended Abstract: in Proc. "Combinatorial Methods in Topology and Algebra'' (CoMeTa), Cortona
Date: May 2013
Download: internal arXiv

Inscribable stacked polytopes

Authors: Gonska, Bernd and Ziegler, Günter M.
Journal: Adv. Geom., 13:723-740
Date: 2013
Download: arXiv


Team+

Prof. Dr. Günter M. Ziegler   +

Projects: A02, A03, CaP
University: FU Berlin
E-Mail: ziegler[at]math.fu-berlin.de
Website: http://page.mi.fu-berlin.de/gmziegler/


Prof. Dr. Raman Sanyal   +

Prof. Dr. Carsten Lange   +

Projects: A03
University: TU München
E-Mail: carsten.lange[at]ma.tum.de


Philip Brinkmann   +

Projects: A03
University: FU Berlin
E-Mail: pbrinkmann[at]zedat.fu-berlin.de


Dr. Moritz Firsching   +

Projects: A03
University: FU Berlin
E-Mail: firsching[at]math.fu-berlin.de


Tobias Friedel   +

Projects: A03
University: FU Berlin
E-Mail: tfriedel[at]zedat.fu-berlin.de


Lauri Loiskekoski   +

Projects: A03
University: FU Berlin
E-Mail: loiskekoski[at]zedat.fu-berlin.de


Hannah Schäfer Sjöberg   +

Projects: A03
University: FU Berlin