Rainbow sets in the intersection of two matroids

详细信息    查看全文

• 作者：Ron Aharoni^a ; ^{ra@tx.technion.ac.il" class="auth_mail" title="E-mail the corresponding author} ; Daniel Kotlar^b ; ^{dannykot@telhai.ac.il" class="auth_mail" title="E-mail the corresponding author} ; Ran Ziv^b ; ^{ranziv@telhai.ac.il" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Rainbow independent sets ; Matroid intersection ; Matroidal Latin squares ; Transversal
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：118
• 期：Complete
• 页码：129-136
• 全文大小：284 K

文摘

Given sets 795675c4d2898ff1406a" title="Click to view the MathML source">F₁,…,F_n$F_1,\dots ,F_n$, a partial rainbow function   is a partial choice function of the sets F_i$F_i$. A partial rainbow set is the range of a partial rainbow function. Aharoni and Berger [1] conjectured that if M$\mathcal{M}$ and N$\mathcal{N}$ are matroids on the same ground set, and 795675c4d2898ff1406a" title="Click to view the MathML source">F₁,…,F_n$F_1,\dots ,F_n$ are pairwise disjoint sets of size n   belonging to M∩N$\mathcal{M}\cap \mathcal{N}$, then there exists a rainbow set of size n−1$n-1$ belonging to M∩N$\mathcal{M}\cap \mathcal{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-\sqrt{n}$.