laminar matroid polytope

125 Views Asked by At

Let S be a ground set, and $\mathcal{S}$ be a laminar family of subsets of S. That is, for every two distinct subsets A, B$\in \mathcal{S}$, we have either $A\subseteq B$ or $B\subseteq A$ or $A \cap B = \emptyset$. For every $A \in \mathcal{S}$, we are given an upper bound $k_A \in\mathbb{Z} _{\ge 0}$. Let $\mathcal{I} = \{X\subseteq S :|X\cap A |\le k_A, \forall A \in \mathcal{S}\}$. We know that (S; I) is a laminar matroid. Prove that the laminar matroid polytope $\mathcal{P} := convex-hull(\{\chi X:X \in \mathcal{I} \})$ is exactly $$\{x\in[0,1]^S :x(A)\le k_A , \forall A \in \mathcal{S}\}.$$ Above, $\chi X \in \{0,1\}^S$ is the indicator vector for X, and x(A) is defined $\sum_{i \in A}x_i.$