Rainbow sets in the intersection of two matroids

DOI10.1016/J.JCTB.2016.01.002MaRDI QIDQ256994zbMATH OpenOpenAlexFDO

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)

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3613053 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• 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
• A matroid generalization of a result on row-Latin rectangles
• An \(n\times n\) Latin square has a transversal with at least \(n-\sqrt n\) distinct symbols
• Combinatorial matrix theory
• Groups of orthogonal row-latin squares
• On the length of a partial independent transversal in a matroidal Latin square
• Rainbow matchings in \(r\)-partite \(r\)-graphs
• Transversals of latin squares and their generalizations

Cited in

(6)

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

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)