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
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.
Journal: Mathematika, 63:260-271
Note: Preprint at arXiv, November 2015, 12 pages
Date: 2017
Download: arXiv

Colorful simplicial depth, Minkowski sums, and generalized Gale transforms

Authors: Adiprasito, Karim and Brinkmann, Philip and Padrol, Arnau and Paták, Pavel and Patáková, Zuzana and Sanyal, Raman
Journal: International Mathematics Research Notices
Date: 2017
DOI: 10.1093/imrn/rnx184
Download: external arXiv

Combinatorial mixed valuations

Authors: Jochemko, Katharina and Sanyal, Raman
Journal: Advances in Mathematics, 319:630--652
Date: 2017
DOI: 10.1016/j.aim.2017.08.032
Download: external arXiv

Extension complexity and realization spaces of hypersimplices

Authors: Grande, Francesco and Padrol, Arnau and Sanyal, Raman
Journal: Discrete Comput Geom
Date: 2017
DOI: 10.1007/s00454-017-9925-4
Download: external arXiv

Lipschitz polytopes of posets and permutation statistics

Authors: Sanyal, Raman and Stump, Christian
Note: Preprint
Date: 2017
Download: arXiv

Minkowski complexes and convex threshold dimension

Authors: Frick, Florian and Sanyal, Raman
Journal: Journal of Combinatorial Theory, Series A, 151:202--206
Date: 2017
Download: external arXiv

Mixed Ehrhart polynomials

Authors: Haase, Christian and Juhnke-Kubitzke, Martina and Sanyal, Raman and Theobald, Thorsten
Journal: Electron. J. Combin., 24(Issue 1):Paper #P1.10
Date: 2017
Download: external arXiv

On degree sequences of undirected, directed, and bidirected graphs

Authors: Gellert, Laura and Sanyal, Raman
Journal: European Journal of Combinatorics, 64:113--124
Date: 2017
Download: external arXiv

On f-and h-vectors of relative simplicial complexes

Authors: Codenotti, Giulia and Katth{\"a}n, Lukas and Sanyal, Raman
Note: Preprint
Date: 2017
Download: arXiv

Reflection groups, reflection arrangements, and invariant real varieties

Authors: Friedl, Tobias and Riener, Cordian and Sanyal, Raman
Journal: Proceedings of the American Mathematical Society
Date: 2017
DOI: 10.1090/proc/13821
Download: external arXiv

Theta rank, levelness, and matroid minors

Authors: Grande, Francesco and Sanyal, Raman
Journal: J. Combin. Theory Ser. B, 123:1–31
Date: 2017
DOI: 10.1016/j.jctb.2016.11.002
Download: external arXiv

Two double poset polytopes

Authors: Chappell, Thomas and Friedl, Tobias and Sanyal, Raman
Journal: SIAM Journal on Discrete Mathematics, 31(4):2378--2413
Date: 2017
Download: external arXiv

Small f-vectors of 3-spheres and of 4-polytopes

Authors: Brinkmann, Philip and Ziegler, Günter M.
Note: Preprint, 19 pages
Date: Oct 2016
Download: arXiv

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

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

Authors: Adiprasito, Karim and Sanyal, Raman
Journal: Publ. Math. Inst. Hautes Études Sci., 124:99–163
Date: 2016
DOI: 10.1007/s10240-016-0083-7
Download: external arXiv

Whitney numbers of arrangements via measure concentration of intrinsic volumes

Authors: Adiprasito, Karim and Sanyal, Raman
Note: Preprint
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

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
Journal: J. Eur. Math. Soc. (JEMS)
Note: accepted for publication, preprint on arxiv
Date: 2015
Download: arXiv

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

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


PhD thesis
f-Vector Spaces of Polytopes, Spheres, and Eulerian Lattices

Author: Brinkmann, Philip
Note: vii+132 pages
Date: Jun 2016
Download: external


Team+

Prof. Dr. Günter M. Ziegler   +

Projects: 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   +

Projects: A03
University: Goethe - Universität Frankfurt
E-Mail: sanyal[at]math.uni-frankfurt.de
Website: http://www.math.uni-frankfurt.de/~sanyal


PD Dr. Carsten Lange   +

Dr. Spencer Backman   +

Projects: A03
University: Goethe - Universität Frankfurt


Marie-Charlotte Brandenburg   +

Projects: A03
University: FU Berlin
E-Mail: marie.brandenburg[at]fu-berlin.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


Dr. Jean-Philippe Labbé   +

Projects: A03
University: FU Berlin
E-Mail: labbe[at]zedat.fu-berlin.de
Website: http://page.mi.fu-berlin.de/labbe/


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
E-Mail: sjoberg[at]math.fu-berlin.de