Three Counter-Examples on Semi-Graphoids

Abstract

Semi-graphoids are combinatorial structures that arise in statistical learning theory. They are equivalent to convex rank tests and to polyhedral fans that coarsen the reflection arrangement of the symmetric group S n . In this paper we resolve two problems on semi-graphoids posed in Studený's book (2005), and we answer a related question of Postnikov, Reiner and Williams on generalized permutohedra. We also study the semigroup and the toric ideal associated with semi-graphoids.