Rainbow matchings and rainbow connectedness

zbMATH Open1355.05203arXiv1504.05373MaRDI QIDQ510322FDOQ510322

Authors: Alexey Pokrovskiy 

Publication date: 17 February 2017

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

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.

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

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

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

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)

Cites Work

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

Cited In (16)

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