Matroids are Equitable

Hannaneh Akrami, Roshan Raj, László A. Végh · 2025

Read Matroids are Equitable by Hannaneh Akrami, Roshan Raj, László A. Végh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-12100.txt.

Introduction

A matroid is a structure that captures what independence means, in settings from graphs to vector spaces. Its ground set can often be split into equal building blocks called bases. Akrami and co-authors settle a standing conjecture about such splits. When the set splits into k bases, the split can be chosen so any subset S meets each base in nearly equal shares, differing by at most one element.

For two marked subsets at once, shares can be kept within one for the first and within two for the second. The authors show that is the best possible in general. They then apply the result to fair division under matroid limits, with envy-free style guarantees for simple value systems.

Catalog record

CREATORHannaneh Akrami, Roshan Raj, László A. Végh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-12100

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Matroids are Equitable Hannaneh Akrami, Roshan Raj, László A. Végh Abstract We show that if the ground set of a matroid can be partitioned into k ≥ 2 k\geq 2 bases, then for any given subset S S of the ground set, there is a partition into k k bases such that the sizes of the intersections of the bases with S 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 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 possible one can hope for arbitrary matroids. We also derive applications of this result into matroid constrained fair division problems. We show that there exists a matroid-constrained fair division that is envy-free up to 1 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. 1 Introduction Let \mathcal{M}=(E,\mathcal{I}) be a matroid defined on ground set E with independent sets \mathcal{I} . We let \mathcal{B}=\mathcal{B}(\mathcal{M}) denote the set of bases, i.e., maximal independent sets. 1 1 1 We include formal definitions of all concepts and notation in Section 2 . For \ell\geq 1 , we say that \mathcal{M} is \ell -equitable , if the ground set E is the disjoint union of two bases in \mathcal{M} , and the following property holds: for any \ell disjoint sets S_{1},\ldots,S_{\ell} , there exists two disjoint bases B_{1} and B_{2} such that \lfloor|S_{i}|/2\rfloor\leq|B_{1}\cap S_{i}|\leq\lceil|S_{i}|/2\rceil . We say that a class of matroids is \ell -equitable, if any matroid in the class where the ground set is the disjoint union of two bases is \ell -equitable. We say that \mathcal{M} or a class of matroids is equitable if it is 1-equitable. This property was first investigated by Fekete and Szabó [ 27 ] . They showed that graphic matroids are equitable, and also showed 3-equitability of graphic matroids for the special case when S_{1} , S_{2} , and S_{3} are disjoint stars. They also observed that weakly base orderable matroids are equitable, and that—using a result by Davies and McDiarmid [ 22 ] —strongly base orderable matroids are \ell -equitable for any \ell\geq 1 . A matroid is weakly base orderable if for any bases B_{1} and B_{2} , there is a bijection f\,:\,B_{1}\to B_{2} such that B_{1}-e+f(e) and B_{2}-f(e)+e are bases for any e\in B_{1} , 2 2 2 We use X-x+y to denote (X\setminus\{x\})\cup\{y\} . and strongly base orderable , if this bijection satisfies the stronger property that (B_{1}\setminus X)\cup f(X) is a basis for any X\subseteq B_{1} . The equitability conjecture asks if all matroids are equitable. This was first posed in [ 27 ] , see also the website [ 24 ] in the Egres Open collection. In recent years, progress has been made in multiple conjectures on matroid base exchanges that imply the equitability conjecture for certain classes. In particular, a result by Bérczi, Mátravölgyi and Schwarcz [ 11 ] imply equitability of regular matroids. See Section 1.2 for a discussion of these conjectures, as well as for other previously known special cases of the equitability conjecture. Our main result resolves the equitability conjecture in the affirmative for all matroids. We state the result more generally, for partitions of the ground set into any number k of bases. We note that equitability for two sets easily implies this more general statement, see also the discussion page in [ 24 ] . Our result also includes the guarantee of polynomial-time computability. Theorem 1.1 . Let \mathcal{M}=(E,\mathcal{I}) be a matroid, and assume that the ground set E can be partitioned into the union of k\geq 1 disjoint bases. Let S\subseteq E be an arbitrary set. Then, there exists a partition E=B_{1}\cup B_{2}\cup\ldots\cup B_{k} into k bases such that \left\lfloor\frac{|S|}{k}\right\rfloor\leq|B_{i}\cap S|\leq\left\lceil\frac{|S|}{k}\right\rceil\,\quad\forall i\in[k]\,. Moreover, such bases can be found in polynomial time. For \ell\geq 2 , \ell -equitability fails in general. A simple example for \ell=2 is the graphic matroid of K_{4} , with S_{1} and S_{2} being two disjoint bases, see Example 4.3 . Nevertheless, we show near-equitability for \ell=2 . Namely, equitability holds if at least one of |S_{1}| and |S_{2}| is odd, and is violated by one on either of the two sets if both have even cardinality. The example of K_{4} demonstrates that this is the strongest statement one may hope for \ell=2 . Our general statement is given in Theorem 4.1 for k bases; here, we present the corollary for two bases. Corollary 1.2 (of Theorem 4.1 ) . Let \mathcal{M}=(E,\mathcal{I}) be a matroid, and assume that the ground set E can be partitioned into the union of two disjoint bases. Let S_{1},S_{2}\subseteq E be two arbitrary disjoint sets. Then, there exists a partition E=B_{1}\cup B_{2} into 2 bases such that (i) If |S_{1}| and |S_{2}| are both odd, then |B_{1}\cap S_{1}|=\lfloor|S_{1}|/2\rfloor and |B_{1}\cap S_{2}|=\lceil|S_{2}|/2\rceil . (ii) If |S_{1}| is even and |S_{2}| is odd, then |B_{1}\cap S_{1}|=|S_{1}|/2 and |B_{1}\cap S_{2}|=\lfloor|S_{2}|/2\rfloor . (iii) If |S_{1}| and |S_{2}| are both even, |B_{1}\cap S_{1}|=|S_{1}|/2 and |B_{1}\cap S_{2}|\in[|S_{2}|/2-1,|S_{2}|/2+1] . Thus, in the third case, one of the even sets S_{1} is partitioned equally, while the other, S_{2} is partitioned such that ||S_{2}\cap B_{1}|-|S_{2}\cap B_{2}||\leq 2 . Corollary 1.2 proves a special case of a conjecture on almost fair representations in the intersection of matroids by Aharoni, Berger, Kotlar, and Ziv [ 2 ] , as discussed in Section 1.2 . We next state the main technical tool used in proving the above results. Definition 1.3 . Let B_{1} and B_{2} be two disjoint bases in the matroid \mathcal{M}=(E,\mathcal{I}) . The set X\subseteq E is an exchangeable set for B_{1} and B_{2} , if X\subseteq B_{1}\cup B_{2} , and B_{1}\Delta X and B_{2}\Delta X are both bases. 3 3 3 X\Delta Y denotes the symmetric difference of the sets X and Y . Further, for S\subseteq B_{1}\cup B_{2} , and t\in(B_{1}\cup B_{2})\setminus S we say that X\subseteq B_{1}\cup B_{2} is a (t,S) -exchangeable set for B_{1} and B_{2} , if t\in X\subseteq S+t and X is an exchangeable set for B_{1} and B_{2} . Our next theorem shows the existence of an exchangeable set. Theorem 1.4 . Let \mathcal{M}=(E,\mathcal{I}) be a matroid, S\subseteq E , and let B_{1} and B_{2} be two disjoint bases. If |B_{1}\cap S|<|B_{2}\cap S| , then for some t\in B_{1}\setminus S there exists a (t,S) -exchangeable set for B_{1} and B_{2} . Moreover, such a set can be found in polynomial time. Theorem 1.1 follows easily, as exchangeable sets can be used to ‘rebalance’ the intersections of two bases B_{1} and B_{2} with a set S . That is, we repeatedly find (t,S) -exchangeable sets for bases B_{i} and B_{j} with |B_{i}\cap S|<|B_{j}\cap S|-1 . One may wonder if analogous results may exist for \ell -equitability. We formulate the

Read the complete text