Show simple item record

dc.contributor.advisorSantos Leal, Francisco 
dc.contributor.authorCriado Gallart, Francisco
dc.contributor.otherUniversidad de Cantabriaes_ES
dc.date.accessioned2016-10-26T12:59:22Z
dc.date.available2016-10-26T12:59:22Z
dc.date.issued2016-09
dc.identifier.urihttp://hdl.handle.net/10902/9379
dc.description.abstractABSTRACT: The computational complexity of the simplex method, widely used for linear programming, depends on the combinatorial diameter of the edge graph of a polyhedron with n facets and dimension d. Despite its popularity, little is known about the (combinatorial) diameter of polytopes, and even for simpler types of complexes. For the case of polytopes, it was conjectured by Hirsch (1957) that the diameter is smaller than (n - d), but this was disproved by Francisco Santos (2010). In this thesis, we present two main results. First, a lower bound on the maximum diameter for two classes of simplicial complexes: pure simplicial complexes and pseudo-manifolds. Second, a topological improvement of Santos’ counter example to the Hirsch Conjecture. This one is (slightly) smaller than the previously known smallest simplicial non-Hirsch sphere.es_ES
dc.description.abstractRESUMEN: La complejidad computacional del método del símplex, ampliamente usado en programación lineal, depende del diámetro combinatorio del grafo de aristas de un poliedro con facetas y dimensión d. Pese a su popularidad, sabemos muy poco sobre el diámetro (combinatorio) de los politopos, incluso para clases más simples de complejos. Para el caso de los politopos, Hirsch (1957) conjeturó que el diámetro era menor que n - d, pero su conjetura fue refutada por Francisco Santos (2010). En esta memoria, presentamos dos resultados fundamentales. Primero, una cota inferior para el diámetro de dos clases de complejos simpliciales: complejos simpliciales puros y pseudo-variedades. Segundo, una mejora topológica del contraejemplo de Santos a la conjetura de Hirsch. Ésta es más pequeña que la anterior esfera simplical no Hirsch más pequeña que se conocía.es_ES
dc.format.extent43 p.es_ES
dc.language.isoenges_ES
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 Españaes_ES
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/es/*
dc.subject.otherDiscrete Geometryes_ES
dc.subject.otherComputational Geometryes_ES
dc.subject.otherSimulated Annealinges_ES
dc.subject.otherSimplicial Complexes_ES
dc.subject.otherCombinatorial Diameteres_ES
dc.subject.otherGeometría discretaes_ES
dc.subject.otherGeometría computacionales_ES
dc.subject.otherEnfriamiento simuladoes_ES
dc.subject.otherComplejo simpliciales_ES
dc.subject.otherDiámetro combinatorioes_ES
dc.titleDiameter of simplicial complexes, a computational approach.es_ES
dc.title.alternativeDiámetro de complejos simpliciales, un enfoque computacional.es_ES
dc.typeinfo:eu-repo/semantics/masterThesises_ES
dc.rights.accessRightsopenAccesses_ES
dc.description.degreeMáster en Matemáticas y Computaciónes_ES


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Atribución-NoComercial-SinDerivadas 3.0 EspañaExcept where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 España