Fair Representation in the Intersection of Two Matroids

Abstract

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}) \le 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.