WP1: Mysteries of the intersection of two matroids.

We approach the study of matching theory from the viewpoint of the intersection of two matroids.

Algebraic methods:  The famous Rota conjecture is a special case of the Aharoni–Berger conjecture on the covering number in the intersection of two matroids. In Rota’s conjecture, one of the two matroids is a partition matroid, and the special condition is that its parts already form a partition of the ground set into bases in the other matroid. The conjectured conclusion is stronger in accord—there is a partition of the ground set into precisely k (and not k + 1) parts independent in both matroids, where k is the partition number of both matroids. Aharoni and Loebl extended algebraic results, connecting the conjecture with the Alon–Tarsi conjecture, to the case of k odd. We shall pursue this direction, aiming to apply algebraic techniques.

Scrambling. It was conjectured that Rota’s conjecture is “almost” true in a more general context. The conjecture is that given n independent sets of size n in a matroid, it is possible to scramble them, retaining the condition that all sets are of size n, and still have n − 1 (instead of n, as in Rota’s conjecture) disjoint independent transversals. In other words: Given a matroid M whose ground set can be partitioned into n independent sets, any system (A1, …, An) of disjoint (not necessarily independent) sets of size n has n − 1 disjoint transversals that are independent in M. A close conjecture is that under the same condition it is possible to cover the ground set by n + 1 transversals that are independent in M. This is a special case of the Aharoni–Berger conjecture mentioned above. It seems that scrambling is similar in nature to the addition of another matroid.

Topological methods: These have been found to be particularly efficient in this family of problems. It is clear that they have not been exhausted, and many results can be improved using them. One such result is a famous theorem of Erdős and Spencer, saying that given three partition matroids, with partition numbers k, k, (k − 1)16 respectively, there exists a common independent set of size  . This was obtained using probability, and as can be expected from this type of tool, the 16 factor is probably far from the truth. It is possible that the right factor is 2. Topology also will probably not yield a sharp result, but may get us nearer to one. The field is still awaiting the development of new topological techniques.

Combination of topology and linear programming:  The famous colorful versions of the theorems of Helly and Carathéodory, proved by Lovász and Bárány, are instances of adding another structure—a partition matroid, to the settings of the classical theorems. Indeed, topological tools have been introduced here, too—Kalai and Meshulam [KM] proved topological versions of both theorems.  A main tool in their approach is that of d-collapsibility of complexes (in the applications—nerve complexes). It will be interesting to prove some of the known theorems belonging to the family of “adding an extra matroid” using this notion. In particular, it will be nice to know the minimal d such that the complex of sets of edges of size r, with no matching of size k, is d-collapsible. This will give new results belonging to the family we are studying. Partial results have been obtained by Aharoni, Holzman and Zilin.