Bérczi–Schwarcz–Yamaguchi coverability conjecture for matroids

Let M=(E,I){\cal M}=(E,\mathcal{I}) be a matroid. It is kk-coverable if its ground set EE can be covered by at most kk independent sets from I\mathcal{I}. A partition matroid on the same ground set EE is likewise kk-coverable when its ground set has such a cover. Bérczi–Schwarcz–Yamaguchi conjecture. Every kk-coverable matroid M=(E,I){\cal M}=(E,\mathcal{I}) can be reduced to a 2k2k-coverable partition matroid on the same ground set EE. The paper states that this conjecture is refuted by its results, so the proposed universal reduction does not hold.

Sources & referencesView supporting material

Primary source

Dorna Abdolazimi, Anna R. Karlin, Nathan Klein and Shayan Oveis Gharan, “Matroid Partition Property and the Secretary Problem”, arXiv:2111.12436 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.