Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656709 | Journal of Combinatorial Theory, Series B | 2016 | 8 Pages |
Abstract
Given sets F1,…,FnF1,…,Fn, a partial rainbow function is a partial choice function of the sets FiFi. A partial rainbow set is the range of a partial rainbow function. Aharoni and Berger [1] conjectured that if MM and NN are matroids on the same ground set, and F1,…,FnF1,…,Fn are pairwise disjoint sets of size n belonging to M∩NM∩N, then there exists a rainbow set of size n−1n−1 belonging to M∩NM∩N. Following an idea of Woolbright and Brouwer–de Vries–Wieringa, we prove that there exists such a rainbow set of size at least n−n.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ron Aharoni, Daniel Kotlar, Ran Ziv,