# Fair Representation in the Intersection of Two Matroids

• Ron Aharoni
• Eli Berger
• Dani Kotlar
• Ran Ziv
Keywords: Dimatroid, Fair representation

### 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.

Published
2017-10-06
Article Number
P4.10