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
  • Joseph Doolittle, Jean-Philippe Labbé, Carsten Lange, Rainer Sinn, Jonathan Speer, and Günter M. Ziegler.
    Combinatorial inscribability obstructions for higher-dimensional polytopes.
    Preprint, October 2019.
    arXiv:1910.05241.
  • Pavle V. M. Blagojević, Günter Rote, Johanna K. Steinmeyer, and Günter M. Ziegler.
    Convex Equipartitions of Colored Point Sets.
    Discrete & Computational Geometry, 61(2):355–363, March 2019.
    doi:10.1007/s00454-017-9959-7.
  • Pavle V. M. Blagojević, Albert Haase, and Günter M. Ziegler.
    Tverberg-Type Theorems for Matroids: A Counterexample and a Proof.
    Combinatorica, February 2019.
    doi:10.1007/s00493-018-3846-6.
  • Günter M. Ziegler.
    Additive structures on f-vector sets of polytopes.
    Advances in Geometry, October 2018. Published online.
    arXiv:1709.02021.
  • Spencer Backman, Sebastian Manecke, and Raman Sanyal.
    Cone valuations, Gram's relation, and flag-angles.
    Preprint, September 2018.
    arXiv:1809.00956.
  • Djordje Baralić, Pavle V. M. Blagojević, Roman Karasev, and Aleksandar Vučić.
    Index of Grassmann manifolds and orthogonal shadows.
    Forum Mathematicum, 30(6):1539–1572, July 2018.
    doi:10.1007/s00454-018-0006-0.
  • Hannah Sjöberg and Günter M. Ziegler.
    Characterizing face and flag vector pairs for polytopes.
    Preprint, March 2018.
    arXiv:1803.04801.
  • Moritz Firsching.
    The complete enumeration of $4$-polytopes and $3$-spheres with nine vertices.
    Preprint, March 2018.
    arXiv:1803.05205.
  • Philip Brinkmann and Günter M. Ziegler.
    Small f-vectors of 3-spheres and of 4-polytopes.
    Mathematics of Computation, 87(314):2955–2975, February 2018.
    arXiv:1610.01028, doi:10.1090/mcom/3300.
  • Jean-Philippe Labbé and Carsten Lange.
    Cambrian acyclic domains: counting $c$-singletons.
    Preprint, 2018.
    arXiv:1802.07978.
  • Pavle V. M. Blagojević, Günter Rote, Johanna Steinmeyer, and Günter M. Ziegler.
    Convex equipartitions of colored point sets.
    Discrete Comput. Geometry, December 2017. Published online.
    arXiv:1705.03953.
  • Hannah Sjöberg and Günter M. Ziegler.
    Semi-algebraic sets of $f$-vectors.
    Preprint, November 2017.
    arXiv:1711.01864.
  • Günter M Ziegler and Andreas Loos.
    “What is Mathematics?” and why we should ask, where one should experience and learn that, and how to teach it.
    In Proceedings of the 13th International Congress on Mathematical Education, 63–77. Springer, November 2017.
    doi:10.1007/978-3-319-62597-3_5.
  • Pavle V. M. Blagojević, Nevena Palić, and Günter M. Ziegler.
    Cutting a part from many measures.
    Preprint, 15 pages, October 2017.
    arXiv:1710.05118.
  • Pavle V. M. Blagojević and Pablo Soberón.
    Thieves can make sandwiches.
    preprint, September 2017.
    arXiv:arXiv:1706.03640, doi:10.1112/blms.12109.
  • Jean-Philippe Labbé, Günter Rote, and Günter M. Ziegler.
    Area difference bounds for dissections of a square into an odd number of triangles.
    Preprint, August 2017.
    arXiv:1708.02891.
  • Pavle V. M. Blagojević and Günter M. Ziegler.
    Beyond the Borsuk-Ulam Theorem: The Topological Tverberg Story.
    In Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, editors, Journey Through Discrete Mathematics. A Tribute to Jiří Matoušek, pages 273–341. Springer, May 2017.
    arXiv:1605.07321, doi:10.1007/978-3-319-44479-6_11.
  • Philip Brinkmann and Günter M Ziegler.
    A flag vector of a 3-sphere that is not the flag vector of a 4-polytope.
    Mathematika, 63(1):260–271, 2017.
    arXiv:1506.08148, doi:10.1112/S0025579316000267.
  • Karim Adiprasito, Philip Brinkmann, Arnau Padrol, Pavel Paták, Zuzana Patáková, and Raman Sanyal.
    Colorful simplicial depth, Minkowski sums, and generalized Gale transforms.
    International Mathematics Research Notices, 2017.
    arXiv:1607.00347, doi:10.1093/imrn/rnx184.
  • Katharina Jochemko and Raman Sanyal.
    Combinatorial mixed valuations.
    Advances in Mathematics, 319:630–652, 2017.
    arXiv:1605.07431, doi:10.1016/j.aim.2017.08.032.
  • Francesco Grande, Arnau Padrol, and Raman Sanyal.
    Extension complexity and realization spaces of hypersimplices.
    Discrete Comput Geom, 2017.
    arXiv:1601.02416, doi:10.1007/s00454-017-9925-4.
  • Raman Sanyal and Christian Stump.
    Lipschitz polytopes of posets and permutation statistics.
    Preprint, 2017.
    arXiv:1703.10586.
  • Florian Frick and Raman Sanyal.
    Minkowski complexes and convex threshold dimension.
    Journal of Combinatorial Theory, Series A, 151:202–206, 2017.
    URL: http://www.sciencedirect.com/science/article/pii/S0097316517300584, arXiv:1607.07814.
  • Christian Haase, Martina Juhnke-Kubitzke, Raman Sanyal, and Thorsten Theobald.
    Mixed Ehrhart polynomials.
    Electron. J. Combin., 24(Issue 1):Paper #P1.10, 2017.
    URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p10, arXiv:1509.02254.
  • Giulia Codenotti, Lukas Katthän, and Raman Sanyal.
    On $f$- and $h$-vectors of relative simplicial complexes.
    Preprint, 2017.
    arXiv:1711.02729.
  • Laura Gellert and Raman Sanyal.
    On degree sequences of undirected, directed, and bidirected graphs.
    European Journal of Combinatorics, 64:113–124, 2017.
    URL: http://www.sciencedirect.com/science/article/pii/S0195669817300409, arXiv:1512.08448.
  • Pavle V. M. Blagojević, Aleksandra S. Dimitrijević Blagojević, and Günter M. Ziegler.
    Polynomial partitioning for several sets of varieties.
    J. Fixed Point Theory Appl., 19:1653–1660, 2017.
    arXiv:1601.01629.
  • Moritz Firsching.
    Realizability and Inscribability for Simplicial Polytopes via Nonlinear Optimization.
    Mathematical Programming, 166(1-2):273–295, 2017.
    arXiv:1508.02531, doi:10.1007/s10107-017-1120-0.
  • Tobias Friedl, Cordian Riener, and Raman Sanyal.
    Reflection groups, reflection arrangements, and invariant real varieties.
    Proceedings of the American Mathematical Society, 2017.
    URL: http://www.ams.org/journals/proc/0000-000-00/S0002-9939-2017-13821-0/home.html, arXiv:1602.06732, doi:10.1090/proc/13821.
  • Lauri Loiskekoski and Günter M Ziegler.
    Simple polytopes without small separators.
    Israel Journal of Mathematics, 221(2):731–739, 2017.
    arXiv:1510.00511, doi:10.1007/s11856-017-1572-1.
  • Lauri Loiskekoski and Günter M. Ziegler.
    Simple polytopes without small separators, II: Thurston's bound.
    Preprint, Israel J. Math., to appear, 2017.
    arXiv:1708.06718.
  • Francesco Grande and Raman Sanyal.
    Theta rank, levelness, and matroid minors.
    J. Combin. Theory Ser. B, 123:1–31, 2017.
    arXiv:1408.1262, doi:10.1016/j.jctb.2016.11.002.
  • Pavle V. M. Blagojević, Albert Haase, and Günter M. Ziegler.
    Tverberg-type theorems for matroids: A counterexample and a proof.
    Preprint, 2017.
    arXiv:1705.03624.
  • Thomas Chappell, Tobias Friedl, and Raman Sanyal.
    Two double poset polytopes.
    SIAM Journal on Discrete Mathematics, 31(4):2378–2413, 2017.
    URL: http://epubs.siam.org/doi/10.1137/16M1091800, arXiv:1606.04938.
  • Pavle V. M. Blagojević, Aleksandra S. Dimitrijević Blagojević, and Günter M. Ziegler.
    The topological transversal Tverberg theorem plus constraints.
    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, march 2016.
    arXiv:1604.02814.
  • Karim Adiprasito and Arnau Padrol.
    A universality theorem for projectively unique polytopes and a conjecture of Shephard.
    Israel J. Math., 211:239–255, 2016.
    arXiv:1301.2960.
  • Pavle V. M. Blagojević, Florian Frick, Albert Haase, and Günter M. Ziegler.
    Hyperplane mass partitions via relative equivariant obstruction theory.
    Documenta Mathematica, 21:735–771, 2016.
    URL: http://emis.ams.org/journals/DMJDMV/vol-21/20.pdf, arXiv:1509.02959.
  • Karim Adiprasito and Raman Sanyal.
    Relative Stanley-Reisner theory and Upper Bound Theorems for Minkowski sums.
    Publ. Math. Inst. Hautes Études Sci., 124:99–163, 2016.
    arXiv:1405.7368, doi:10.1007/s10240-016-0083-7.
  • Arnau Padrol and Günter M Ziegler.
    Six topics on inscribable polytopes.
    In Advances in Discrete Differential Geometry, pages 407–419. Springer, 2016.
    arXiv:1511.03458, doi:10.1007/978-3-662-50447-5_13.
  • Imre Bárány, Pavle V. M. Blagojević, and Günter M. Ziegler.
    Tverberg’s theorem at 50: extensions and counterexamples.
    Notices of the AMS, 63(7):732–739, 2016.
    doi:10.1090/noti1415.
  • Karim Adiprasito and Raman Sanyal.
    Whitney numbers of arrangements via measure concentration of intrinsic volumes.
    Preprint, 2016.
    arXiv:1606.09412.
  • Andreas Loos and Günter M Ziegler.
    „Was ist Mathematik" lernen und lehren.
    Mathematische Semesterberichte, 63(1):155–169, 2016.
    doi:10.1007/s00591-016-0167-y.
  • Pavle V. M. Blagojevic, Florian Frick, Albert Haase, and Günter M. Ziegler.
    Hyperplane mass partitions via relative Equivariant Obstruction Theory.
    preprint, September 2015.
    arXiv:1509.02959.
  • Moritz Firsching.
    Realizability and inscribability for some simplicial spheres and matroid polytopes.
    Preprint, August 2015.
    arXiv:1508.02531.
  • Hao Chen and Arnau Padrol.
    Scribability Problems for Polytopes.
    Preprint, August 2015.
    arXiv:1508.03537.
  • Karim Adiprasito and Arnau Padrol.
    The universality theorem for neighborly polytopes.
    Combinatorica, February 2015. accepted, preprint at arxiv.
    arXiv:1402.7207.
  • Katharina Jochemko and Raman Sanyal.
    Combinatorial positivity of translation-invariant valuations and a discrete Hadwiger theorem.
    accepted for publication, preprint on arxiv, 2015.
    arXiv:1505.07440.
  • Cesar Ceballos, Arnau Padrol, and Camilo Sarmiento.
    Dyck path triangulations and extendability.
    Journal of Combinatorial Theory, Series A, 131(0):187–208, 2015.
    URL: http://www.sciencedirect.com/science/article/pii/S009731651400140X, arXiv:1402.5111.
  • Hiroyuki Miyata and Arnau Padrol.
    Enumeration of neighborly polytopes and oriented matroids.
    Experimental Math., 24:489–505, 2015.
    arXiv:1408.0688, doi:10.1080/10586458.2015.1015084.
  • Günter M. Ziegler Karim Adiprasito.
    Many projectively unique polytopes.
    Inventiones math., 199:581–652, 2015.
    arXiv:1212.5812, doi:10.1007/s00222-014-0519-y.
  • Benjamin Nill and Arnau Padrol.
    The degree of point configurations: Ehrhart theory, Tverberg points and almost neighborly polytopes.
    European Journal of Combinatorics (special issue in honour of Michel Las Vergnas), 50:159–179, 2015.
    arXiv:1209.5712.
  • Karim Adiprasito, Arnau Padrol, and Louis Theran.
    Universality theorems for inscribed polytopes and Delaunay triangulations.
    Discrete Comput. Geom., 54:412–431, 2015.
    arXiv:1406.7831.
  • Arnau Padrol and Julian Pfeifle.
    Polygons as slices of higher-dimensional polytopes.
    Preprint, April 2014.
    arXiv:1404.2443.
  • Arnau Padrol and Louis Theran.
    Delaunay triangulations with disconnected realization spaces.
    In Siu-Wing Cheng and Olivier Devillers, editors, 30th Annual Symposium on Computational Geometry, SOCG'14, Kyoto, Japan, June 08 - 11, 2014, 163 – 170. ACM, 2014.
    doi:10.1145/2582112.2582119.
  • Bernd Gonska and Arnau Padrol.
    Many neighborly inscribed polytopes and Delaunay triangulations.
    In 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 161–168. 2014.
    URL: http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAT0115.
  • Pavle V. M. Blagojevic, Florian Frick, Benjamin Matschke, and Günter M. Ziegler.
    Tight and non-tight topological Tverberg type theorems.
    Oberwolfach Reports, 11(3):2284–2287, 2014.
    dgd:67.
  • Pavle V. M. Blagojevic, Florian Frick, and Günter M. Ziegler.
    Tverberg plus constraints.
    Bulletin of the London Mathematical Society, 46:953–967, 2014. Extended Abstract: Oberwolfach Reports, 11(1):14-16, 2014.
    URL: http://blms.oxfordjournals.org/cgi/content/abstract/bdu049?ijkey=s0zAd5sXaMm0aIt, arXiv:1401.0690, doi:10.1112/blms/bdu049.
  • Arnau Padrol.
    Many neighborly polytopes and oriented matroids.
    Discrete Comput. Geom., 50(4):865–902, December 2013.
    arXiv:1202.2810, doi:10.1007/s00454-013-9544-7.
  • Bernd Gonska and Arnau Padrol.
    Neighborly inscribed polytopes and Delaunay triangulations.
    Preprint, August 2013.
    arXiv:1308.5798.
  • Pavle V. M. Blagojevic, Wolfgang Lück, and Günter M. Ziegler.
    On highly regular embeddings.
    Preprint, 19 pages; Transactions Amer. Math. Soc. to appear, Extended Abstract: in Proc. "Combinatorial Methods in Topology and Algebra” (CoMeTa), Cortona, May 2013.
    arXiv:1305.7483, dgd:65.
  • Bernd Gonska and Günter M. Ziegler.
    Inscribable stacked polytopes.
    Adv. Geom., 13:723–740, 2013.
    arXiv:1111.5322.

PhD thesis

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/