On t he Number of Facets of Polytopes RepresentingComparative Probability Orders

摘要

Fine and Gill (Ann Probab 4:667-673, 1976) introduced the geometric representation for those comparative probability orders on n atoms that have an underlying probability measure. In this representation every such comparative probability order is represented by a region of a certain hyperplane arrangement. Maclagan (Order 15:279-295, 1999) asked how many facets a polytope, which is the closure of such a region, might have. We prove that the maximal number of facets is at least F_(n+1), where F_n is the nth Fibonacci number. We conjecture that this lower bound is sharp. Our proof is combinatorial and makes use of the concept of a flippable pair introduced by Maclagan. We also obtain an upper bound which is not too far from the lower bound.