A03Geometric 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.
Note: Published online
Date: Oct 2018

Characterizing face and flag vector pairs for polytopes

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

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

Cambrian acyclic domains: counting c-singletons

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

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

Semi-algebraic sets of f-vectors

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

“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

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

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

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

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

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

Combinatorial mixed valuations

Authors: Jochemko, Katharina and Sanyal, Raman
Date: 2017
DOI: 10.1016/j.aim.2017.08.032

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

Lipschitz polytopes of posets and permutation statistics

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

Minkowski complexes and convex threshold dimension

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

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

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

On f-and h-vectors of relative simplicial complexes

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

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

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

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

Semi-algebraic sets of f-vectors

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

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

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

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

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

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

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

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

Journal: Israel J. Math., 211:239-255
Date: 2016

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

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

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

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

Whitney numbers of arrangements via measure concentration of intrinsic volumes

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

„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

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

Realizability and inscribability for some simplicial spheres and matroid polytopes

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

Scribability Problems for Polytopes

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

The universality theorem for neighborly polytopes

Journal: Combinatorica
Note: accepted, preprint at arxiv
Date: Feb 2015

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

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

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

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

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

Universality theorems for inscribed polytopes and Delaunay triangulations

Journal: Discrete Comput. Geom., 54:412-431
Date: 2015

Polygons as slices of higher-dimensional polytopes

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

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

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

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

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

Many neighborly polytopes and oriented matroids.

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

Neighborly inscribed polytopes and Delaunay triangulations

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

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

Inscribable stacked polytopes

Authors: Gonska, Bernd and Ziegler, Günter M.
Date: 2013

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

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

Optimization Methods in Discrete Geometry

Author: Firsching, Moritz
Note: 85 pages
Date: Jan 2016

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

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