MIT Combinatorics Seminar

Semigraphoids and The Permutohedron

Jason Morton (UC Berkeley)

Friday October 6, 2006   4:15 pm    Room 2-136


Introduced by J. Pearl to model conditional independence and useful in statistical learning theory, a semigraphoid is a collection of conditional independence statements i,j|K subject to certain axioms. I will show using a result of Tits that semigraphoids are equivalent to coarsenings of the braid arrangement, and relate them to poset arrangements and generalized permutohedra. Nice classes of these objects include those arising from submodular functions as certain regular subdivisions of the n-cube, and graph associahedra, which correspond to graphical models in statistics. The geometric point of view on semigraphoids, together with a toric algebraic perspective, is exploited to find counterexamples to conjectures of Studeny and a question of Postnikov, Reiner, and Williams.