pith. sign in

arxiv: 1405.3119 · v3 · pith:TPGBMIIAnew · submitted 2014-05-13 · 🧮 math.CO

Rainbow sets in the intersection of two matroids

classification 🧮 math.CO
keywords rainbowpartialsetsfunctionsizebelongingexistsldots
0
0 comments X
read the original abstract

Given sets $F_1, \ldots ,F_n$, a {\em partial rainbow function} is a partial choice function of the sets $F_i$. A {\em partial rainbow set} is the range of a partial rainbow function. Aharoni and Berger \cite{AhBer} conjectured that if $M$ and $N$ are matroids on the same ground set, and $F_1, \ldots ,F_n$ are pairwise disjoint sets of size $n$ belonging to $M \cap N$, then there exists a rainbow set of size $n-1$ belonging to $M \cap N$. Following an idea of Woolbright and Brower-de Vries-Wieringa, we prove that there exists such a rainbow set of size at least $n-\sqrt{n}$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.