Rainbow sets in the intersection of two matroids

DOI10.1016/J.JCTB.2016.01.002zbMATH Open1332.05027arXiv1405.3119OpenAlexW2129248989MaRDI QIDQ256994FDOQ256994

Authors: Ron Aharoni, Daniel Kotlar, Ran Ziv 

Publication date: 14 March 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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 $McapN$, then there exists a rainbow set of size $n-1$ belonging to $McapN$. Following an idea of Woolbright and Brower-de Vries-Wieringa, we prove that there exists such a rainbow set of size at least $n-sqrtn$.

Full work available at URL: https://arxiv.org/abs/1405.3119

Recommendations

• Rainbow sets in the intersection of two matroids: a generalization of results of Drisko and Chappell
• Choice functions in the intersection of matroids
• The intersection of a matroid and a simplicial complex
• On Rainbow Matchings for Hypergraphs
• Cooperative conditions for the existence of rainbow matchings

zbMATH Keywords

matroid intersectionmatroidal Latin squaresrainbow independent setstransversal

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorial aspects of matroids and geometric lattices (05B35) Transversal (matching) theory (05D15)

Cites Work

• Transversals of latin squares and their generalizations
• An \(n\times n\) Latin square has a transversal with at least \(n-\sqrt n\) distinct symbols
• A matroid generalization of a result on row-Latin rectangles
• Rainbow matchings in \(r\)-partite \(r\)-graphs
• Groups of orthogonal row-latin squares
• Combinatorial matrix theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the length of a partial independent transversal in a matroidal Latin square
• Title not available (Why is that?)
• A lower bound for the length of a partial transversal in a Latin square
• A lower bound for the length of a partial transversal in a Latin square

Cited In (6)

• An improved bound on the sizes of matchings guaranteeing a rainbow matching
• Choice functions in the intersection of matroids
• Rainbow bases in matroids
• Large matchings in bipartite graphs have a rainbow matching
• Fair representation in dimatroids
• Rainbow sets in the intersection of two matroids: a generalization of results of Drisko and Chappell

This page was built for publication: Rainbow sets in the intersection of two matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q256994)