We show that if the ground set of a matroid can be partitioned into <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$k\ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> bases, then for any given subset S of the ground set, there is a partition into k bases such that the sizes of the intersections of the bases with S may differ by at most one. This settles the matroid equitability conjecture by Fekete and Szabó (Electron. J. Comb. 2011) in the affirmative. We also investigate equitable splittings of two disjoint sets <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$S_1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$S_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>, and show that there is a partition into k bases such that the sizes of the intersections with <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$S_1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> may differ by at most one and the sizes of the intersections with <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$S_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> may differ by at most two; this is the best one can hope for arbitrary matroids. We also derive applications of this result to matroid-constrained fair division problems. We show that there exists a matroid-constrained allocation that is envy-free up to one item if the valuations are identical and tri-valued additive. We also show that for bi-valued additive valuations, there exists a matroid-constrained allocation that provides everyone their maximin share.

Matroids are Equitable

期刊论文
出版模式：

开放获取
发表日期：

2026年6月2日

查看全文

Hannaneh Akrami,
Siyue Liu,
Roshan Raj,
László A. Végh

摘要

We show that if the ground set of a matroid can be partitioned into $k\ge 2$ $k \geq 2$ bases, then for any given subset S of the ground set, there is a partition into k bases such that the sizes of the intersections of the bases with S may differ by at most one. This settles the matroid equitability conjecture by Fekete and Szabó (Electron. J. Comb. 2011) in the affirmative. We also investigate equitable splittings of two disjoint sets $S_1$ $S_{1}$ and $S_2$ $S_{2}$ , and show that there is a partition into k bases such that the sizes of the intersections with $S_1$ $S_{1}$ may differ by at most one and the sizes of the intersections with $S_2$ $S_{2}$ may differ by at most two; this is the best one can hope for arbitrary matroids. We also derive applications of this result to matroid-constrained fair division problems. We show that there exists a matroid-constrained allocation that is envy-free up to one item if the valuations are identical and tri-valued additive. We also show that for bi-valued additive valuations, there exists a matroid-constrained allocation that provides everyone their maximin share.