Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 8 of 8 for “"Hirsch Conjecture"”.
-
Homological and Combinatorial Properties of m-Primary Monomial Ideals and Integer Sets
… Specifically, motivated by the polynomial Hirsch conjecture, we show that the graph corresponding to a linearly presented ideal has diameter bounded by a linear function of the generating degree.
-
Combinatorial Optimization and Discrete Geometry Approaches for Half-Integral Polytopes
… on the worst-case number of simplex pivots. Hirsch conjectured in 1953 that the diameter of a bounded polyhedron (polytope) is at most the difference between the number of its facets and its dimension. Research on the maximum diameter of polytopes has usually considered polytopes in terms of …
-
Equivariant topology methods in discrete geometry
… theorem that implies the Bárány-Larman conjecture for primes minus one and asymptotically in general. This in turn improves the bounds in the second selection lemma, which is used in computational complexity for example to bound the number of halving sets of an n-set in R^d . Then we …
-
On the number of distinct squares in strings
… was instrumental in Santos' tackling of the Hirsch conjecture, we introduce a (d,n-d) table with entries S(d,n) where d is the index for the rows and n-d is the index for the columns. We examine the properties of the S(d,n) function in the context of (d,n-d) table and conjecture that the …
-
COMBINATORIAL OPTIMIZATION APPROACHES TO DISCRETE PROBLEMS
… limit of c_t(n) for n going to infinity. A 1962 conjecture of Erdos stating that c_t = 2^{1-\tbinom{t}{2}} was disproved by Thomason in 1989 for all t > 3. Tighter counterexamples have been constructed by Jagger, Stovicek and Thomason in 1996, by Thomason for t < 7 in 1997, and by Franek for t=6 …
-
Serre's Condition and Depth of Stanley-Reisner Rings
The aim of this work is to garner a deeper understanding of the relationship between depth of a ring and connectivity properties of the spectrum of that ring. We examine with particular interest the case where our ring is a Stanley- Reisner ring. In this circumstance, we consider the simplicial …
-
Methods from Differential Geometry in Polytope Theory
The purpose of this thesis is to study classical objects, such as polytopes, polytopal complexes, and subspace arrangements. We will tackle problems, old and new, concerning them. We do so by using some of the new tools that have been developed in combinatorial topology, especially those tools …
-
On The Circuit Diameters of Some Combinatorial Polytopes
The combinatorial diameter of a polytope P is the maximum value of a shortest path between two vertices of P, where the path uses the edges of P only. In contrast to the combinatorial diameter, the circuit diameter of P is defined as the maximum value of a shortest path between two vertices of P, …