Rainbow matchings and rainbow connectedness

MaRDI QIDQ510322zbMATH OpenFDO

Authors Alexey Pokrovskiy

Publication date 17 February 2017

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

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

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

Latin squaresconnectednessmatchingstransversals

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Abstract: Aharoni and Berger conjectured that every bipartite graph which is the union of n matchings of size n + 1 contains a rainbow matching of size n. This conjecture is a generalization of several old conjectures of Ryser, Brualdi, and Stein about transversals in Latin squares. There have been many recent partial results about the Aharoni-Berger Conjecture. In the case when the matchings are much larger than n + 1, the best bound is currently due to Clemens and Ehrenm"uller who proved the conjecture when the matchings are of size at least 3n/2 + o(n). When the matchings are all edge-disjoint and perfect, then the best result follows from a theorem of H"aggkvist and Johansson which implies the conjecture when the matchings have size at least n + o(n). In this paper we show that the conjecture is true when the matchings have size n + o(n) and are all edge-disjoint (but not necessarily perfect). We also give an alternative argument to prove the conjecture when the matchings have size at least $phin+o(n)$ where $phiapprox1.618$ is the Golden Ratio. Our proofs involve studying connectedness in coloured, directed graphs. The notion of connectedness that we introduce is new, and perhaps of independent interest.

Recommendations

• Rainbow matchings and connectedness of coloured graphs
• An approximate version of a conjecture of Aharoni and Berger
• Rainbow matchings in properly colored multigraphs
• An improved bound on the sizes of matchings guaranteeing a rainbow matching
• Rainbow paths and large rainbow matchings

Cites work

• scientific article; zbMATH DE number 3613053 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• A lower bound for the length of a partial transversal in a Latin square
• An \(n\times n\) Latin square has a transversal with at least \(n-\sqrt n\) distinct symbols
• An improved bound on the sizes of matchings guaranteeing a rainbow matching
• Combinatorial matrix theory
• Large matchings in bipartite graphs have a rainbow matching
• On a generalization of the Ryser-Brualdi-Stein conjecture
• Orthogonal Latin Rectangles
• Rainbow matchings in \(r\)-partite \(r\)-graphs
• Representation of large matchings in bipartite graphs
• Transversals in Latin squares: a survey
• Transversals of latin squares and their generalizations

Cited in

(16)

• Short Proofs of Rainbow Matchings Results
• An improved bound on the sizes of matchings guaranteeing a rainbow matching
• Fair representation in the intersection of two matroids
• Full rainbow matchings in graphs and hypergraphs
• Rainbow structures in locally bounded colorings of graphs
• A better bound on the size of rainbow matchings
• Rainbow matchings and transversals
• Topological methods for the existence of a rainbow matching
• Cooperative conditions for the existence of rainbow matchings
• Rainbow paths and large rainbow matchings
• An approximate version of a conjecture of Aharoni and Berger
• Rainbow matchings in properly colored multigraphs
• Rainbow matchings and connectedness of coloured graphs
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Degree conditions for matchability in 3-partite hypergraphs
• New bounds for Ryser’s conjecture and related problems

This page was built for publication: Rainbow matchings and rainbow connectedness

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