Geodesic EmBeddings of Path Complexes

David Bremner
University of New Brunswick

A natural question in the context of the simplex method is what combi-
natorial types of edge paths can occur as shortest paths in the 1-skeleton of
a simple polytope. In the polar setting, the paths of interest become facet
paths on the boundary of simplicial polytopes.
A path complex is a pure simplicial complex whose dual graph (with edges
de ned by ridges) is a path. It turns out to be relatively straightforward to
generate all combinatorial types of path complex with a small number of
revisits, i.e. where most vertices not used again after they are pivoted out.
A geodesic embedding of a path complex P is a simplicial sphere S con-
taining P as a sub-complex such that no-shorter path complex P  S shares
end facets with P. In general we are most interested in the case where the
sphere is the boundary of a simplicial polytope; at least for the purposes of
proving non-embedability it suces to show that no geodesic embedding in
the boundary of a uniform matroid polytope (oriented matroid generalization
of a simplicial polytope) exists.
From a computational point of view, the question of geodesic embedability
of a path complex in (the boundary of) a matroid polytope can be reduced
to solving one large SAT (boolean satis ability) problem, or more practically
to the solution of a sequence of moderate sized SAT problems. In the last
few years, Deza, Hua, Schewe and I have used these techniques to compute
some new bounds for the maximum diameters of simple polytopes in low
dimensions or with relatively few facets.

Presentation (PDF File)

Back to Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?