Talk:Equitability of matroids

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

In this conjecture, the set $$B$$ 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 $$H=(V,E)$$ be a hypergraph whose edge set can be partitioned into two bases: B and E-B. Then for every hyperedge $$e \in E$$ we can choose a graph edge $$e' \subseteq e$$ such that $$B'$$ (the chosen graph edges for hyperedges in B) and $$(E-B)'$$ 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 $$X \subseteq S$$ there is a partition $$B_1,\dots,B_k$$ into k bases such that $$\lfloor |X|/k \rfloor \leq |B_i \cap X| \leq \lceil |X|/k \rceil$$ for every i.

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