@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{DiaconicsSturmfels, author = {Diaconics, Persi and Sturmfels, Bernd}, title = {Algebraic Algorithms for Sampling from Conditional Distributions.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1131}, number = {SC-93-17}, abstract = {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.}, language = {en} }