FAIR REPRESENTATION IN THE INTERSECTION OF TWO MATROIDS

NEW

Problem: Reconstructed Conjecture 4.2: Let $\mathcal D=\mathcal M\cap\mathcal N$ be the intersection of two finite matroids on the same ground set. If $C,D\in\mathcal D$, then there exist $C',D'\in\mathcal D$ with

This is the natural reading of “dimatroid” and “almost equal size” in Aharoni–Berger–Kotlar–Ziv.

Result: The conjecture is false.

Work over $\mathbb F_3$, with ground set $E=\{0,\dots,9\}$. Let $M,N$ be the vector matroids represented by the following $6\times 10$ matrices, columns labeled $0,\dots,9$:

Let $\mathcal D=M\cap N$. Put

Then $C,D\in\mathcal D$: $C$ is the standard basis in both matroids, and a direct row-reduction shows the four columns $6,7,8,9$ are independent in both $M$ and $N$.

Suppose, toward contradiction, that there are almost equal $C',D'\in\mathcal D$ with union $E$. Since both matroids have rank $6$, $|C'|,|D'|\le 6$, and since $|E|=10$, an almost equal cover would yield, by deleting overlap elements if necessary, a partition

with $X,Y\in\mathcal D$.

Write $x_i=1$ if $i\in X$, and $x_i=0$ otherwise. The matrices show the following dependent sets:

and

Thus no one of these dependent sets may lie wholly in $X$ or wholly in $Y$.

From $\{3,9\}$ and $\{0,8\}$, we get $x_3\ne x_9$ and $x_0\ne x_8$. Swapping $X,Y$ if necessary, assume $x_3=1,x_9=0$.

Using the listed $N$-dependencies gives

Hence either $x_6=x_7=1$, forcing $x_2=x_4=0$, or $x_6=x_7=0$, forcing $x_2=x_4=1$.

If $x_6=x_7=1$, the $M$-dependencies $\{3,5,6,7\}$ and $\{1,6,7\}$ force $x_5=x_1=0$. Together with exactly one of $x_0,x_8$ being $1$, this gives $|X|=4$.

If $x_6=x_7=0$, the $M$-dependencies $\{5,6,7,9\}$ and $\{1,6,7\}$ force $x_5=x_1=1$. Together with exactly one of $x_0,x_8$ being $1$, this gives $|X|=6$.

Both contradict $|X|=5$. Therefore no almost equal cover exists, although $C,D\in\mathcal D$ and $C\cup D=E$.

Citation: Original conjecture: Aharoni, Berger, Kotlar, Ziv, “Fair representation in the intersection of two matroids,” arXiv:1612.07652, Conjecture 4.2. No prior counterexample is used here.