A03
Geometric Constraints for Polytopes

Exploring the Subtle Interplay of Geometry and Combinatorics

This project is based on the observation that combinatorial and geometric features of polytopes are interlocked in many different, conceptually independent, ways. This interaction in both directions divides our project into two main strands, “Geometry → Combinatorics” and “Combinatorics → Geometry,” where the arrows may be read as “constrains,” “impacts,” or “restricts.” Both directions are pursued in parallel, and the focus of understanding the interactions was considerably furthered during the first funding period. We now joined by our Einstein Visiting Fellow Francisco Santos.

Mission-

This project studies the interaction between geometric properties of polytopes (such as “roundness” measured in various ways) and combinatorial data (such as given by face/flag vectors or adjacency information). 

Scientific Details+


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.

Publications+

Papers
Additive structures on f-vector sets of polytopes

Author: Ziegler, Günter M.
Journal: Advances in Geometry
Note: Published online
Date: Oct 2018
Download: arXiv

Characterizing face and flag vector pairs for polytopes

Authors: Sjöberg, Hannah and Ziegler, Günter M.
Note: Preprint
Date: Mar 2018
Download: arXiv

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

Authors: Brinkmann, Philip and Ziegler, Günter M.
Journal: Mathematics of Computation
Date: Feb 2018
DOI: 10.1090/mcom/3300
Download: external arXiv

Cambrian acyclic domains: counting c-singletons

Authors: Labbé, Jean-Philippe and Lange, Carsten
Note: Preprint
Date: 2018
Download: arXiv

Convex equipartitions of colored point sets

Authors: Blagojević, Pavle V. M. and Rote, Günter and Steinmeyer, Johanna and Ziegler, Günter M.
Journal: Discrete Comput. Geometry
Note: Published online
Date: Dec 2017
Download: arXiv

Semi-algebraic sets of f-vectors

Authors: Sjöberg, Hannah and Ziegler, Günter M.
Note: Preprint
Date: Nov 2017
Download: arXiv

“What is Mathematics?” and why we should ask, where one should experience and learn that, and how to teach it

Authors: Ziegler, Günter M and Loos, Andreas
In Proceedings: Proceedings of the 13th International Congress on Mathematical Education
Date: Nov 2017
DOI: 10.1007/978-3-319-62597-3_5
Download: external

Cutting a part from many measures

Authors: Blagojević, Pavle V. M. and Palić, Nevena and Ziegler, Günter M.
Note: Preprint, 15 pages
Date: Oct 2017
Download: arXiv

Area difference bounds for dissections of a square into an odd number of triangles

Authors: Labbé, Jean-Philippe and Rote, Günter and Ziegler, Günter M.
Note: Preprint
Date: Aug 2017
Download: arXiv

Beyond the Borsuk-Ulam Theorem: The Topological Tverberg Story

Authors: Blagojević, Pavle V. M. and Ziegler, Günter M.
In Collection: Journey Through Discrete Mathematics. A Tribute to Jiří Matoušek, Springer
Date: May 2017
DOI: 10.1007/978-3-319-44479-6_11
Download: external 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
Journal: Mathematika, 63(1):260--271
Date: 2017
DOI: 10.1112/S0025579316000267
Download: external 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

Polynomial partitioning for several sets of varieties

Authors: Blagojević, Pavle V. M. and Blagojević, Aleksandra S. Dimitrijević and Ziegler, Günter M.
Journal: J. Fixed Point Theory Appl., 19:1653--1660
Date: 2017
Download: arXiv

Realizability and inscribability for simplicial polytopes via nonlinear optimization

Author: Firsching, Moritz
Journal: Mathematical Programming, 166(1-2):273--295
Date: 2017
DOI: 10.1007/s10107-017-1120-0
Download: external 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

Semi-algebraic sets of f-vectors

Authors: Sjöberg, Hannah and Ziegler, Günter M
Note: Israel J. Math., to appear.
Date: 2017
Download: arXiv

Simple polytopes without small separators

Authors: Loiskekoski, Lauri and Ziegler, Günter M
Journal: Israel Journal of Mathematics, 221(2):731--739
Date: 2017
DOI: 10.1007/s11856-017-1572-1
Download: external arXiv

Simple polytopes without small separators, II: Thurston's bound

Authors: Loiskekoski, Lauri and Ziegler, Günter M.
Note: Preprint, Israel J. Math., to appear
Date: 2017
Download: 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

Tverberg-type theorems for matroids: A counterexample and a proof

Authors: Blagojević, Pavle V. M. and Haase, Albert and Ziegler, Günter M.
Note: Preprint
Date: 2017
Download: 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

The topological transversal Tverberg theorem plus constraints

Authors: Blagojević, Pavle V. M. and Blagojević, Aleksandra S. Dimitrijević and Ziegler, Günter M.
Note: Preprint, "Discrete and Intuitive Geometry -- László Fejes Tóth 100 Festschrift" (G. Ambrus, I. Bárány, K. J. Böröczky, G. Fejes Tóth, J. Pach, eds.), Bolyai Society Mathematical Studies series, to appear
Date: Mar 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

Hyperplane mass partitions via relative equivariant obstruction theory

Authors: Blagojević, Pavle V. M. and Frick, Florian and Haase, Albert and Ziegler, Günter M.
Journal: Documenta Mathematica, 21:735--771
Date: 2016
Download: external 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

Six topics on inscribable polytopes

Authors: Padrol, Arnau and Ziegler, Günter M
In Collection: Advances in Discrete Differential Geometry, Springer
Date: 2016
DOI: 10.1007/978-3-662-50447-5_13
Download: external arXiv

Tverberg’s theorem at 50: extensions and counterexamples

Authors: Bárány, Imre and Blagojević, Pavle V. M. and Ziegler, Günter M.
Journal: Notices of the AMS, 63(7):732--739
Date: 2016
DOI: 10.1090/noti1415
Download: external

Whitney numbers of arrangements via measure concentration of intrinsic volumes

Authors: Adiprasito, Karim and Sanyal, Raman
Note: Preprint
Date: 2016
Download: arXiv

„Was ist Mathematik" lernen und lehren

Authors: Loos, Andreas and Ziegler, Günter M
Journal: Mathematische Semesterberichte, 63(1):155--169
Date: 2016
DOI: 10.1007/s00591-016-0167-y
Download: external

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

Optimization Methods in Discrete Geometry

Author: Firsching, Moritz
Note: 85 pages
Date: Jan 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. Jean-Philippe Labbé   +

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


Sebastian Manecke   +

Projects: A03
University: Goethe - Universität Frankfurt
E-Mail: manecke[at]math.uni-frankfurt.de


Hannah Schäfer Sjöberg   +

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