2.4k citations · 2.9k across the 64 of their papers we have counts for
8 papers · 1 filter
Bier spheres and posets
Anders Björner, Andreas Paffenholz, Jonas Sjöstrand +1
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…
Construction techniques for cubical complexes, odd cubical 4-polytopes, and prescribed dual manifolds
Alexander Schwartz, Guenter M. Ziegler
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…
The Simplex Algorithm in Dimension Three
Volker Kaibel, Rafael Mechtel, Micha Sharir +1
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 c…
On the Monotone Upper Bound Problem
Julian Pfeifle, Günter M. Ziegler
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…
Singular 0/1-matrices, and the hyperplanes spanned by random 0/1-vectors
Thomas Voigt, Günter M. Ziegler
Let be the probability that a random 0/1-matrix of size is singular, and let be the expected number of 0/1-vectors in the linear subspace spanned by d-1…
The -Construction for Lattices, Spheres and Polytopes
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 (…
Convex Hulls, Oracles, and Homology
Michael Joswig, G"unter M. Ziegler
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 tur…
The Random Edge Rule on Three-Dimensional Linear Programs
Volker Kaibel, Raphael Mechtel, Micha Sharir +1
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 b…