On the Number of Facets of Polytopes RepresentingComparative Probability Orders

Ilya Chevyrev, Dominic Searles , Arkadii Slinko

Research output: Contribution to journalArticlepeer-review

Abstract

Fine and Gill (Ann Probab 4:667–673,1976) introduced the geometricrepresentation for those comparative probability orders onnatoms that havean underlying probability measure. In this representation every such comparativeprobability order is represented by a region of a certain hyperplane arrangement.Maclagan (Order 15:279–295,1999) asked how many facets a polytope, which isthe closure of such a region, might have. We prove that the maximal number offacets is at leastFn+1,whereFnis thenth Fibonacci number. We conjecture thatthis lower bound is sharp. Our proof is combinatorial and makes use of the conceptof a flippable pair introduced by Maclagan. We also obtain an upper bound which isnot too far from the lower bound.
Original languageEnglish
Pages (from-to)749–761
Number of pages13
JournalDiscrete & computational geometry
Volume30
Issue number3
Early online date19 Oct 2012
DOIs
Publication statusPublished - 30 Nov 2013

Fingerprint

Dive into the research topics of 'On the Number of Facets of Polytopes RepresentingComparative Probability Orders'. Together they form a unique fingerprint.

Cite this