Choice functions in the intersection of matroids

MaRDI QIDQ2335696zbMATH OpenFDO

Authors Joseph Briggs, Min-Ki Kim

Publication date 15 November 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.00043, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i4p26

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

intersection of two matroidsmatchingrainbow setrow-Latin rectangle

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Fractional graph theory, fuzzy graph theory (05C72) Transversal (matching) theory (05D15) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Abstract: We prove a common generalization of two results, one on rainbow fractional matchings and one on rainbow sets in the intersection of two matroids: Given $d=rlceilkceil-r+1$ functions of size (=sum of values) $k$ that are all independent in each of $r$ given matroids, there exists a rainbow set of $supp(f_i)$, $ileqd$, supporting a function with the same properties.

Review text

Summary: We prove a common generalization of two results, one on rainbow fractional matchings [\textit{R. Aharoni}, \textit{R. Holzman} and \textit{Z. Jiang}, ``Rainbow fractional matchings, Preprint, \url{arXiv:1805.09732}] and one on rainbow sets in the intersection of two matroids [\textit{D. Kotlar} and \textit{R. Ziv}, Discrete Math. 338, No. 5, 695--697 (2015; Zbl 1306.05028)]: Given \(d=r\lceil k\rceil -r+1\) functions of size (= sum of values) \(k\) that are all independent in each of \(r\) given matroids, there exists a rainbow set of \(\mathrm{supp}(f_i)\), \(i \le d\), supporting a function with the same properties.

Recommendations

• Rainbow sets in the intersection of two matroids
• Rainbow sets in the intersection of two matroids: a generalization of results of Drisko and Chappell
• The intersection of a matroid and a simplicial complex
• Choice functions
• Rainbow fractional matchings

Cites work

• A topological colorful Helly theorem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• d-collapsing and nerves of families of convex sets
• How many colors guarantee a rainbow matching?
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Large rainbow matchings in general graphs
• Multicolored matchings in hypergraphs
• Rainbow fractional matchings
• Rainbow matchings in r-partite r-graphs
• Rainbow sets in the intersection of two matroids: a generalization of results of Drisko and Chappell
• Transversals in row-latin rectangles

Cited in

(7)

• A system of disjoint representatives of line segments with given \(k\) directions
• Mathematics of Plott choice functions
• Rainbow sets in the intersection of two matroids: a generalization of results of Drisko and Chappell
• Rainbow sets in the intersection of two matroids
• Complexes of graphs with bounded independence number
• Complexes of graphs with bounded independence number
• Choice functions

This page was built for publication: Choice functions in the intersection of matroids

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