Completely unimodal numberings of a simple polytope

摘要: Abstract A completely unimodal numbering of the m vertices a simple d-dimensional polytope is 0, 1, …,m−1 such that on every k-dimensional face (2≤k≤d) there exactly one local minimum (a vertex with no lower-numbered neighbors face). Such numberings are abstract objective functions in sense Adler and Saigal [1]. It shown induces shelling facets dual simplicial polytope. The h-vector interpreted terms (with respect to using local-improvement algorithm locate numbered 0). In case combinatorially equivalent cube, ‘successor-tuple’ for each defined which carries crucial information algorithms. Combinatorial properties these d-tuples studied. Finally running time particular algorithm, Random Algorithm, studied d-cube. certain class (which includes example Klee Minty [8] showing simplex not polynomial all Hamiltonian saddle-free injective pseudo-Boolean [6]) this has expected at worst quadratic dimension d.