Unimodality of the number of paths per length on polytopes: Examples, counterexamples, and a central limit theorem

Abstract

Because of its importance in combinatorics and optimization we study the full distribution of the lengths of monotone paths of a convex polytope. De Loera had conjectured that the number of such paths counted by length is always a unimodal sequence. We confirm this for several classes of polytopes but construct counterexamples disproving the conjecture in general. Nevertheless, we show that for random polytopes with vertices uniformly distributed on the sphere, the length of coherent paths satisfies a central limit theorem.

31 pages, 13+ figures