@misc{ZieglerZivaljevic, author = {Ziegler, G{\"u}nter M. and Zivaljevic, R. T.}, title = {Homotopy Types of Subspace Arrangements via Diagrams of Spaces.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-658}, number = {SC-91-15}, abstract = {We prove combinatorial formulas for the homotopy type of the union of the subspaces in an (affine, compactified affine, spherical or projective) subspace arrangement. From these formulas we derive results of Goresky \& MacPherson on the homology of the arrangement and the cohomology of its complement. The union of an arrangement can be interpreted as the direct limit of a diagram of spaces over the intersection poset. A closely related space is obtained by taking the homotopy direct limit of this diagram. Our method consists in constructing a combinatorial model diagram over the same poset, whose homotopy limit can be compared to the original one by usual homotopy comparison results for diagrams of spaces.}, language = {en} } @misc{Ziegler, author = {Ziegler, G{\"u}nter M.}, title = {Lectures on Polytopes.}, number = {TR-93-06}, abstract = {These lecture notes have several aims: \begin{itemize} \item to give an introduction to some basic facts about convex polytopes, with an emphasis on the basic methods that yield them (Fourier-Motzkin elimination, Schlegel diagrams, shellability, Gale transforms and oriented matroids), \item to discuss some important examples and elegant constructions (cyclic and neighborly polytopes, zonotopes, Minkowski sums, permutahedra and associahedra, fiber polytopes, the Lawrence construction) \item and to illustrate why polytope theory is exciting, with highlights like Kalai's new diameter bounds, the construction of non-rational polytopes, the Bohne-Dress tiling theorem, shellability and the upper bound theorem, .... \end{itemize} For several of these topics the decisive break-through is very recent, which suggests that there is much more discovered.}, language = {en} } @misc{Ziegler, author = {Ziegler, G{\"u}nter M.}, title = {Shellability of Chessboard Complexes.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-890}, number = {SC-92-19}, abstract = {The matchings in a complete bipartite graph form a simplicial complex, which in many cases has strong structural properties. We use an equivalent description as chessboard complexes: the complexes of all non-taking rook positions on chessboards of various shapes. In this paper we construct `certificate \$k\$-shapes' \$\Sigma(m,n,k)\$ such that if the shape \$A\$ contains some \$\Sigma(m,n,k)\$, then the \$(k{-}1)\$-skeleton of the chessboard complex \$\Delta(A)\$ is vertex decomposable in the sense of Provan \& Billera. This covers, in particular, the case of rectangular chessboards \$A=[m]{\times}[n]\$, for which \$\Delta(A)\$ is vertex decomposable if \$n\ge 2m{-}1\$, and the \$(\lfloor{m+n+1\over3}\rfloor{-}1)\$-skeleton is vertex decomposable in general. The notion of vertex decomposability is a very convenient tool to prove shellability of such combinatorially defined simplicial complexes. We establish a relation between vertex decomposability and the CL-shellability technique (for posets) of Bj{\"o}rner \& Wachs.}, language = {en} } @misc{Ziegler, author = {Ziegler, G{\"u}nter M.}, title = {On the Difference Between Real and Complex Arrangements.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-648}, number = {SC-91-14}, abstract = {If \$B\$ is an arrangement of linear complex Hyperplanes in \$C^d\$, then the following can be constructed from knowledge of its intersection lattice: (a) the cohomology groups of the complement [Br], (b) the cohomology algebra of the complement [OS], (c) the fundamental group of the complement, if \$d\le2\$, (d) the singularity link up to homeomorphism, if \$d\le3\$, (e) the singularity link up to homotopy type [ZZ]. 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 (a) the cohomology groups of the complement [GM] and (e) the homotopy type of the singularity link [ZZ]. We show, however, that for 2-arrangements the data (b), (c) and (d) are not determined by the intersection lattice. They require the knowledge of extra information on sign patterns, which can be computed as determinants of linear relations, or (equivalently) as linking coefficients in the sense of knot theory.}, language = {en} } @misc{Ziegler, author = {Ziegler, G{\"u}nter M.}, title = {Higher Bruhat Orders and Cyclic Hyperplane Arrangements.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-607}, number = {SC-91-10}, abstract = {We study the higher Bruhat orders \$B(n,k)\$ of Manin \& Schechtman [MaS] and - characterize them in terms of inversion sets, - identify them with the posets \$U(C^{n+1,r},n+1)\$ of uniform extensions of the alternating oriented matroids \$C^{n,r}\$ for \$r:=n-k\$ (that is, with the extensions of a cyclic hyperplane arrangement by a new oriented pseudoplane), - show that \$B(n,k)\$ is a lattice for \$k =1\$ and for \$r\le 3\$, but not in general, - show that \$B(n,k)\$ is ordered by inclusion of inversion sets for \$k=1\$ and for \$r\le 4\$. However, \$B(8,3)\$ is not ordered by inclusion. This implies that the partial order \$B_\subseteq (n,k)\$ defined by inclusion of inversion sets differs from \$B(n,k)\$ in general. We show that the proper part of \$B_\subseteq (n,k)\$ is homotopy equivalent to \$S^{r-2}\$. Consequently, - \$B(n,k)\simeq S^{r-2}\$ for \$k=1\$ and for \$r\le 4\$. In contrast to this, we find that the uniform extension poset of an affine hyperplane arrangement is in general not graded and not a lattice even for \$r=3\$, and that the proper part is not always homotopy equivalent to \$S^{r(M)-2}\$.}, language = {en} } @misc{UrbaniakWeismantelZiegler, author = {Urbaniak, Regina and Weismantel, Robert and Ziegler, G{\"u}nter M.}, title = {A New Variant of Buchberger's Algorithm for Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1570}, number = {SC-94-29}, abstract = {In this paper we modify Buchberger's \$S\$-pair reduction algorithm for computing a Gr{\"o}bner basis of a toric ideal so as to apply to an integer program in inequality form with fixed right hand sides and fixed upper bounds on the variables. We formulate the algorithm in the original space and interpret the reduction steps geometrically. In fact, three variants of this algorithm are presented and we give elementary proofs for their correctness. A relationship between these (exact) algorithms, iterative improvement heuristics and the Kernighan-Lin procedure is established.}, language = {en} } @misc{SturmfelsZiegler, author = {Sturmfels, Bernd and Ziegler, G{\"u}nter M.}, title = {Extension Spaces of Oriented Matriods.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-618}, number = {SC-91-11}, abstract = {We study the space of all extensions of a real hyperplane arrangement by a new pseudo- hyperplane, and, more generally, of an oriented matroid by a new element. The question whether this space has the homotopy type of a sphere is a special case of the "Generalized Baues Problem" of Billera, Kapranov \& Sturmfels, via the Bohne-Dress Theorem on zonotopal tilings. We prove that the extension space is spherical for the class of strongly euclidean oriented matroids. This class includes the alternating matroids and all oriented matroids of rank at most 3 or of corank at most 2. In general it is not even known whether the extension space is connected. We show that the subspace of realizable extensions is always connected but not necessarily spherical.}, language = {en} } @misc{SturmfelsWeismantelZiegler, author = {Sturmfels, Bernd and Weismantel, Robert and Ziegler, G{\"u}nter M.}, title = {Gr{\"o}bner bases of lattices, corner polyhedra, and integer programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1548}, number = {SC-94-26}, abstract = {We investigate the generating sets (``Gr{\"o}bner bases'') of integer lattices which correspond to the Gr{\"o}bner bases of the associated binomial ideals. Extending results in Sturmfels and Thomas, preprint 1994, we obtain a geometric characterization of the universal Gr{\"o}bner basis in terms of the vertices and edges of the associated corner polyhedra. We emphasize the special case where the lattice has finite index. In this case the corner polyhedra were studied by Gomory, and there is a close connection to the ``group problem in integer programming'' Schrijver, p.~363. We present exponential lower and upper bounds for the size of a reduced Gr{\"o}bner basis. The initial complex of (the ideal of) a lattice is shown to be dual to the boundary of a certain simple polyhedron.}, language = {en} } @misc{SchulzWeismantelZiegler, author = {Schulz, Andreas S. and Weismantel, Robert and Ziegler, G{\"u}nter M.}, title = {0/1-Integer Programming: Optimization and Augmentation are Equivalent}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1744}, number = {SC-95-08}, abstract = {{\def\xnew{x^{\mbox{\tiny new}}}\def\Z{{{\rm Z}\!\! Z}}For every fixed set \${\cal F}\subseteq\{0,1\}^n\$ the following problems are strongly polynomial time equivalent: given a feasible point \$x\in\cal F\$ and a linear objective function \$c\in\Z^n\$, \begin{itemize} \item find a feasible point \$x^*\in\cal F\$ that maximizes \$cx\$ (Optimization), \item find a feasible point \$\xnew\in\cal F\$ with \$c\xnew>cx\$ (Augmentation), and \item find a feasible point \$\xnew\in\cal F\$ with \$c\xnew>cx\$ such that \$\xnew-x\$ is ``irreducible''\\(Irreducible Augmentation). \end{itemize} This generalizes results and techniques that are well known for \$0/1\$--integer programming problems that arise from various classes of combinatorial optimization problems.}}, language = {en} } @misc{RichterGebertZiegler, author = {Richter-Gebert, J{\"u}rgen and Ziegler, G{\"u}nter M.}, title = {Zonotopal Tilings and the Bohne-Dress Theorem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1212}, number = {SC-93-25}, abstract = {We prove a natural bijection between the polytopal tilings of a zonotope \$Z\$ by zonotopes, and the one-element-liftings of the oriented matroid \${\cal M}(Z)\$ associated with \$Z\$. This yields a simple proof and a strengthening of the Bohne-Dress Theorem on zonotopal tilings.}, language = {en} }