Rainbow sets in the intersection of two matroids
classification
🧮 math.CO
keywords
rainbowpartialsetsfunctionsizebelongingexistsldots
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.