Fair representation in the intersection of two matroids

Abstract

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,\dots ,A_m$ of the ground set there exists a set $S\in \mathcal{C}$ meeting each $A_i$ in at least $\frac{|A_i|}{\beta (\mathcal{C})}$ elements. We conjecture that a slightly weaker result is true for the intersections 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{P})\le k$, then for every partition $A_1,\dots ,A_m$ of the ground set there exists a set $S\in \mathcal{D}$ meeting each $A_i$ in at least $(\frac{1}{k}-\frac{1}{|V|})|A_i|-1$ elements. We prove this for a partition into two sets.