Matroid bases polytope decomposition

11 November 2014
14:30
Jorge Ramirez-Alfonsin
Abstract
Let $P(M)$ be the matroid base polytope of a matroid $M$. A decomposition of $P(M)$ is a subdivision of the form $P(M)=\cup_{i=1}^t P(M_i)$ where each $P(M_i)$ is also a matroid base polytope for some matroid $M_i$, and for each $1\le i\neq j\le t$ the intersection $P(M_i)\cap P(M_j)$ is a face of both $P(M_i)$ and $P(M_j)$. In this talk, we shall discuss some results on hyperplane splits, that is, polytope decomposition when $t=2$. We present sufficient conditions for $M$ so $P(M)$ has a hyperplane split and a characterization when $P(M_i\oplus M_j)$ has a hyperplane split, where $M_i\oplus M_j$ denotes the direct sum of $M_i$ and $M_j$. We also show that $P(M)$ has not a hyperplane split if $M$ is binary. Finally, we present some recent results concerning the existence of decompositions with $t\ge 3$.
  • Combinatorial Theory Seminar