Back to Search
Start Over
Matroid base polytope decomposition
- Publication Year :
- 2009
-
Abstract
- Let $P(M)$ be the matroid base polytope of a matroid $M$. A {\em matroid base polytope decomposition} of $P(M)$ is a decomposition of the form $P(M) = \bigcup\limits_{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 paper, we investigate {\em hyperplane splits}, that is, polytope decompositions when $t=2$. We give sufficient conditions for $M$ so $P(M)$ has a hyperplane split and characterize when $P(M_1 \oplus M_2)$ has a hyperplane split where $M_1 \oplus M_2$ denote the {\em direct sum} of matroids $M_1$ and $M_2$. We also prove that $P(M)$ has not a hyperplane split if $M$ is binary. Finally, we show that $P(M)$ has not a decomposition if its 1-skeleton is the {\em hypercube}.<br />Comment: 23 pages
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.0909.0840
- Document Type :
- Working Paper