math_groups_discgeom

Publikationen_old

List of scientific publications: download

List of other publications: download

185 Publikation(en)

On k-regular maps

Pavle V. M. Blagojević and Wolfgang Lück and Günter M. Ziegler

http://arxiv.org/abs/1305.7483

Given parameters k, l, and d, we give new lower bounds on the dimensions N such that there are maps from R^d to R^N that are k-regular, l-skew embeddings, or k-regular-l-skew embeddings. This extends and sharpens results due to Chisholm (1979) and Ghomi-Tabachnikov (2008).

Realizing the associahedron: Mysteries and questions

Cesar Ceballos and Günter M. Ziegler

Basel: Springer | 2012

Erschienen in: "Associahedra, Tamari Lattices and Related Structures'', Tamari Memorial Festschrift, Progress in Mathematics, volume 299, pages 119-127

http://arxiv.org/abs/1110.4059v1http://link.springer.com/chapter/10.1007 ...

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.

Lectures on Polytopes (Russian Translation)

Günter M. Ziegler

Moscow: MCCME Publishers | 2012

A tight colored Tverberg theorem for maps to manifolds

Pavle V. M. Blagojević and Benjamin Matschke and Günter M. Ziegler

Erschienen in: Topology and its Applications (Proc.\ ATA2010), volume 158, pages 1445-1452

http://arxiv.org/abs/1107.1904v1

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 special case of M=R^d. It is also a generalization of Volovikov's 1996 topological Tverberg theorem for maps to manifolds, which arises when all color classes have size 1 (i.e., without color constraints); for this special case Volovikov's proof, as well as ours, work when r is a prime power.

A lost counterexample and a problem on illuminated polytopes

Ronald Wotzlaw and Günter M. Ziegler

Erschienen in: American Math. Monthly, volume 118, pages 534-543 #

http://arxiv.org/abs/0908.1698v1

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 elementary linear algebra technique devised by Micha A. Perles in the sixties. Thus, we note that Mani's study provides a counterexample for Marcus' conjecture with exactly the parameters that Marcus had claimed. In the other direction, with Marcus' tools we provide an answer to a problem left open by Mani: Could ``illuminated'' d-dimensional polytopes on a minimal number of vertices be nonsimplicial?

3N colored points in a plane

Günter M. Ziegler

Erschienen in: Notices of the AMS, pages 550-557

http://www.ams.org/notices/201104/rtx110 ...

On locally constructible spheres and balls

Bruno Benedetti and Günter M. Ziegler

Erschienen in: Acta Mathematica, volume 206, pages 205-243

http://arxiv.org/abs/0902.0436v4http://link.springer.com/article/10.1007 ...

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 constructibility, and obtain hierarchies of such properties for simplicial balls and spheres. The main corollaries from this study are: 1.) Not all simplicial 3-spheres are locally constructible. (This solves a problem by Durhuus and Jonsson.) 2.) There are only exponentially many shellable simplicial 3-spheres with given number of facets. (This answers a question by Kalai.) 3.) All simplicial constructible 3-balls are collapsible. (This answers a question by Hachimori.) 4.) Not every collapsible 3-ball collapses onto its boundary minus a facet. (This property appears in papers by Chillingworth and Lickorish.)

Optimal bounds for a colorful Tverberg--Vrećica type problem

Pavle V. M. Blagojević and Benjamin Matschke and Günter M. Ziegler

Erschienen in: Advances in Math., volume 226, pages 5198-5215

http://arXiv.org/abs/0911.2692http://www.sciencedirect.com/science/art ...

We prove the following optimal colorful Tverberg-Vrecica type transversal theorem: For prime r and for any k+1 colored collections of points C^l of size |C^l|=(r-1)(d-k+1)+1 in R^d, where each C^l is a union of subsets (color classes) C_i^l of size smaller than r, l=0,...,k, there are partition of the collections C^l into colorful sets F_1^l,...,F_r^l such that there is a k-plane that meets all the convex hulls conv(F_j^l), under the assumption that r(d-k) is even or k=0. Along the proof we obtain three results of independent interest: We present two alternative proofs for the special case k=0 (our optimal colored Tverberg theorem (2009)), calculate the cohomological index for joins of chessboard complexes, and establish a new Borsuk-Ulam type theorem for (Z_p)^m-equivariant bundles that generalizes results of Volovikov (1996) and Zivaljevic (1999).

A tight colored Tverberg theorem for maps to manifolds (Extended abstract)

Pavle V. M. Blagojević and Benjamin Matschke and Günter M. Ziegler

Erschienen in: Proc.\ FPSAC 2011 (Reykjaví k, Iceland), Discrete Mathematics and Theoretical Computer Science (DMTCS), http://www.dmtcs.org, volume AO, pages 183-190

Polytopes with low-dimensional realization spaces (joint work with Karim Adiprasito)

Günter M. Ziegler

Erschienen in: Oberwolfach Reports, volume 8, pages 2522-2525

Polyhedral surfaces in wedge products

Thilo Rörig and Günter M. Ziegler

Erschienen in: Geometriae Dedicata, volume 151, pages 155-173

http://arxiv.org/abs/0908.3159v1http://link.springer.com/article/10.1007 ...

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 especially interesting: The wedge products of polygons with simplices contain certain combinatorially regular polyhedral surfaces as subcomplexes. These generalize known classes of surfaces ``of unusually large genus'' that first appeared in works by Coxeter (1937), Ringel (1956), and McMullen, Schulz, and Wills (1983). Via ``projections of deformed wedge products'' we obtain realizations of some of the surfaces in the boundary complexes of 4-polytopes, and thus in R^3. As additional benefits our construction also yields polyhedral subdivisions for the interior and the exterior, as well as a great number of local deformations (``moduli'') for the surfaces in R^3. In order to prove that there are many moduli, we introduce the concept of ``affine support sets'' in simple polytopes. Finally, we explain how duality theory for 4-dimensional polytopes can be exploited in order to also realize combinatorially dual surfaces in R^3 via dual 4-polytopes.

The ideal-valued index for a dihedral group action, and mass partition by two hyperplanes

Pavle V. M. Blagojević and Günter M. Ziegler

Erschienen in: Topology and its Applications (Proc.\ ATA2010), volume 158, pages 1326-1351

http://arxiv.org/abs/0704.1943v4http://www.sciencedirect.com/science/art ...

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 established bounds based on one of the maximal abelian subgroups of D_8.

Projecting lattice polytopes without interior lattice points

Benjamin Nill and Günter M. Ziegler

Erschienen in: Math. of Operations Research, volume 36, pages 462-467

http://arxiv.org/abs/1101.4292v2http://mor.journal.informs.org/content/3 ...

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 show that in dimension four and higher some of these finitely many polytopes are not maximal as convex bodies without interior lattice points.

Eulers Polyederformel und die Arithmetisierung der Gestalt

Günter M. Ziegler and Christian Blatter

Berlin: Akademie-Verlag | 2010

Erschienen in: Mathesis & Graphé. Leonhard Euler und die Entfaltung der Wissenssysteme, pages 243-256

http://www.math.ethz.ch/~blatter/Mathesi ...

Spheres in the Computer---the Kepler Conjecture

Martin Henk and Günter M. Ziegler

Providence, RI: Amer. Math. Soc. | 2010

Erschienen in: Mathematics Everywhere, pages 143-164

Convex Polytopes: Examples and Conjectures (Notes by Vincent Pilaud)

Günter M. Ziegler

Erschienen in: Doc Course Combinatorics and Geometry 2009 "Discrete and Computational Geometry'', CRM Documents, volume 5.1, pages 9-49

3N bunte Punkte in der Ebene

Günter M. Ziegler

Erschienen in: Mitteilungen der DMV, volume 18, pages 164-170

http://page.math.tu-berlin.de/~mdmv/arch ...

Construction and analysis of projected deformed products

Raman Sanyal and Günter M. Ziegler

Erschienen in: Discrete Comput. Geometry, volume 43, pages 412-435

http://arxiv.org/abs/0710.2162v1http://link.springer.com/article/10.1007 ...

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 a neighborly cubical d-polytope. As an extension of thecubical case, we construct matrix representations of deformed products of(even) polygons (DPPs), which have a projection to d-space that retains the complete (\lfloor \tfrac{d}{2} \rfloor - 1)-skeleton. In both cases the combinatorial structure of the images under projection is completely determined by the neighborly polytope Q: Our analysis provides explicit combinatorial descriptions. This yields a multitude of combinatorially different neighborly cubical polytopes and DPPs. As a special case, we obtain simplified descriptions of the neighborly cubical polytopes of Joswig & Ziegler (2000) as well as of the ``projected deformed products of polygons'' that were announced by Ziegler (2004), a family of 4-polytopes whose ``fatness'' gets arbitrarily close to 9.

Die Rätselseite: Zehn bunte Punkte in der Ebene

Benjamin Matschke and Günter M. Ziegler

Erschienen in: Mitteilungen der DMV, volume 18, pages 171

http://page.math.tu-berlin.de/~mdmv/arch ...

Kugeln im Computer --- Die Kepler-Vermutung

Martin Henk and Günter M. Ziegler

Wiesbaden: Vieweg+Teubner | 2009

Erschienen in: Alles Mathematik. Von Pythagoras zum CD-Player, pages 177-201

http://link.springer.com/chapter/10.1007 ...

Linear programming via zonotopes is exponential

Thilo Rörig and Nikolaus Witte and Günter M. Ziegler

Erschienen in: Discrete Comput.\ Geometry, volume 42, pages 527-541

On Kalai's conjectures about centrally symmetric polytopes

Raman Sanyal and Axel Werner and Günter M. Ziegler

Erschienen in: Discrete Comput.\ Geometry, volume 41, pages 183-198

http://arxiv.org/abs/0708.3661v2http://link.springer.com/article/10.1007 ...

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.

Tetrahedra on deformed spheres and integral group cohomology

Pavle V. M. Blagojević and Günter M. Ziegler

Erschienen in: Electronic J. Combinatorics, volume 16(2) (Björner Festschrift

http://arxiv.org/abs/0808.3841v1

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 integer coefficients yield results that cannot be accessed using only field coefficients.

Combinatorial Stokes formulas via minimal resolutions

Bernhard Hanke and Raman Sanyal and Carsten Schultz and Günter M. Ziegler

Erschienen in: J. Combinatorial Theory, Ser.~A, volume 116, pages 404-420

http://arxiv.org/abs/0710.0050v1

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 with methods from equivariant topology. The special case k=2 for this is classical; it involves Tucker's (1949) combinatorial lemma which implies the Borsuk-Ulam theorem, its proof via chain complexes by Lefschetz (1949), the combinatorial Stokes formula of Fan (1967), and Meunier's work (2006).

Zonotopes with large 2D-cuts

Thilo Rörig and Nikolaus Witte and Günter M. Ziegler

Erschienen in: EG-Models, http://www.eg-models.de/

http://www.eg-models.de/models/Polytopes ...

A small polyhedral Z-acyclic 2-complex in R^4

Frank Lutz and Günter M. Ziegler

Erschienen in: EG-Models, http://www.eg-models.de/

http://www.eg-models.de/models/Polytopal ...

Das Jahrhundert der Mathematik

Günter M. Ziegler

Wiesbaden: Vieweg | 2008

Erschienen in: Berufs- und Karriere-Planer Mathematik 2008, pages 36-41

La congettura di Keplero

Martin Henk and Günter M. Ziegler

Torino: Einaudi | 2008

Erschienen in: La matematica. Problemi e teoremi, volume II, pages 765-792

On the number of simplicial 3-spheres and 4-polytopes with N facets (joint work with Bruno Benedetti)

Günter M. Ziegler

Erschienen in: Oberwolfach Reports, volume 5, pages 2512-2514

Polyhedral surfaces of high genus

Günter M. Ziegler

Basel: Birkhäuser | 2008

Erschienen in: Discrete Differential Geometry, Oberwolfach Seminars, volume 38, pages 191-213

http://arxiv.org/abs/math/0412093v1http://link.springer.com/chapter/10.1007 ...

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 with n vertices the maximal genus is not known. The current record is g ~ n log n, due to McMullen, Schulz & Wills (1983). We present these surfaces with a new construction: We find them in Schlegel diagrams of ``neighborly cubical 4-polytopes,'' as constructed by Joswig & Ziegler (2000).

π & Co. Kaleidoskop der Mathematik

Editor: Ehrhard Behrends and Peter Gritzmann and Günter M. Ziegler

Heidelberg: Springer | 2008

http://www.springer.com/mathematics/book ...

Non-rational configurations, polytopes, and surfaces

Günter M. Ziegler

Erschienen in: Mathematical Intelligencer, volume 30, pages 36-42

http://arXiv.org/abs/0710.4453http://download.springer.com/static/pdf/ ...

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 polyhedral surfaces in 3-space, a discovery by Ulrich Brehm from 1997. His construction also starts from any non-rational point configuration in the plane, and then performs what one should call Brehm extensions, in order to obtain non-rational partial surfaces. These examples and objects are first mile stones on the way to the remarkable "universality theorems'' for polytopes and for polyhedral surfaces by Mn\"ev (1986), Richter-Gebert (1994), and Brehm (1997).

Discrete Differential Geometry

Editor: Alexander I. Bobenko and Peter Schröder and John M. Sullivan and Günter M. Ziegler

Basel: Birkhäuser | 2008

Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions

Günter M. Ziegler

Springer-Verlag | 2007

Erschienen in: Computational Discrete Mathematics Lectures, Lecture Notes in Computer Science, volume 2122, pages 159-171

http://link.springer.com/chapter/10.1007 ...

Convex Polytopes: Extremal constructions and f-vector shapes

Günter M. Ziegler

Providence, RI: Amer. Math. Society | 2007

Erschienen in: "Geometric Combinatorics'', Proc. Park City Mathematical Institute (PCMI) 2004, pages 617-691

http://arxiv.org/abs/math/0411400v2http://page.mi.fu-berlin.de/gmziegler/ft ...

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 for 2-simple 2-simplicial 4-polytopes, which have symmetric f-vectors. Lecture 4 sketches the geometry of the cone of f-vectors for 4-polytopes, and thus identifies the existence/construction of 4-polytopes of high ``fatness'' as a key problem. In this direction, the last lecture presents a very recent construction of ``projected products of polygons,'' whose fatness reaches 9-\eps.

Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions

Günter M. Ziegler

Springer-Verlag | 2007

Erschienen in: Computational Discrete Mathematics Lectures, Lecture Notes in Computer Science, volume 2122, pages 159-171

http://link.springer.com/chapter/10.1007 ...

On the existence of crepant resolutions of Gorenstein abelian quotient singularities in dimensions >=4

Dimitrios Dais and Martin Henk and Günter M. Ziegler

Providence, RI: Amer. Math. Soc. | 2007

Erschienen in: Algebraic and Geometric Combinatorics (Proc.\ Anogia, August 2005), Contemporary Math., volume 423, pages 125-204

http://arXiv.org/abs/math/0512619

For which finite subgroups G of SL(r,C), r \geq 4, are there crepant desingularizations of the quotient space C^r/G? A complete answer to this question (also known as "Existence Problem" for such desingularizations) would classify all those groups for which the high-dimensional versions of McKay correspondence are valid. In the paper we consider this question in the case of abelian finite subgroups of SL(r,C) by using techniques from toric and discrete geometry. We give two necessary existence conditions, involving the Hilbert basis elements of the cone supporting the junior simplex, and an Upper Bound Theorem, respectively. Moreover, to the known series of Gorenstein abelian quotient singularities admitting projective, crepant resolutions (which are briefly recapitulated) we add a new series of non-c.i. cyclic quotient singularities having this property.

On generalized Kneser hypergraph colorings

Carsten Lange and Günter M. Ziegler

Erschienen in: J. Combinatorial Theory, Ser.~A, volume 114, pages 159-166

http://arxiv.org/abs/math/0504607v2http://link.springer.com/article/10.1007 ...

In Ziegler (2002), the second author presented a lower bound for the chromatic numbers of hypergraphs $\KG{r}{\pmb s}{\calS}$, "generalized $r$-uniform Kneser hypergraphs with intersection multiplicities $\pmb s$." It generalized previous lower bounds by Kriz (1992/2000) for the case ${\pmb s}=(1,...,1)$ without intersection multiplicities, and by Sarkaria (1990) for $\calS=\tbinom{[n]}k$. Here we discuss subtleties and difficulties that arise for intersection multiplicities $s_i>1$: 1. In the presence of intersection multiplicities, there are two different versions of a "Kneser hypergraph," depending on whether one admits hypergraph edges that are multisets rather than sets. We show that the chromatic numbers are substantially different for the two concepts of hypergraphs. The lower bounds of Sarkaria (1990) and Ziegler (2002) apply only to the multiset version. 2. The reductions to the case of prime $r$ in the proofs Sarkaria and by Ziegler work only if the intersection multiplicities are strictly smaller than the largest prime factor of $r$. Currently we have no valid proof for the lower bound result in the other cases. We also show that all uniform hypergraphs without multiset edges can be represented as generalized Kneser hypergraphs.

Polyhedral Surfaces in Wedge Products (joint work with Raman Sanyal and Günter M. Ziegler)

Thilo Rörig

Erschienen in: Oberwolfach Reports, volume 4, pages 244-247

http://arxiv.org/abs/0908.3159v1http://page.math.tu-berlin.de/~thilosch/ ...

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 especially interesting: The wedge products of polygons with simplices contain certain combinatorially regular polyhedral surfaces as subcomplexes. These generalize known classes of surfaces ``of unusually large genus'' that first appeared in works by Coxeter (1937), Ringel (1956), and McMullen, Schulz, and Wills (1983). Via ``projections of deformed wedge products'' we obtain realizations of some of the surfaces in the boundary complexes of 4-polytopes, and thus in R^3. As additional benefits our construction also yields polyhedral subdivisions for the interior and the exterior, as well as a great number of local deformations (``moduli'') for the surfaces in R^3. In order to prove that there are many moduli, we introduce the concept of ``affine support sets'' in simple polytopes. Finally, we explain how duality theory for 4-dimensional polytopes can be exploited in order to also realize combinatorially dual surfaces in R^3 via dual 4-polytopes.

Euler's polyhedron formula as a starting point for modern polytope theory

Günter M. Ziegler and Christian Blatter

Erschienen in: Elemente Math., volume 62, pages 184-192

Generalized Kneser coloring theorems with combinatorial proofs (Erratum)

Günter M. Ziegler

Erschienen in: Inventiones math., volume 163, pages 227-228

Singular 0/1-matrices, and the hyperplanes spanned by random 0/1-vectors

Thomas Voigt and Günter M. Ziegler

Erschienen in: Combinatorics, Probability & Computing, volume 15, pages 463-471

http://arxiv.org/abs/math/0308050v3

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 experiments pertaining to these numbers.

Das Jahrhundert der Mathematik

Günter M. Ziegler

Wiesbaden: Vieweg | 2006

Erschienen in: Berufs- und Karriere-Planer Mathematik 2006, pages 36-42

Combinatorial and polyhedral surfaces (joint work with Raman Sanyal and Thilo Schröder)

Günter M. Ziegler

Erschienen in: Oberwolfach Reports, volume 3, pages 14-17

The simplex algorithm in dimension three

Volker Kaibel and Rafael Mechtel and Micha Sharir and Günter M. Ziegler

Erschienen in: SIAM J. Computing, volume 34, pages 475--497

http://arxiv.org/abs/math/0309351v2

We investigate the worst-case behavior of the simplex algorithm on linear programs with three variables, that is, on 3-dimensional simple polytopes. Among the pivot rules that we consider, the ``random edge'' rule yields the best asymptotic behavior as well as the most complicated analysis. All other rules turn out to be much easier to study, but also produce worse results: Most of them show essentially worst-possible behavior; this includes both Kalai's ``random-facet'' rule, which without dimension restriction is known to be subexponential, as well as Zadeh's deterministic history dependent rule, for which no non-polynomial instances in general dimensions have been found so far.

Bier spheres and posets

Anders Björner and Andreas Paffenholz and Jonas Sjöstrand and Günter M. Ziegler

Erschienen in: Discrete & Computational Geometry, volume 34, pages 71-86

http://arxiv.org/abs/math/0311356v2

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 length. In the case of face posets of PL spheres this yields cellular "generalized Bier spheres." In the case of Eulerian or Cohen-Macaulay posets P we show that the Bier posets Bier(P,I) inherit these properties. In the boolean case originally considered by Bier, we show that all the spheres produced by his construction are shellable, which yields "many shellable spheres", most of which lack convex realization. Finally, we present simple explicit formulas for the g-vectors of these simplicial spheres and verify that they satisfy a strong form of the g-conjecture for spheres.

The Topological Tverberg Problem and winding numbers

Torsten Schöneborn and Günter M. Ziegler

Erschienen in: J. Combinatorial Theory, Ser.~A, volume 112, pages 82-104

http://arxiv.org/abs/math/0409081v2http://www.sciencedirect.com/science/art ...

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 partitions'' arise if and only if there are ``many q-winding partitions.'' The d=2 case of the Winding Number Conjecture is a problem about drawings of the complete graphs K_{3q-2} in the plane. We investigate graphs that are minimal with respect to the winding number condition.

A cubical 4-polytope with an odd number of facets

Alexander Schwartz and Günter M. Ziegler

Erschienen in: EG-Models, http://www.eg-models.de

http://www.eg-models.de/models/Polytopes ...

Projected polytopes, Gale diagrams, and polyhedral surfaces (joint work with Raman Sanyal and Thilo Schröder)

Günter M. Ziegler

Erschienen in: Oberwolfach Reports, volume 2, pages 986-989

Topological lower bounds for the chromatic number: A~hierarchy

Jiří Matoušek and Günter M. Ziegler

Erschienen in: Jahresbericht der DMV, volume 106, pages 71-90

http://arxiv.org/abs/math/0208072v3http://page.mi.fu-berlin.de/gmziegler/ft ...

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, Schrijver, Dolnikov, Sarkaria, Kriz, Greene, and others), all of them based on some version of the Borsuk--Ulam theorem, but otherwise quite different. Each can be extended to yield some lower bound on the chromatic number of an arbitrary graph. (Indeed, we observe that \emph{every} finite graph may be represented as a generalized Kneser graph, to which the above bounds apply.) We show that these bounds are almost linearly ordered by strength, the strongest one being essentially Lov\'asz' original bound in terms of a neighborhood complex. We also present and compare various definitions of a \emph{box complex} of a graph (developing ideas of Alon, Frankl, and Lov\'asz and of \kriz). A suitable box complex is equivalent to Lov\'asz' complex, but the construction is simpler and functorial, mapping graphs with homomorphisms to $\Z_2$-spaces with $\Z_2$-maps.

Typical and extremal linear programs

Günter M. Ziegler

Erschienen in: The Sharpest Cut: The Impact of Manfred Padberg and His Work, MPS-SIAM Series on Optimization, volume 4, pages 217-230

http://epubs.siam.org/doi/abs/10.1137/1. ...

Convex hulls, oracles, and homology

Michael Joswig and Günter M. Ziegler

Erschienen in: J. Symbolic Computation (special issue for ICMS 2002), volume 38, pages 1247-1259

http://arxiv.org/abs/math/0301100v1http://www.sciencedirect.com/science/art ...

This paper presents a new algorithm for the convex hull problem, which is based on a reduction to a combinatorial decision problem POLYTOPE-COMPLETENESS-COMBINATORIAL, which in turn can be solved by a simplicial homology computation. Like other convex hull algorithms, our algorithm is polynomial (in the size of input plus output) for simplicial or simple input. We show that the ``no''-case of POLYTOPE-COMPLETENESS-COMBINATORIAL has a certificate that can be checked in polynomial time (if integrity of the input is guaranteed).

A cubical 4-polytope with a dual Klein bottle

Alexander Schwartz and Günter M. Ziegler

Erschienen in: EG-Models, http://www.eg-models.de

http://www.eg-models.de/models/Polytopes ...

Construction techniques for cubical complexes, odd cubical 4-polytopes, and prescribed dual manifolds

Alexander Schwartz and Günter M. Ziegler

Erschienen in: Experimental Math., volume 13, pages 385-413

http://arxiv.org/abs/math/0310269v3https://eudml.org/doc/53092

We provide a number of new construction techniques for cubical complexes and cubical polytopes, and thus for cubifications (hexahedral mesh generation). As an application we obtain an instance of a cubical 4-polytope that has a non-orientable dual manifold (a Klein bottle). This confirms an existence conjecture of Hetyei (1995). More systematically, we prove that every normal crossing codimension one immersion of a compact 2-manifold into R^3 PL-equivalent to a dual manifold immersion of a cubical 4-polytope. As an instance we obtain a cubical 4-polytope with a cubation of Boy's surface as a dual manifold immersion, and with an odd number of facets. Our explicit example has 17 718 vertices and 16 533 facets. Thus we get a parity changing operation for 3-dimensional cubical complexes (hexa meshes); this solves problems of Eppstein, Thurston, and others.

Basic properties of convex polytopes

Martin Henk and Jürgen Richter-Gebert and Günter M. Ziegler

Boca Raton: Chapman & Hall/CRC Press | 2004

Erschienen in: Handbook of Discrete and Computational Geometry, pages 355-382

http://fma2.math.uni-magdeburg.de/~henk/ ...

The E_t-construction for lattices, spheres and polytopes

Andreas Paffenholz and Günter M. Ziegler

Erschienen in: Discrete & Computational Geometry (Billera Festschrift: M. Bayer, C. Lee, B. Sturmfels, eds.), volume 32, pages 601-624

http://arxiv.org/abs/math/0304492v2

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 and Ziegler. We also construct for each $d\ge3$ an infinite family of $(d-2)$-simplicial 2-simple $d$-polytopes, thus solving a problem of Gr\"unbaum.

Many triangulated 3-spheres

Julian Pfeifle and Günter M. Ziegler

Erschienen in: Mathematische Annalen, volume 330, pages 829-837

http://arxiv.org/abs/math/0212004v2http://link.springer.com/article/10.1007 ...

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 >= 4.

Projected Products of Polygons

Günter M. Ziegler

Erschienen in: Electronic Research Announcements AMS, volume 10, pages 122-134

http://arXiv.org/abs/math/0407042http://www.ams.org/journals/era/2004-10- ...

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.

Kissing numbers, sphere packings and some unexpected proofs

Florian Pfender and Günter M. Ziegler

Erschienen in: Notices of the AMS, volume 51, pages 873-883

http://www.ams.org/notices/200408/fea-pf ...

Kissing numbers: Surprises in Dimension four

Günter M. Ziegler

Erschienen in: MSRI Emissary, pages 4--5

On the Monotone Upper Bound Problem

Julian Pfeifle and Günter M. Ziegler

Erschienen in: Experimental Math., volume 13, pages 1-11

http://arxiv.org/abs/math/0308186v1http://projecteuclid.org/DPubS?service=U ...

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)<=M_{ubt}(d,n) provided by McMullen's (1970) Upper Bound Theorem is tight, where M_{ubt}(d,n) is the number of vertices of a dual-to-cyclic d-polytope with n facets. It was recently shown that the upper bound M(d,n)<=M_{ubt}(d,n) holds with equality for small dimensions (d<=4: Pfeifle, 2003) and for small corank (n<=d+2: G\"artner et al., 2001). Here we prove that it is not tight in general: In dimension d=6 a polytope with n=9 facets can have M_{ubt}(6,9)=30 vertices, but not more than 26 <= M(6,9) <= 29 vertices can lie on a strictly-increasing edge-path. The proof involves classification results about neighborly polytopes, Kalai's (1988) concept of abstract objective functions, the Holt-Klee conditions (1998), explicit enumeration, Welzl's (2001) extended Gale diagrams, randomized generation of instances, as well as non-realizability proofs via a version of the Farkas lemma.

The Great Prime Number Record Races

Günter M. Ziegler

Erschienen in: Notices of the AMS, volume 51, pages 414--416

http://www.ams.org/notices/200404/comm-z ...

Oriented matroids

Jürgen Richter-Gebert and Günter M. Ziegler

Boca Raton: Chapman & Hall/CRC Press | 2004

Erschienen in: Handbook of Discrete and Computational Geometry, pages 129-151

http://www2.lirmm.fr/~sol/Rapports/Refer ...

Das Jahrhundert der Mathematik

Günter M. Ziegler

Wiesbaden: Vieweg | 2003

Erschienen in: Berufs- und Karriere-Planer Mathematik 2003, pages 36-41

Primzahl-Rekordjagd

Günter M. Ziegler

Erschienen in: Mitteilungen der DMV, pages 5--7

Fat 4-polytopes and fatter 3-spheres

David Eppstein and Greg Kuperberg and Günter M. Ziegler

New York: Marcel Dekker Inc. | 2003

Erschienen in: Discrete Geometry: In honor of W. Kuperberg's 60th birthday, Pure and Applied Mathematics, volume 253, pages 239--265

http://arxiv.org/abs/math/0204007v3

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 show that fatness is not bounded for the more general class of strongly regular CW decompositions of the 3-sphere.

Convex Polytopes

Branko Grünbaum (2nd Edition editited by Volker Kaibel, Victor Klee and Günter M. Ziegler)

New York: Springer-Verlag | 2003

http://www.springer.com/mathematics/geom ...

Brillanten für das "BUCH der Beweise''

Martin Aigner and Günter M. Ziegler

Munich/München: Math.\ Dept., Ludwigs-Maximilians University | 2003

Erschienen in: ~mathe-lmu.de, volume No.~7, pages 22-28

Geometrie zum Anfassen: Kachelungen und Polyeder

Günter M. Ziegler

Hildesheim und Berlin: Verlag Franzbecker | 2003

Erschienen in: Beiträge zum Mathematikunterricht 2003. Vorträge auf der 37. Tagung für Didaktik der Mathematik vom 3. bis 7. März 2003 in Dortmund, pages 41-48

Counting lattice triangulations

Volker Kaibel and Günter M. Ziegler

Cambridge University Press | 2003

Erschienen in: Surveys in Combinatorics 2003, London Math. Society Lecture Notes Series, pages 277-307

http://arxiv.org/abs/math/0211268v2

We discuss the problem to count, or, more modestly, to estimate the number f(m,n) of unimodular triangulations of the planar grid of size $m\times n$. Among other tools, we employ recursions that allow one to compute the (huge) number of triangulations for small m and rather large n by dynamic programming; we show that this computation can be done in polynomial time if m is fixed, and present computational results from our implementation of this approach. We also present new upper and lower bounds for large m and n, and we report about results obtained from a computer simulation of the random walk that is generated by flips.

A counterexample to the Perles conjecture

Nikolaus Witte

Erschienen in: EG-Models, http://www.eg-models.de

http://www-sfb288.math.tu-berlin.de/eg-m ...

On orbit configuration spaces of spheres

Eva Maria Feichtner and Günter M. Ziegler

Erschienen in: Topology and its Applications (Proc.\ "Arrangements in Boston'': A.~Suciu, D. Cohen, eds.), volume 118, pages 85-102

http://www.sciencedirect.com/science/art ...

Generalized Kneser coloring theorems with combinatorial proofs

Günter M. Ziegler

Erschienen in: Inventiones math., volume 147, pages 671-691

http://arxiv.org/abs/math/0103146v1

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 by (hyper)graph coloring theorems of Dol'nikov, Alon-Frankl-Lov\'asz, Sarkaria, and Kriz. We also give a combinatorial proof of Schrijver's theorem.

Kugeln im Computer --- Die Kepler-Vermutung

Martin Henk and Günter M. Ziegler

Wiesbaden: Vieweg | 2002

Erschienen in: Alles Mathematik. Von Pythagoras zum CD-Player, pages 153-175

http://link.springer.com/chapter/10.1007 ...

Examples and counterexamples for the Perles conjecture

Christian Haase and Günter M. Ziegler

Erschienen in: Discrete & Computational Geometry, volume 28, pages 29-44

http://arxiv.org/abs/math/0011170v2

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 the graph of a simple d-polytope are exactly all the (d-1)-regular, connected, induced, non-separating subgraphs'' [Perles 1970]. We give examples for the validity of Perles conjecture: In particular, it holds for the duals of cyclic polytopes, and for the duals of stacked polytopes. On the other hand, we identify a topological obstruction that must be present in any counterexample to Perles' conjecture; thus, starting with a modification of ``Bing's house'', we construct explicit 4-dimensional counterexamples.

Face Numbers of 4-Polytopes and 3-Spheres

Günter M. Ziegler

Beijing, China: Higher Education Press | 2002

Erschienen in: Proceedings of the International Congress of Mathematicians (ICM 2002, Beijing), volume III, pages 625-634

http://arxiv.org/abs/math/0208073v2

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 differentiate between the cones of f- or flag-vectors of -- connected Eulerian lattices of length 5 (combinatorial objects), -- strongly regular CW 3-spheres (topological objects), -- convex 4-polytopes (discrete geometric objects), and -- rational convex 4-polytopes (whose study involves arithmetic aspects). Further progress will depend on the derivation of tighter f-vector inequalities for convex 4-polytopes. On the other hand, we will need new construction methods that produce interesting polytopes which are far from being simplicial or simple -- for example, very ``fat'' or ``complex'' 4-polytopes. In this direction, I will report about constructions (from joint work with Michael Joswig, David Eppstein and Greg Kuperberg) that yield -- strongly regular CW 3-spheres of arbitrarily large fatness, -- convex 4-polytopes of fatness larger than 5.048, and -- rational convex 4-polytopes of fatness larger than 5-epsilon.

Questions about polytopes

Günter M. Ziegler

Berlin Heidelberg: Springer-Verlag | 2001

Erschienen in: Mathematics Unlimited -- 2001 and Beyond, pages 1195-1211

Das Jahrhundert der Mathematik

Günter M. Ziegler

Wiesbaden: Vieweg | 2001

Erschienen in: Berufs- und Karriere-Planer Mathematik 2001, pages 18-23

Zonotopes associated with higher Bruhat orders

Stefan Felsner and Günter M. Ziegler

Erschienen in: Discrete Mathematics (Tverberg Festschrift: B. Lindström, J. Zaks, eds.), volume 241, pages 301-312

http://www.sciencedirect.com/science/art ...

Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions

Günter M. Ziegler

Springer-Verlag | 2001

Erschienen in: Computational Discrete Mathematics Lectures, Lecture Notes in Computer Science, volume 2122, pages 159-171

http://link.springer.com/chapter/10.1007 ...

Vertex-facet incidences of unbounded polyhedra

Michael Joswig and Volker Kaibel and Marc E. Pfetsch and Günter M. Ziegler

Erschienen in: Advances in Geometry, volume 1, pages 23-36

http://arxiv.org/abs/math/0006225v1http://www.degruyter.com/view/j/advg.200 ...

How much of the combinatorial structure of a pointed polyhedron is contained in its vertex-facet incidences? Not too much, in general, as we demonstrate by examples. However, one can tell from the incidence data whether the polyhedron is bounded. In the case of a polyhedron that is simple and "simplicial," i.e., a d-dimensional polyhedron that has d facets through each vertex and d vertices on each facet, we derive from the structure of the vertex-facet incidence matrix that the polyhedron is necessarily bounded. In particular, this yields a characterization of those polyhedra that have circulants as vertex-facet incidence matrices.

"Der diskrete Charme der Geometrie''

Günter M. Ziegler

Erschienen in: http://www.mathematik.de

http://www.mathematik.de/ger/information ...

All toric local complete intersection singularities admit projective crepant resolutions

Dimitrios I. Dais and Christian Haase and Günter M. Ziegler

Erschienen in: Tohoku Math. Journal, volume 53, pages 95-107

http://arxiv.org/abs/math/9812025v2http://projecteuclid.org/DPubS?service=U ...

It is known that the underlying spaces of all abelian quotient singularities which are embeddable as complete intersections of hypersurfaces in an affine space can be overall resolved by means of projective torus-equivariant crepant birational morphisms in all dimensions. In the present paper we extend this result to the entire class of toric l.c.i.-singularities. Our proof makes use of Nakajima's classification theorem and of some special techniques from toric and discrete geometry.

A Neighborly Cubical 4-Polytope

Michael Joswig and Günter M. Ziegler

Erschienen in: EG-Models, http://www.eg-models.de

Polytopes --- Combinatorics and Computation

Editor: Gil Kalai and Günter M. Ziegler

Basel: Birkhäuser-Verlag | 2000

Erschienen in: DMV Seminars, volume 29, pages 1-4

Kugeln im Computer --- Die Kepler-Vermutung

Martin Henk and Günter M. Ziegler

Wiesbaden: Vieweg | 2000

Erschienen in: Alles Mathematik. Von Pythagoras zum CD-Player, pages 121-143

http://link.springer.com/chapter/10.1007 ...

Neighborly cubical polytopes

Michael Joswig and Günter M. Ziegler

Erschienen in: Discrete & Computational Geometry (Grünbaum Festschrift: G. Kalai, V. Klee, eds.), volume (2-3)24, pages 325-344

http://arxiv.org/abs/math/9812033v2

Neighborly cubical polytopes exist: for any $n\ge d\ge 2r+2$, there is a cubical convex d-polytope $C^n_d$ whose $r$-skeleton is combinatorially equivalent to that of the $n$-dimensional cube. This solves a problem of Babson, Billera & Chan. Kalai conjectured that the boundary $\partial C^n_d$ of a neighborly cubical polytope $C^n_d$ maximizes the $f$-vector among all cubical $(d-1)$-spheres with $2^n$ vertices. While we show that this is true for polytopal spheres for $n\le d+1$, we also give a counter-example for $d=4$ and $n=6$. Further, the existence of neighborly cubical polytopes shows that the graph of the $n$-dimensional cube, where $n\ge5$, is ``dimensionally ambiguous'' in the sense of Gr\"unbaum. We also show that the graph of the 5-cube is ``strongly 4-ambiguous''. In the special case $d=4$, neighborly cubical polytopes have $f_3=f_0/4 \log_2 f_0/4$ vertices, so the facet-vertex ratio $f_3/f_0$ is not bounded; this solves a problem of Kalai, Perles and Stanley studied by Jockusch.

The integral cohomology algebras of ordered configuration spaces of spheres

Eva Maria Feichtner and Günter M. Ziegler

Erschienen in: Documenta Math., volume 5, pages 115-139

http://www.math.uiuc.edu/documenta/vol-0 ...

On cohomology algebras of complex subspace arrangements

Eva Maria Feichtner and Günter M. Ziegler

Erschienen in: Transactions of the American Mathematical Society, volume 352, pages 3523-3555

http://www.ams.org/journals/tran/2000-35 ...

Sharir's cube

Günter M. Ziegler

Erschienen in: EG-Models, http://www.eg-models.de

Lectures on 0/1-polytopes

Günter M. Ziegler

Basel: Birkhäuser-Verlag | 2000

Erschienen in: Polytopes --- Combinatorics and Computation, DMV Seminars, volume 29, pages 1-41

http://arxiv.org/abs/math/9909177v1

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 that is derived from the analysis of examples in ``low dimensions'' will miss the true complexity of 0/1-polytopes. Thus, in the following we will study several aspects of the complexity of higher-dimensional 0/1-polytopes: the doubly-exponential number of combinatorial types, the number of facets which can be huge, and the coefficients of defining inequalities which sometimes turn out to be extremely large. Some of the effects and results will be backed by proofs in the course of these lectures; we will also be able to verify some of them on explicit examples, which are accessible as a {\tt polymake} database.

Ambiguous Incidences of Unbounded Polyhedra

Michael Joswig and Volker Kaibel and Marc E. Pfetsch and Günter M. Ziegler

Erschienen in: EG-Models, http://www.eg-models.de

http://www.eg-models.de/models/Polytopes ...

Decompositions of simplicial balls and spheres with knots consisting of few edges

Masahiro Hachimori and Günter M. Ziegler

Erschienen in: Mathematische Zeitschrift, volume 235, pages 159-171

http://link.springer.com/article/10.1007 ...

On the maximal width of empty lattice simplices

Christian Haase and Günter M. Ziegler

Erschienen in: European J. Combinatorics, volume 21, pages 111-119

http://www.sciencedirect.com/science/art ...

A census of flag-vectors of 4-polytopes

Andrea Höppner and Günter M. Ziegler

Basel: Birkhäuser-Verlag | 2000

Erschienen in: Polytopes --- Combinatorics and Computation, DMV Seminars, volume 29, pages 105-110

http://link.springer.com/chapter/10.1007 ...

Hilbert bases, unimodular triangulations, and binary covers of rational polyhedral cones

Robert T. Firla and Günter M. Ziegler

Erschienen in: Discrete & Computational Geometry, volume 21, pages 205-216

http://link.springer.com/article/10.1007 ...

Homotopy colimits -- comparison lemmas for combinatorial applications

Volkmar Welker and Günter M. Ziegler and Jade T. Živaljević

Erschienen in: Journal für die Reine und Angewandte Mathematik (Crelles Journal), volume 509, pages 117-149

https://www.google.com/url?sa=t&rct=j&q= ...

Oriented Matroids

Anders Björner and Michel Las Vergnas and Bernd Sturmfels and Neil White and Günter M. Ziegler

Cambridge: Cambridge University Press | 1999

Gröbner bases and integer programming

Günter M. Ziegler

Heidelberg Berlin: Springer-Verlag | 1999

Erschienen in: Some Tapas of Computer Algebra, pages 168-183

Methoden der Kombinatorischen Geometrie "im Einsatz''

Günter M. Ziegler

Erschienen in: Mathematische Semesterberichte, volume 46, pages 187-203

http://link.springer.com/article/10.1007 ...

Deformed products and maximal shadows

Nina Amenta and Günter M. Ziegler

Providence RI: Amer. Math. Soc. | 1998

Erschienen in: Advances in Discrete and Computational Geometry (South Hadley, MA, 1996), Contemporary Mathematics, volume 223, pages 57-90

https://www.google.com/url?sa=t&rct=j&q= ...

Recent progress on polytopes

Günter M. Ziegler

Providence RI: Amer. Math. Soc. | 1998

Erschienen in: Advances in Discrete and Computational Geometry, Contemporary Mathematics, volume 223, pages 395-406

Shelling polyhedral 3-balls and 4-polytopes

Günter M. Ziegler

Erschienen in: Discrete & Computational Geometry, volume 19, pages 159-174

http://link.springer.com/article/10.1007 ...

All abelian quotient c.i.-singularities admit projective crepant resolutions in all dimensions

Dimitrios I. Dais and Martin Henk and Günter M. Ziegler

Erschienen in: Advances in Mathematics, volume 139, pages 194-239

http://arxiv.org/abs/alg-geom/9704007v1

For Gorenstein quotient spaces $C^d/G$, a direct generalization of the classical McKay correspondence in dimensions $d\geq 4$ would primarily demand the existence of projective, crepant desingularizations. Since this turned out to be not always possible, Reid asked about special classes of such quotient spaces which would satisfy the above property. We prove that the underlying spaces of all Gorenstein abelian quotient singularities, which are embeddable as complete intersections of hypersurfaces in an affine space, have torus-equivariant projective crepant resolutions in all dimensions. We use techniques from toric and discrete geometry.

Shellability of complexes of trees

Henryk Trappmann and Günter M. Ziegler

Erschienen in: J. Combinatorial Theory, Ser.~A, volume 82, pages 168-178

http://www.sciencedirect.com/science/art ...

Randomized simplex algorithms on Klee-Minty cubes

Bernd Gärtner and Martin Henk and Günter M. Ziegler

Erschienen in: Combinatorica, volume 18, pages 349-372

http://people.inf.ethz.ch/~gaertner/text ...

[The Mathematics of Convex Polytopes]

Günter M. Ziegler

Tokyo: Springer-Verlag | 1998

Proofs from THE BOOK

Martin Aigner and Günter M. Ziegler

Heidelberg Berlin: Springer-Verlag | 1998

http://www.springer.com/mathematics/book ...

Oriented matroids

Jürgen Richter-Gebert and Günter M. Ziegler

Boca Raton: CRC Press | 1997

Erschienen in: Handbook of Discrete and Computational Geometry, pages 111-132

http://www2.lirmm.fr/~sol/Rapports/Refer ...

Extremal properties of 0/1-polytopes

Ulrich H. Kortenkamp and Jürgen Richter-Gebert and A. Sarangarajan and Günter M. Ziegler

Erschienen in: Discrete & Computational Geometry, volume 17, pages 439-448

http://www-m10.ma.tum.de/foswiki/pub/Leh ...

Basic properties of convex polytopes

Martin Henk and Jürgen Richter-Gebert and Günter M. Ziegler

Boca Raton: CRC Press | 1997

Erschienen in: Handbook of Discrete and Computational Geometry, pages 243-270

http://fma2.math.uni-magdeburg.de/~henk/ ...

Lê numbers

David Massey and Rodica E. Simion and Richard P. Stanley and Dirk L. Vertigan and Dominic J. A. Welsh and Günter M. Ziegler

Erschienen in: Journal of Combinatorial Theory, Ser.~B, volume 70, pages 118-133

A variant of the Buchberger algorithm for integer programming

Regina Urbaniak and Robert Weismantel and Günter M. Ziegler

Erschienen in: SIAM Journal on Discrete Mathematics, volume 10, pages 96-108

https://www.google.com/url?sa=t&rct=j&q= ...

Projections of polytopes and the Generalized Baues Conjecture

Jörg Rambau and Günter M. Ziegler

Erschienen in: Discrete & Computational Geometry, volume 16, pages 215-237

http://link.springer.com/article/10.1007 ...

Polytopes and optimization: Recent progress and some challenges

Günter M. Ziegler

Erschienen in: GMÖOR Newsletter, pages 3-12

Shadows and slices of polytopes

Nina Amenta and Günter M. Ziegler

Erschienen in: Proceedings of the 12th Annual ACM Symposium on Computational Geometry, pages 10-19

http://dl.acm.org/citation.cfm?id=237228

Oriented matroids today: Dynamic survey and updated bibliography

Günter M. Ziegler

Erschienen in: the electronic journal of combinatorics, volume 3, pages DS\#4

https://www.google.com/url?sa=t&rct=j&q= ...

Lectures on Polytopes

Günter M. Ziegler

New York: Springer-Verlag | 1995

0/1-Integer programming: Augmentation and optimization are equivalent

Andreas S. Schulz and Robert Weismantel and Günter M. Ziegler

Springer-Verlag | 1995

Erschienen in: "Algorithms --- ESA '95'': Proc.\ Third Annual European Symposium, Corfu, Greece, September 1995, Springer Lecture Notes in Computer Science, volume 979, pages 473-483

http://www.zib.de/Publications/Reports/S ...

Combinatorics in pure mathematics

László Lovász and László Pyber and Dominic J. A. Welsh and Günter M. Ziegler

North Holland/Elsevier | 1995

Erschienen in: Handbook of Combinatorics, pages 2039-2082

Gröbner bases of lattices, corner polyhedra, and integer programming

Bernd Sturmfels and Robert Weismantel and Günter M. Ziegler

Erschienen in: Beiträge zur Algebra und Geometrie/ Contributions to Algebra and Geometry, volume 36, pages 281-298

https://www.google.com/url?sa=t&rct=j&q= ...

Realization spaces of 4-polytopes are universal

Jürgen Richter-Gebert and Günter M. Ziegler

Erschienen in: Bulletin of the American Mathematical Society, volume 32, pages 403-412

http://arxiv.org/abs/math/9510217v1

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$. This implies that the realization space of a $4$-polytope can have the homotopy type of an arbitrary finite simplicial complex, and that all algebraic numbers are needed to realize all $4$- polytopes. The proof is constructive. These results sharply contrast the $3$-dimensional case, where realization spaces are contractible and all polytopes are realizable with integral coordinates (Steinitz's Theorem). No similar universality result was previously known in any fixed dimension.

Maximizing Möbius functions on subsets of Boolean algebras

Bruce E. Sagan and Yeong Nan Yeh and Günter M. Ziegler

Erschienen in: Discrete Mathematics, volume 126, pages 293-311

http://www.sciencedirect.com/science/art ...

Zonotopal tilings and the Bohne-Dress theorem

Jürgen Richter-Gebert and Günter M. Ziegler

American Math.\ Society | 1994

Erschienen in: Proc.\ "Jerusalem Combinatorics 93'', Contemporary Mathematics, volume 178, pages 211-232

http://www-m10.mathematik.tu-muenchen.de ...

A new local criterion for the lattice property

Günter M. Ziegler

Basel: Birkhäuser | 1994

Erschienen in: Algebra Universalis, volume 31, pages 608-610

http://link.springer.com/article/10.1007 ...

Three problems about 4-polytopes

Günter M. Ziegler

Dordrecht: Kluwer Academic Publishers | 1994

Erschienen in: Polytopes: Abstract, Convex and Computational (Proc. NATO Advanced Study Institute, Toronto 1993), pages 499-502

http://link.springer.com/chapter/10.1007 ...

Randomized simplex algorithms on Klee-Minty cubes

Bernd Gärtner and Günter M. Ziegler

Los Alamitos CA: IEEE Computer Society Press | 1994

Erschienen in: Proc.\ 35th Annual "Symposium on Foundations of Computer Science'' (FOCS), Nov.~20-22, 1994, Santa Fe NM, pages 502-510

http://people.inf.ethz.ch/~gaertner/text ...

Coxeter-associahedra

Victor Reiner and Günter M. Ziegler

Erschienen in: Mathematika, volume 41, pages 364-393

http://www.zib.de/Publications/Reports/S ...

Shellability of chessboard complexes

Günter M. Ziegler

Erschienen in: Israel J. Mathematics, volume 87, pages 97-110

http://link.springer.com/article/10.1007 ...

On the difference between real and complex arrangements

Günter M. Ziegler

Erschienen in: Mathematische Zeitschrift, volume 212, pages 1-11

http://arxiv.org/abs/alg-geom/9202005v1http://link.springer.com/article/10.1007 ...

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 complement, as was shown by Goresky \& MacPherson. We prove, however, that for $2$-arrangements the cohomology {\it algebra} is not determined by the intersection lattice. It encodes extra information on sign patterns, which can be computed from determinants of linear relations or, equivalently, from linking coefficients in the sense of knot theory. This also allows us (in the case $d=2$) to identify arrangements with the same lattice but different fundamental groups.

Higher Bruhat orders and cyclic hyperplane arrangements

Günter M. Ziegler

Erschienen in: Topology, volume 32, pages 259-279

https://www.google.com/url?sa=t&rct=j&q= ...

Homotopy types of subspace arrangements via diagrams of spaces

Günter M. Ziegler and Rade T. Živaljević

Erschienen in: Mathematische Annalen, volume 295, pages 527-548

http://link.springer.com/article/10.1007 ...

Oriented Matroids

Anders Björner and Michel Las Vergnas and Bernd Sturmfels and Neil White and Günter M. Ziegler

Cambridge: Cambridge University Press | 1993

Extension spaces of oriented matroids

Bernd Sturmfels and Günter M. Ziegler

Erschienen in: Discrete & Computational Geometry, volume 10, pages 23-45

http://link.springer.com/article/10.1007 ...

Topological representation of dual pairs of oriented matroids

Thomas H. Brylawski and Günter M. Ziegler

Springer-Verlag | 1993

Erschienen in: Special issue on "Oriented Matroids'', Discrete & Computational Geometry, volume (3)10, pages 237-240

http://link.springer.com/article/10.1007 ...

"What is a complex matroid?''

Günter M. Ziegler

Springer-Verlag | 1993

Erschienen in: Special issue on "Oriented Matroids'', Discrete & Computational Geometry, volume (3)10, pages 313-348

http://link.springer.com/article/10.1007 ...

On the height of the minimal Hilbert basis

Jiyong Liu and Leslie E. Trotter Jr. and Günter M. Ziegler

Erschienen in: Results in Mathematics, volume 23, pages 374-376

Some almost exceptional arrangements

Günter M. Ziegler

Erschienen in: Advances in Mathematics, volume 101, pages 50-58

http://www.sciencedirect.com/science/art ...

Combinatorial models for the finite-dimensional Grassmannians

Nikolai E. Mnёv and Günter M. Ziegler

Springer-Verlag | 1993

Erschienen in: special issue on "Oriented Matroids'', Discrete & Computational Geometry, volume (3)10, pages 241--250

http://link.springer.com/article/10.1007 ...

Matroid shellability, β-systems, and affine hyperplane arrangements

Günter M. Ziegler

Erschienen in: Journal of Algebraic Combinatorics, volume 1, pages 283-300

http://link.springer.com/article/10.1023 ...

Combinatorial stratification of complex arrangements

Anders Björner and Günter M. Ziegler

Erschienen in: Journal of the American Mathematical Society, volume 5, pages 105-149

http://www.ams.org/journals/jams/1992-05 ...

Introduction to greedoids

Anders Björner and Günter M. Ziegler

Cambridge University Press | 1992

Erschienen in: Matroid Applications, Encyclopedia of Mathematics, volume 40, pages 284-357

Supersolvable and modularly complemented matroid extensions

Thomas Wanner and Günter M. Ziegler

Erschienen in: European Journal of Combinatorics, volume 12, pages 341-360

Bounds for lattice polytopes containing a fixed number of interior points in a sublattice

Jeffrey C. Lagarias and Günter M. Ziegler

Erschienen in: Canadian Journal of Mathematics, volume 43, pages 1022-1035

http://math.ca/10.4153/CJM-1991-058-4

Some minimal non-orientable matroids of rank three

Günter M. Ziegler

Erschienen in: Geometriae Dedicata, volume 38, pages 365-371

http://link.springer.com/article/10.1007 ...

Broken circuit complexes: factorizations and generalizations

Anders Björner and Günter M. Ziegler

Erschienen in: Journal of Combinatorial Theory, Ser.~B, volume 51, pages 96-126

http://www.sciencedirect.com/science/art ...

Posets with maximal Möbius function

Günter M. Ziegler

Erschienen in: Journal of Combinatorial Theory, Ser.~A, volume 56, pages 203-222

http://www.sciencedirect.com/science/art ...

Binary supersolvable matroids and modular constructions

Günter M. Ziegler

Erschienen in: Proceedings of the American Mathematical Society, volume 113, pages 817-829

http://www.ams.org/journals/proc/1991-11 ...

Hyperplane arrangements with a lattice of regions

Anders Björner and Paul H. Edelman and Günter M. Ziegler

Erschienen in: Discrete and Computational Geometry, volume 5, pages 263-288

http://link.springer.com/article/10.1007 ...

Matroid representations and free arrangements

Günter M. Ziegler

Erschienen in: Transactions of the American Mathematical Society, volume 320, pages 525-541

http://www.ams.org/journals/tran/1990-32 ...

Multiarrangements of hyperplanes and their freeness

Günter M. Ziegler

Amer. Math. Soc. | 1989

Erschienen in: Proc. International Conference Singularities (Iowa City 1986), Contemporary Mathematics, volume 90, pages 345-358

The face lattice of hyperplane arrangements

Günter M. Ziegler

Erschienen in: Discrete Mathematics, volume 73, pages 233-238

http://www.sciencedirect.com/science/art ...

Combinatorial construction of logarithmic differential forms

Günter M. Ziegler

Erschienen in: Advances in Mathematics, volume 76, pages 116-154

http://www.sciencedirect.com/science/art ...

Branchings in rooted graphs and the diameter of greedoids

Günter M. Ziegler

Erschienen in: Combinatorica, volume 8, pages 217-234

http://link.springer.com/article/10.1007 ...

On the poset of partitions of an integer

Günter M. Ziegler

Erschienen in: Journal of Combinatorial Theory, Ser.~A, volume 42, pages 215-222

http://www.sciencedirect.com/science/art ...

Many non-equivalent realizations of the associahedron

Cesar Ceballos and Francisco Santos and Günter M. Ziegler

http://arxiv.org/abs/1109.5544v1

We show that three systematic construction methods for the $n$-dimensional associahedron, - as the secondary polytope of a convex $(n+3)$-gon (by Gelfand-Kapranov-Zelevinsky), - via cluster complexes of the root system $A_n$ (by Chapoton-Fomin-Zelevinsky), and - as Minkowski sums of simplices (by Postnikov) produce substantially different realizations, independent of the choice of the parameters for the constructions. The cluster complex and the Minkowski sum realizations were generalized by Hohlweg-Lange to produce exponentionally many distinct realizations, all of them with normal vectors in $\{0,\pm1\}^n$. We present another, even larger, exponential family, generalizing the cluster complex construction -- and verify that this family is again disjoint from the previous ones, with one single exception: The Chapoton-Fomin-Zelevinsky associahedron appears in both exponential families.

Lecture notes on equivariant obstruction theory and applications

Pavle V. M. Blagojević and Günter M. Ziegler

Around Brouwers fixed point theorem (Lecture notes)

Jiří Matoušek and Günter M. Ziegler

Spaces of convex n-partitions

Emerson Leon and Günter M. Ziegler

Foldable triangulations of lattice polygons

Michael Joswig and Günter M. Ziegler

http://arxiv.org/abs/1207.6865v2

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".

Convex equipartitions via Equivariant Obstruction Theory

Pavle V. M. Blagojević and Günter M. Ziegler

http://arxiv.org/abs/1202.5504v2

We describe a regular cell complex model for the configuration space F(\R^d,n). Based on this, we use equivariant obstruction theory in order 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. For a generalization of the conjecture we get a complete answer: It holds IF AND ONLY IF n is a prime power.

Many polytopes with low-dimensional realization space

Karim Adiprasito and Günter M. Ziegler

http://arxiv.org/abs/1212.5812v1

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: To bound the dimension of the realization space of a polytope in terms of its f-vector. Moreover, 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 in the sixties.

Equivariant topology of configuration spaces

Pavle V. M. Blagojević and Wolfgang Lück and Günter M. Ziegler

http://arxiv.org/abs/1207.2852v2

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 generalized Dold theorem for elementary abelian groups. The results on the Fadell-Husseini index yield a new proof of the Nandakumar & Ramana Rao conjecture for a prime. For n=p^k a prime power, we compute the Lusternik-Schnirelmann category cat(F(R^d,n)/S_n)=(d-1)(n-1), and for spheres obtain the bounds (d-1)(n-1)\le cat(F(S^d,n)/S_n)\le (d-1)(n-1)+1. Moreover, we extend coincidence results related to the Borsuk-Ulam theorem, as obtained by Cohen & Connett, Cohen & Lusk, and Karasev & Volovikov.

Ten Problems

Moritz Schmitt and Günter M. Ziegler

Optimal elliptic Sobolev regularity near three--dimensional, multi-material Neumann vertices

Robert Haller-Dintelmann and Wolfgang Höppner and Hans-Christoph Kaiser and Joachim Rehberg and Günter M. Ziegler

Unimodular triangulations of dilated 3-polytopes

Francisco Santos and Günter M. Ziegler

The random-edge rule on three-dimensional linear programs

Volker Kaibel and Rafael Mechtel and Micha Sharir and Günter M. Ziegler

http://arxiv.org/abs/math/0301076v1

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 <= f(n) <= 1.4943 n for large enough n.

Three non-equivalent realizations of the associahedron

Cesar Ceballos and Günter M. Ziegler

http://arxiv.org/abs/1006.3487v2

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.

Inscribable stacked polytopes

Bernd Gonska and Günter M. Ziegler

http://arxiv.org/abs/1111.5322v1

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 Björner Festschrift Volume

Editor: Axel Hultman and Svante Linusson and Günter M. Ziegler

The Victor Klee Memorial Festschrift

Editor: Peter Gritzmann and Bernd Sturmfels and Günter M. Ziegler

Special Issue: Oriented Matroids

Editor: Jürgen Richter-Gebert and Günter M. Ziegler

Special Issue: Combinatorics of Polytopes

Editor: Komei Fukuda and Günter M. Ziegler

Optimal bounds for the colored Tverberg problem

Pavle V. M. Blagojević and Benjamin Matschke and Günter M. Ziegler

http://arxiv.org/abs/0910.4987v2

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.

Face numbers of centrally symmetric polytopes from split graphs

Ragnar Freij and Matthias Henze and Moritz W. Schmitt and Günter M. Ziegler

http://arxiv.org/abs/1201.5790v1

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.

Warum Lineare Algebra?

Gerd Fischer and Günter M. Ziegler