MIT Combinatorics Seminar
Semigraphoids and The Permutohedron
Jason Morton (UC Berkeley)
Friday October 6, 2006 4:15 pm Room 2136
ABSTRACT

Introduced by J. Pearl to model conditional independence and useful in
statistical learning theory, a semigraphoid is a collection of conditional
independence statements i,jK 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
ncube, 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.


