Matroid Partition Property and the Secretary Problem

Abstract

A matroid $\mathcal{M}$ on a set $E$ of elements has the $\alpha$-partition property, for some $\alpha >0$, if it is possible to (randomly) construct a partition matroid $\mathcal{P}$ on (a subset of) elements of $\mathcal{M}$ such that every independent set of $\mathcal{P}$ is independent in $\mathcal{M}$ and for any weight function $w:E\to {\mathbb{R}}_{\ge 0}$, the expected value of the optimum of the matroid secretary problem on $\mathcal{P}$ is at least an $\alpha$-fraction of the optimum on $\mathcal{M}$. We show that the complete binary matroid, ${\mathcal{B}}_d$ on ${\mathbb{F}}_2^d$ does not satisfy the $\alpha$-partition property for any constant $\alpha >0$ (independent of $d$). Furthermore, we refute a recent conjecture of Bérczi, Schwarcz, and Yamaguchi by showing the same matroid is $2^d/d$-colorable but cannot be reduced to an $\alpha 2^d/d$-colorable partition matroid for any $\alpha$ that is sublinear in $d$.