The EF1 conjecture for matroids with a common valuation

Let M=(E,I)M=(E,\mathcal{I}) be an independence structure, where EE is a finite set and I\mathcal{I} is closed under taking subsets. Let χ(M)\chi(M) be the least number of independent sets in a partition of EE. A matroid is an independence structure satisfying the exchange property: whenever X,YIX,Y\in\mathcal{I} and X>Y|X|>|Y|, some xXYx\in X\setminus Y satisfies Y{x}IY\cup\{x\}\in\mathcal{I}. For an integer qχ(M)q\geq\chi(M), MM is EF1-qq-colorable if every nonnegative additive valuation on EE admits an EF1 partition of EE into qq independent sets; a class has the EF1 property if every member is EF1-qq-colorable for every such qq. The matroid EF1 conjecture. The class of matroids satisfies the EF1 property. This is known for broad classes including base-orderable and regular matroids, but remains open for general matroids; its validity is known to follow from a conjecture of Gabow.

Sources & referencesView supporting material

Primary source

Marcin Anholcer, Maciej Bartkowiak, Bartłomiej Bosek and Jarosław Grytczuk, “Epistemic fair division of independence structures”, arXiv:2606.11494 (2026).

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.