Bérczi–Schwarcz–Yamaguchi coverability conjecture for matroids

At least 4 years old · documented by

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.

References

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.