Günter M. Ziegler
Günter Matthias Ziegler is a German mathematician who has been serving as president of the Free University of Berlin since 2018. Ziegler is known for his research in discrete mathematics and geometry, and particularly on the combinatorics of polytopes... Read More
19 May 1963 (age 57)
Munich, Bavaria, West Germany
Face numbers of 4-Polytopes and 3-Spheres
by Günter M. Ziegler
In this paper, we discuss f- and flag-vectors of 4-dimensional convex polytopes and cellular 3-spheres. We put forward two crucial parameters of fatness and complexity: Fatness F(P) := (f_1+f_2-20)/(f_0+f_3-10) is large if there are many more edges and 2-faces than there are vertices and facets, while complexity C(P) := (f_{03}-20)/(f_0+f_3-10) is large if every facet has many vertices, and every vertex is in many facets. Recent results suggest that these parameters might allow one to...
Source: http://arxiv.org/abs/math/0208073v2
Lectures on 0/1-polytopes
These lectures on the combinatorics and geometry of 0/1-polytopes are meant as an \emph{introduction} and \emph{invitation}. Rather than heading for an extensive survey on 0/1-polytopes I present some interesting aspects of these objects; all of them are related to some quite recent work and progress. 0/1-polytopes have a very simple definition and explicit descriptions; we can enumerate and analyze small examples explicitly in the computer (e.g. using {\tt polymake}). However, any intuition...
On the difference between real and complex arrangements
Let $B$ be an arrangement of linear complex hyperplanes in $C^d$. Then a classical result by Orlik \& Solomon asserts that the cohomology algebra of the complement can be constructed from the combinatorial data that are given by the intersection lattice. If $B'$ is, more generally, a $2$-arrangement in $R^{2d}$ (an arrangement of real subspaces of codimension $2$ with even-dimensional intersections), then the intersection lattice still determines the cohomology {\it groups} of the...
Source: http://arxiv.org/abs/alg-geom/9202005v1
Non-rational configurations, polytopes, and surfaces
It is an amazing and a bit counter-intuitive discovery by Micha Perles from the sixties that there are ``non-rational polytopes'': combinatorial types of convex polytopes that cannot be realized with rational vertex coordinates. We describe a simple construction of non-rational polytopes that does not need duality (Perles' ``Gale diagrams''): It starts from a non-rational point configuration in the plane, and proceeds with so-called Lawrence extensions. We also show that there are non-rational...
Source: http://arxiv.org/abs/0710.4453v2
Projected Products of Polytopes
We construct a 2-parameter family of 4-dimensional polytopes with extreme combinatorial structure: In this family, the ``fatness'' of the f-vector gets arbitrarily close to 9, the ``complexity'' (given by the flag vector) gets arbitrarily close to 16. The polytopes are obtained from suitable deformed products of even polygons by a projection to four-space.
Polyhedral surfaces of high genus
The construction of the COMBINATORIAL data for a surface with n vertices of maximal genus is a classical problem: The maximal genus g=[(n-3)(n-4)/12] was achieved in the famous ``Map Color Theorem'' by Ringel et al. (1968). We present the nicest one of Ringel's constructions, for the case when n is congruent to 7 mod 12, but also an alternative construction, essentially due to Heffter (1898), which easily and explicitly yields surfaces of genus g ~ 1/16 n^2. For GEOMETRIC (polyhedral) surfaces...
Generalized Kneser coloring theorems with combinatorial proofs
The Kneser conjecture (1955) was proved by Lov\'asz (1978) using the Borsuk-Ulam theorem; all subsequent proofs, extensions and generalizations also relied on Algebraic Topology results, namely the Borsuk-Ulam theorem and its extensions. Only in 2000, Matou\v{s}ek provided the first combinatorial proof of the Kneser conjecture. Here we provide a hypergraph coloring theorem, with a combinatorial proof, which has as special cases the Kneser conjecture as well as its extensions and generalization...
Convex Polytopes: Extremal Constructions and f-Vector Shapes
These lecture notes treat some current aspects of two closely interrelated topics from the theory of convex polytopes: the shapes of f-vectors, and extremal constructions. The first lecture treats 3-dimensional polytopes; it includes a complete proof of the Koebe--Andreev--Thurston theorem, using the variational principle by Bobenko & Springborn (2004). In Lecture 2 we look at f-vector shapes of very high-dimensional polytopes. The third lecture explains a surprisingly simple construction...
Polyhedral Surfaces in Wedge Products
by Thilo Rörig; Günter M. Ziegler
We introduce the wedge product of two polytopes. The wedge product is described in terms of inequality systems, in terms of vertex coordinates as well as purely combinatorially, from the corresponding data of its constituents. The wedge product construction can be described as an iterated ``subdirect product'' as introduced by McMullen (1976); it is dual to the ``wreath product'' construction of Joswig and Lutz (2005). One particular instance of the wedge product construction turns out to be...
Simple polytopes without small separators
by Lauri Loiskekoski; Günter M. Ziegler
We show that by cutting off the vertices and then the edges of neighborly cubical polytopes, one obtains simple 4-dimensional polytopes with n vertices such that all separators of the graph have size at least $\Omega(n/\log^{3/2}n)$. This disproves a conjecture by Kalai from 1991/2004.
Topics: Combinatorics, Metric Geometry, Mathematics
Source: http://arxiv.org/abs/1510.00511
Spaces of convex n-partitions
by Emerson León; Günter M. Ziegler
We construct and study the space C(\R^d,n) of all partitions of \R^d into n non-empty open convex regions (n-partitions). A representation on the upper hemisphere of an n-sphere is used to obtain a metric and thus a topology on this space. We show that the space of partitions into possibly empty regions C(\R^d,\le n) yields a compactification with respect to this metric. We also describe faces and face lattices, combinatorial types, and adjacency graphs for $n$-partitions, and use these...
Topics: Metric Geometry, Mathematics
Projecting lattice polytopes without interior lattice points
by Benjamin Nill; Günter M. Ziegler
We show that up to unimodular equivalence there are only finitely many d-dimensional lattice polytopes without interior lattice points that do not admit a lattice projection onto a (d-1)-dimensional lattice polytope without interior lattice points. This was conjectured by Treutlein. As an immediate corollary, we get a short proof of a recent result of Averkov, Wagner and Weismantel, namely the finiteness of the number of maximal lattice polytopes without interior lattice points. Moreover, we...
Three non-equivalent realizations of the associahedron
by Cesar Ceballos; Günter M. Ziegler
We review three realizations of the associahedron that arise as secondary polytopes, from cluster algebras, and as Minkowski sums of simplices, and show that under any choice of parameters, the resulting associahedra are affinely non-equivalent.
A flag vector of a 3-sphere that is not the flag vector of a 4-polytope
by Philip Brinkmann; Günter M. Ziegler
We present a first example of a flag vector of a polyhedral sphere that is not the flag vector of any polytope. Namely, there is a unique 3-sphere with the parameters $(f_0,f_1,f_2,f_3;f_{02})=(12,40,40,12;120)$, but this sphere is not realizable by a convex 4-polytope. The 3-sphere, which is 2-simple and 2-simplicial, was found by Werner (2009); we present results of a computer enumeration which imply that the sphere with these parameters is unique. We prove that it is non-polytopal in two...
Topics: Metric Geometry, Combinatorics, Mathematics
Small f-vectors of 3-spheres and of 4-polytopes
We present a new algorithmic approach that can be used to determine whether a given quadruple $(f_0,f_1,f_2,f_3)$ is the f-vector of any convex 4-dimensional polytope. By implementing this approach, we classify the f-vectors of 4-polytopes in the range $f_0+f_3\le22$. In particular, we thus prove that there are f-vectors of cellular 3-spheres with the intersection property that are not f-vectors of any convex 4-polytopes, thus answering a question that may be traced back to the works of...
The $E_t$-Construction for Lattices, Spheres and Polytopes
by Andreas Paffenholz; Günter M. Ziegler
We describe and analyze a new construction that produces new Eulerian lattices from old ones. It specializes to a construction that produces new strongly regular cellular spheres (whose face lattices are Eulerian). The construction does not always specialize to convex polytopes; however, in a number of cases where we can realize it, it produces interesting classes of polytopes. Thus we produce an infinite family of rational 2-simplicial 2-simple 4-polytopes, as requested by Eppstein, Kuperberg...
Many Triangulated 3-Spheres
by Julian Pfeifle; Günter M. Ziegler
We construct 2^{\Omega(n^{5/4})} combinatorial types of triangulated 3-spheres on n vertices. Since by a result of Goodman and Pollack (1986) there are no more than 2^{O(n log n)} combinatorial types of simplicial 4-polytopes, this proves that asymptotically, there are far more combinatorial types of triangulated 3-spheres than of simplicial 4-polytopes on n vertices. This complements results of Kalai (1988), who had proved a similar statement about d-spheres and (d+1)-polytopes for fixed d...
Foldable Triangulations of Lattice Polygons
by Michael Joswig; Günter M. Ziegler
We give a simple formula for the signature of a foldable triangulation of a lattice polygon in terms of its boundary. This yields lower bounds on the number of real roots of certain of systems of polynomial equations known as "Wronski systems".
Realizing the associahedron: Mysteries and questions
There are many open problems and some mysteries connected to the realizations of the associahedra as convex polytopes. In this note, we describe three -- concerning special realizations with the vertices on a sphere, the space of all possible realizations, and possible realizations of the multiassociahedron.
Inscribable stacked polytopes
by Bernd Gonska; Günter M. Ziegler
We characterize the combinatorial types of stacked d-polytopes that are inscribable. Equivalently, we identify the triangulations of a simplex by stellar subdivisions that can be realized as Delaunay triangulations.
The Topological Tverberg Problem and winding numbers
by Torsten Schöneborn; Günter M. Ziegler
The Topological Tverberg Theorem claims that any continuous map of a (q-1)(d+1)-simplex to \R^d identifies points from q disjoint faces. (This has been proved for affine maps, for d=1, and if q is a prime power, but not yet in general.) The Topological Tverberg Theorem can be restricted to maps of the d-skeleton of the simplex. We further show that it is equivalent to a ``Winding Number Conjecture'' that concerns only maps of the (d-1)-skeleton of a (q-1)(d+1)-simplex to \R^d. ``Many Tverberg...
Construction and Analysis of Projected Deformed Products
by Raman Sanyal; Günter M. Ziegler
We introduce a deformed product construction for simple polytopes in terms of lower-triangular block matrix representations. We further show how Gale duality can be employed for the construction and for the analysis of deformed products such that specified faces (e.g. all the k-faces) are ``strictly preserved'' under projection. Thus, starting from an arbitrary neighborly simplicial (d-2)-polytope Q on n-1 vertices we construct a deformed n-cube, whose projection to the last dcoordinates yields...
Singular 0/1-matrices, and the hyperplanes spanned by random 0/1-vectors
by Thomas Voigt; Günter M. Ziegler
Let $P(d)$ be the probability that a random 0/1-matrix of size $d \times d$ is singular, and let $E(d)$ be the expected number of 0/1-vectors in the linear subspace spanned by d-1 random independent 0/1-vectors. (So $E(d)$ is the expected number of cube vertices on a random affine hyperplane spanned by vertices of the cube.) We prove that bounds on $P(d)$ are equivalent to bounds on $E(d)$: \[ P(d) = (2^{-d} E(d) + \frac{d^2}{2^{d+1}}) (1 + o(1)). \] We also report about computational...
On locally constructible spheres and balls
by Bruno Benedetti; Günter M. Ziegler
Durhuus and Jonsson (1995) introduced the class of "locally constructible" (LC) 3-spheres and showed that there are only exponentially-many combinatorial types of simplicial LC 3-spheres. Such upper bounds are crucial for the convergence of models for 3D quantum gravity. We characterize the LC property for d-spheres ("the sphere minus a facet collapses to a (d-2)-complex") and for d-balls. In particular, we link it to the classical notions of collapsibility, shellability and...
Martin Aigner, Günter M. Ziegler Auth. Proofs From THE BOOK
by Martin Aigner, Günter M. Ziegler
Book Proofs from THE BOOK, 5th edition. The one that says "-PRINT" has extra blank pages for printing.
Topics: math, proofs, demonstrations
Six topics on inscribable polytopes
by Arnau Padrol; Günter M. Ziegler
Inscribability of polytopes is a classic subject but also a lively research area nowadays. We illustrate this with a selection of well-known results and recent developments on six particular topics related to inscribable polytopes. Along the way we collect a list of (new and old) open questions.
Examples and counterexamples for Perles' conjecture
by Christian Haase; Günter M. Ziegler
The combinatorial structure of a d-dimensional simple convex polytope can be reconstructed from its abstract graph [Blind & Mani 1987, Kalai 1988]. However, no polynomial/efficient algorithm is known for this task, although a polynomially checkable certificate for the correct reconstruction was found by [Joswig, Kaibel & Koerner 2000]. A much stronger certificate would be given by the following characterization of the facet subgraphs, conjectured by M. Perles: ``The facet subgraphs of...
Topological lower bounds for the chromatic number: A hierarchy
by Jiri Matousek; Günter M. Ziegler
This paper is a study of ``topological'' lower bounds for the chromatic number of a graph. Such a lower bound was first introduced by Lov\'asz in 1978, in his famous proof of the \emph{Kneser conjecture} via Algebraic Topology. This conjecture stated that the \emph{Kneser graph} $\KG_{m,n}$, the graph with all $k$-element subsets of $\{1,2,...,n\}$ as vertices and all pairs of disjoint sets as edges, has chromatic number $n-2k+2$. Several other proofs have since been published (by B\'ar\'any,...
On the Monotone Upper Bound Problem
The Monotone Upper Bound Problem asks for the maximal number M(d,n) of vertices on a strictly-increasing edge-path on a simple d-polytope with n facets. More specifically, it asks whether the upper bound M(d,n)
Unimodular triangulations of dilated 3-polytopes
by Francisco Santos; Günter M. Ziegler
A seminal result in the theory of toric varieties, due to Knudsen, Mumford and Waterman (1973), asserts that for every lattice polytope $P$ there is a positive integer $k$ such that the dilated polytope $kP$ has a unimodular triangulation. In dimension 3, Kantor and Sarkaria (2003) have shown that $k=4$ works for every polytope. But this does not imply that every $k>4$ works as well. We here study the values of $k$ for which the result holds showing that: 1. It contains all composite...
Many projectively unique polytopes
by Karim A. Adiprasito; Günter M. Ziegler
We construct an infinite family of 4-polytopes whose realization spaces have dimension smaller or equal to 96. This in particular settles a problem going back to Legendre and Steinitz: whether and how the dimension of the realization space of a polytope is determined/bounded by its f-vector. From this, we derive an infinite family of combinatorially distinct 69-dimensional polytopes whose realization is unique up to projective transformation. This answers a problem posed by Perles and Shephard...
Realization spaces of 4-polytopes are universal
by Jürgen Richter-Gebert; Günter M. Ziegler
Let $P\subset\R^d$ be a $d$-dimensional polytope. The {\em realization space} of~$P$ is the space of all polytopes $P'\subset\R^d$ that are combinatorially equivalent to~$P$, modulo affine transformations. We report on work by the first author, which shows that realization spaces of \mbox{4-dimensional} polytopes can be ``arbitrarily bad'': namely, for every primary semialgebraic set~$V$ defined over~$\Z$, there is a $4$-polytope $P(V)$ whose realization space is ``stably equivalent'' to~$V$....
A Lost Counterexample and a Problem on Illuminated Polytopes
by Ronald F. Wotzlaw; Günter M. Ziegler
In a Note added in proof to a 1984 paper, Daniel A. Marcus claimed to have a counterexample to his conjecture that a minimal positively k-spanning vector configuration in R^m has size at most 2km. However, the counterexample was never published, and seems to be lost. Independently, ten years earlier, Peter Mani in 1974 solved a problem by Hadwiger, disproving that every ``illuminated'' d-dimensional polytope must have at least 2d vertices. These two studies are related by Gale duality, an...
Many non-equivalent realizations of the associahedron
by Cesar Ceballos; Francisco Santos; Günter M. Ziegler
Hohlweg and Lange (2007) and Santos (2004, unpublished) have found two different ways of constructing exponential families of realizations of the n-dimensional associahedron with normal vectors in {0,1,-1}^n, generalizing the constructions of Loday (2004) and Chapoton-Fomin-Zelevinsky (2002). We classify the associahedra obtained by these constructions modulo linear equivalence of their normal fans and show, in particular, that the only realization that can be obtained with both methods is the...
Zonotopes With Large 2D Cuts
by Thilo Rörig; Nikolaus Witte; Günter M. Ziegler
There are d-dimensional zonotopes with n zones for which a 2-dimensional central section has \Omega(n^{d-1}) vertices. For d=3 this was known, with examples provided by the "Ukrainian easter eggs'' by Eppstein et al. Our result is asymptotically optimal for all fixed d>=2.
Convex Equipartitions via Equivariant Obstruction Theory
by Pavle V. M. Blagojević; Günter M. Ziegler
We describe a regular cell complex model for the configuration space F(\R^d,n). Based on this, we use Equivariant Obstruction Theory to prove the prime power case of the conjecture by Nandakumar and Ramana Rao that every polygon can be partitioned into n convex parts of equal area and perimeter.
On Kalai's conjectures concerning centrally symmetric polytopes
by Raman Sanyal; Axel Werner; Günter M. Ziegler
In 1989 Kalai stated the three conjectures A, B, C of increasing strength concerning face numbers of centrally symmetric convex polytopes. The weakest conjecture, A, became known as the ``$3^d$-conjecture''. It is well-known that the three conjectures hold in dimensions d \leq 3. We show that in dimension 4 only conjectures A and B are valid, while conjecture C fails. Furthermore, we show that both conjectures B and C fail in all dimensions d \geq 5.
Fat 4-polytopes and fatter 3-spheres
by David Eppstein; Greg Kuperberg; Günter M. Ziegler
We introduce the fatness parameter of a 4-dimensional polytope P, defined as \phi(P)=(f_1+f_2)/(f_0+f_3). It arises in an important open problem in 4-dimensional combinatorial geometry: Is the fatness of convex 4-polytopes bounded? We describe and analyze a hyperbolic geometry construction that produces 4-polytopes with fatness \phi(P)>5.048, as well as the first infinite family of 2-simple, 2-simplicial 4-polytopes. Moreover, using a construction via finite covering spaces of surfaces, we...
The ideal-valued index for a dihedral group action, and mass partition by two hyperplanes
We compute the complete Fadell-Husseini index of the 8 element dihedral group D_8 acting on S^d \times S^d, both for F_2 and for integer coefficients. This establishes the complete goup cohomology lower bounds for the two hyperplane case of Gr"unbaum's 1960 mass partition problem: For which d and j can any j arbitrary measures be cut into four equal parts each by two suitably-chosen hyperplanes in R^d? In both cases, we find that the ideal bounds are not stronger than previously...
Using Brouwer's fixed point theorem
by Anders Björner; Jiří Matoušek; Günter M. Ziegler
Brouwer's fixed point theorem from 1911 is a basic result in topology - with a wealth of combinatorial and geometric consequences. In these lecture notes we present some of them, related to the game of HEX and to the piercing of multiple intervals. We also sketch stronger theorems, due to Oliver and others, and explain their applications to the fascinating (and still not fully solved) evasiveness problem.
Topics: Mathematics, Combinatorics, Algebraic Topology
Source: http://arxiv.org/abs/1409.7890
Tetrahedra on deformed spheres and integral group cohomology
by Pavle V. M. Blagojevic; Günter M. Ziegler
We show that for every injective continuous map f: S^2 --> R^3 there are four distinct points in the image of f such that the convex hull is a tetrahedron with the property that two opposite edges have the same length and the other four edges are also of equal length. This result represents a partial result for the topological Borsuk problem for R^3. Our proof of the geometrical claim, via Fadell-Husseini index theory, provides an instance where arguments based on group cohomology with...
Barycenters of points that are constrained to a polytope skeleton
by Pavle V. M. Blagojević; Florian Frick; Günter M. Ziegler
We give a short and simple proof of a recent result of Dobbins that any point in an $nd$-polytope is the barycenter of $n$ points in the $d$-skeleton. This new proof builds on the constraint method that we recently introduced to prove Tverberg-type results.
Topics: Mathematics, Metric Geometry, Combinatorics
Barycenters of Polytope Skeleta and Counterexamples to the Topological Tverberg Conjecture, via Constraints
Using the authors' 2014 "constraints method," we give a short proof for a 2015 result of Dobbins on representations of a point in a polytope as the barycenter of points in a skeleton, and show that the "r-fold Whitney trick" of Mabillard and Wagner (2014/2015) implies that the Topological Tverberg Conjecture for r-fold intersections fails dramatically for all r that are not prime powers.
Topics: Combinatorics, Algebraic Topology, Mathematics, Metric Geometry
A tight colored Tverberg theorem for maps to manifolds
by Pavle V. M. Blagojević; Benjamin Matschke; Günter M. Ziegler
We prove that any continuous map of an N-dimensional simplex Delta_N with colored vertices to a d-dimensional manifold M must map r points from disjoint rainbow faces of Delta_N to the same point in M: For this we have to assume that N \geq (r-1)(d+1), no r vertices of Delta_N get the same color, and our proof needs that r is a prime. A face of Delta_N is a rainbow face if all vertices have different colors. This result is an extension of our recent "new colored Tverberg theorem", the...
Equivariant Topology of Configuration Spaces
by Pavle V. M. Blagojević; Wolfgang Lück; Günter M. Ziegler
We study the Fadell-Husseini index of the configuration space F(R^d,n) with respect to different subgroups of the symmetric group S_n. For p prime and d>0, we completely determine Index_{Z/p}(F(R^d,p);F_p) and partially describe Index{(Z/p)^k}(F(R^d,p^k);F_p). In this process we obtain results of independent interest, including: (1) an extended equivariant Goresky-MacPherson formula, (2) a complete description of the top homology of the partition lattice Pi_p as an F_p[Z_p]-module, and (3) a...
The Random Edge Rule on Three-Dimensional Linear Programs
by Volker Kaibel; Raphael Mechtel; Micha Sharir; Günter M. Ziegler
The worst-case expected length f(n) of the path taken by the simplex algorithm with the Random Edge pivot rule on a 3-dimensional linear program with n constraints is shown to be bounded by 1.3445 n
Optimal bounds for the colored Tverberg problem
We prove a "Tverberg type" multiple intersection theorem. It strengthens the prime case of the original Tverberg theorem from 1966, as well as the topological Tverberg theorem of Barany et al. (1980), by adding color constraints. It also provides an improved bound for the (topological) colored Tverberg problem of Barany & Larman (1992) that is tight in the prime case and asymptotically optimal in the general case. The proof is based on relative equivariant obstruction theory.
Bier spheres and posets
by Anders Björner; Andreas Paffenholz; Jonas Sjöstrand; Günter M. Ziegler
In 1992 Thomas Bier presented a strikingly simple method to produce a huge number of simplicial (n-2)-spheres on 2n vertices as deleted joins of a simplicial complex on n vertices with its combinatorial Alexander dual. Here we interpret his construction as giving the poset of all the intervals in a boolean algebra that "cut across an ideal." Thus we arrive at a substantial generalization of Bier's construction: the Bier posets Bier(P,I) of an arbitrary bounded poset P of finite...
Combinatorial Stokes formulas via minimal resolutions
by Bernhard Hanke; Raman Sanyal; Carsten Schultz; Günter M. Ziegler
We describe an explicit chain map from the standard resolution to the minimal resolution for the finite cyclic group Z_k of order k. We then demonstrate how such a chain map induces a "Z_k-combinatorial Stokes theorem", which in turn implies "Dold's theorem" that there is no equivariant map from an n-connected to an n-dimensional free Z_k-complex. Thus we build a combinatorial access road to problems in combinatorics and discrete geometry that have previously been treated...
Face numbers of centrally symmetric polytopes from split graphs
by Ragnar Freij; Matthias Henze; Moritz W. Schmitt; Günter M. Ziegler
We analyze a remarkable class of centrally symmetric polytopes, the Hansen polytopes of split graphs. We confirm Kalai's 3^d-conjecture for such polytopes (they all have at least 3^d nonempty faces) and show that the Hanner polytopes among them (which have exactly 3^d nonempty faces) correspond to threshold graphs. Our study produces a new family of Hansen polytopes that have only 3^d+16 nonempty faces.