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.
Copyright. All Rights Reserved.