Article ID Journal Published Year Pages File Type
4656709 Journal of Combinatorial Theory, Series B 2016 8 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,