Fair representation in the intersection of two matroids (Q2409842)

Summary: Mysteriously, hypergraphs that are the intersection of two matroids behave in some respects almost as well as one matroid. In the present paper we study one such phenomenon -- the surprising ability of the intersection of two matroids to fairly represent the parts of a given partition of the ground set. For a simplicial complex \(\mathcal{C}\) denote by \(\beta(\mathcal{C})\) the minimal number of edges from \(\mathcal{C}\) needed to cover the ground set. If \(\mathcal{C}\) is a matroid then for every partition \(A_1, \ldots, A_m\) of the ground set there exists a set \(S \in \mathcal{C}\) meeting each \(A_i\) in at least \(\lfloor \frac{|A_i|}{\beta(\mathcal{C})}\rfloor\) elements. We conjecture that a slightly weaker result is true for the intersection of two matroids: if \(\mathcal{D}=\mathcal{P}\cap \mathcal{Q}\), where \(\mathcal{P},\mathcal{Q}\) are matroids on the same ground set \(V\) and \(\beta(\mathcal{P}), \beta(\mathcal{Q}) \leq k\), then for every partition \(A_1, \ldots, A_m\) of the ground set there exists a set \(S \in \mathcal{D}\) meeting each \(A_i\) in at least \(\frac{1}{k}|A_i|-1\) elements. We prove that if \(m=2\) (meaning that the partition is into two sets) there is a set belonging to \(\mathcal{D}\) meeting each \(A_i\) in at least \((\frac{1}{k}-\frac{1}{|V|})|A_i|-1\) elements.