The EF1 conjecture for matroids with a common valuation
The EF1 conjecture for matroids with a common valuation
Let be an independence structure, where is a finite set and is closed under taking subsets. Let be the least number of independent sets in a partition of . A matroid is an independence structure satisfying the exchange property: whenever and , some satisfies . For an integer , is EF1--colorable if every nonnegative additive valuation on admits an EF1 partition of into independent sets; a class has the EF1 property if every member is EF1--colorable for every such . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.