A counterexample to the Hirsch conjecture

F Santos - Annals of mathematics, 2012 - JSTOR
The Hirsch Conjecture (1957) stated that the graph of a d-dimensional polytope with n facets
cannot have (combinatorial) diameter greater than n–d. That is, any two vertices of the …

Recent progress on the combinatorial diameter of polytopes and simplicial complexes

F Santos - Top, 2013 - Springer
Abstract The Hirsch Conjecture, posed in 1957, stated that the graph of ad-dimensional
polytope or polyhedron with n facets cannot have diameter greater than n− d. The conjecture …

Finding large counterexamples by selectively exploring the Pachner graph

BA Burton, A He - arXiv preprint arXiv:2303.06321, 2023 - arxiv.org
We often rely on censuses of triangulations to guide our intuition in $3 $-manifold topology.
However, this can lead to misplaced faith in conjectures if the smallest counterexamples are …

Diameter of polyhedra: limits of abstraction

F Eisenbrand, N Hähnle, T Rothvoß - Proceedings of the twenty-fifth …, 2009 - dl.acm.org
We investigate the diameter of a natural abstraction of the 1-skeleton of polyhedra. Although
this abstraction is simpler than other abstractions that were previously studied in the …

Realizability and inscribability for simplicial polytopes via nonlinear optimization

M Firsching - Mathematical Programming, 2017 - Springer
We show that nonlinear optimization techniques can successfully be applied to realize and
to inscribe matroid polytopes and simplicial spheres. In order to show non-realizability of …

On the circuit diameter conjecture

S Borgwardt, T Stephen, T Yusun - Discrete & Computational Geometry, 2018 - Springer
From the point of view of optimization, a critical issue is relating the combinatorial diameter
of a polyhedron to its number of facets f and dimension d. In the seminal paper of Klee and …

[图书][B] Polytopes and graphs

GP Villavicencio - 2024 - books.google.com
This book introduces convex polytopes and their graphs, alongside the results and
methodologies required to study them. It guides the reader from the basics to current …

Topological prismatoids and small simplicial spheres of large diameter

F Criado, F Santos - Experimental Mathematics, 2022 - Taylor & Francis
We introduce topological prismatoids, a combinatorial abstraction of the (geometric)
prismatoids recently introduced by the second author to construct counter-examples to the …

Enumerating neighborly polytopes and oriented matroids

H Miyata, A Padrol - Experimental Mathematics, 2015 - Taylor & Francis
Neighborly polytopes are those that maximize the number of faces in each dimension
among all polytopes with the same number of vertices. Despite their extremal properties …

More bounds on the diameters of convex polytopes

D Bremner, A Deza, W Hua… - Optimization Methods and …, 2013 - Taylor & Francis
Let Δ (d, n) be the maximum possible diameter of the vertex-edge graph over all d-
dimensional polytopes defined by n inequalities. The Hirsch bound holds for particular n and …