Category Archives: Uncategorized

The mysteries of the intersection of two matroids

An extremely mysterious phenomenon:

the intersection of two matroids behaves almost like a matroid, in many respects. Let M and N be two matroids on the same ground set, and let P be their intersection, namely the collection of the sets that belong to both. Then:

1. If there exists a partition of the ground set into k sets from P, then there exists a balanced partition into k sets, namely a partition into almost equal sets (differing by at most  1). This is an easy result, by Berger, Spruessel and myself.

2. If F_1, \ldots, F_k are sets in P of size k+1, then there exists a rainbow P-set (namely f_1 \in F_1, \ldots f_k \in F_k, such that {f_1, \ldots, f_k} \in P) – this is a conjecture.

3. If the ground set can be partitioned into k sets in M and into k sets in N, it can be partitioned into k+1 sets in P (conjecture).

and more.