Computer Science/Discrete Mathematics Seminar II

A classical theorem of Edmonds provides a min-max formula relating the maximal size of a set in the intersection of two matroids to a ``covering" parameter. In this talk we generalize this theorem, replacing one of the matroids by a general simplicial complex. One application is a solution of the case $r=3$ of a matroidal version of Ryser's conjecture. Another is an upper bound on the minimal number of sets belonging to the intersection of two matroids, needed to cover their common ground set. This, in turn, is used to derive a weakened version of a conjecture of Rota. Bounds are also found on the dual parameter - the maximal number of disjoint sets, all spanning in each of two given matroids. We describe the case in which the complex is the complex of independent sets of a graph, and prove generalizations of known results on ``independent systems of representatives" (which are the special case in which the matroid is a partition matroid). In particular, we define a notion of $k$-matroidal colorability of a graph, and prove a fractional version of a conjecture, that every graph $G$ is $2\Delta(G)$-matroidally colorable. This is joint work with Ron Aharoni