Talk:Equitability of matroids

Missing condition -- Dion 21:33, 23 January 2010 (UTC)

In this conjecture, the set [math]B[/math] should probably be required to be both a base and the complement of a base. Indeed, otherwise the conjecture would (trivially) be true by taking a base-cobase and moving one exchange at a time to its complement.

Re: Missing condition -- Tamás Király 18:40, 24 January 2010 (UTC)

Thanks, you are right. I corrected the conjecture.

True for hypergraphic matroids -- Tamás Király 10:37, 25 February 2011 (UTC)

It is very easy to see that hypergraphic matroids are equitable. Let [math]H=(V,E)[/math] be a hypergraph whose edge set can be partitioned into two bases: B and E-B. Then for every hyperedge [math]e \in E[/math] we can choose a graph edge [math]e' \subseteq e[/math] such that [math]B'[/math] (the chosen graph edges for hyperedges in B) and [math](E-B)'[/math] are forests with the same components. Thus the circuit matroid of the graph G=(V,E') can be partitioned into 2 bases. We know that this circuit matroid is equitable; but this clearly implies that the hypergraphic matroid is also equitable, since for any base in the circuit matroid, the corresponding hyperedges form a base in the hypergraphic matroid too.

Stronger corollary -- Tamás Király (talk) 13:44, 15 July 2015 (UTC)

If the conjecture is true, then the following, seemingly stronger statement is also true:

If the ground set S of a matroid M can be partitioned into k bases, then for any set [math]X \subseteq S[/math] there is a partition [math]B_1,\dots,B_k[/math] into k bases such that [math]\lfloor |X|/k \rfloor \leq |B_i \cap X| \leq \lceil |X|/k \rceil [/math] for every i.

Indeed, consider a partition [math]B_1,\dots,B_k[/math] into k bases such that [math]\sum_{i=1}^k |(|B_i \cap X|- |X|/k)|[/math] is minimal. We can assume that [math]|B_1 \cap X| \leq \dots \leq |B_k \cap X|[/math]. If [math]B_1,\dots,B_k[/math] does not satisfy the conditions, then we can use the equitability w.r.t. X of the matroid M restricted to [math]B_1 \cup B_k[/math], to obtain [math]B_1'[/math] and [math]B_k'[/math] such that [math]|B_k' \cap X|-|B_1' \cap X| \lt |B_k \cap X|-|B_1 \cap X|[/math]. This contradicts the choice of [math]B_1,\dots,B_k[/math].