TY - GEN A1 - Sturmfels, Bernd A1 - Ziegler, Günter M. T1 - Extension Spaces of Oriented Matriods. N2 - 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. T3 - ZIB-Report - SC-91-11 Y1 - 1991 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-618 ER - TY - GEN A1 - Sturmfels, Bernd A1 - Weismantel, Robert A1 - Ziegler, Günter M. T1 - Gröbner bases of lattices, corner polyhedra, and integer programming N2 - We investigate the generating sets (``Gröbner bases'') of integer lattices which correspond to the Gröbner bases of the associated binomial ideals. Extending results in Sturmfels and Thomas, preprint 1994, we obtain a geometric characterization of the universal Grö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öbner basis. The initial complex of (the ideal of) a lattice is shown to be dual to the boundary of a certain simple polyhedron. T3 - ZIB-Report - SC-94-26 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1548 ER - TY - GEN A1 - Diaconics, Persi A1 - Sturmfels, Bernd T1 - Algebraic Algorithms for Sampling from Conditional Distributions. N2 - We construct Markov chain algorithms for sampling from discrete exponential families conditional on a sufficient statistic. Examples include generating tables with fixed row and column sums and higher dimensional analogs. The algorithms involve finding bases for associated polynomial ideals and so an excursion into computational algebraic geometry. T3 - ZIB-Report - SC-93-17 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1131 ER -