Matroid Partition Property and the Secretary Problem
share
A matroid ℳ on a set E of elements has the α-partition property, for some α>0, if it is possible to (randomly) construct a partition matroid 𝒫 on (a subset of) elements of ℳ such that every independent set of 𝒫 is independent in ℳ and for any weight function w:E→ℝ_≥ 0, the expected value of the optimum of the matroid secretary problem on 𝒫 is at least an α-fraction of the optimum on ℳ. We show that the complete binary matroid, B_d on 𝔽_2^d does not satisfy the α-partition property for any constant α>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 α 2^d/d-colorable partition matroid for any α that is sublinear in d.
READ FULL TEXT
