Rainbow matchings in bipartite multigraphs

详细信息    查看全文

• 作者：János Barát ; András Gyárfás ; Gábor N. Sárközy
• 关键词：Factorizations ; Rainbow matchings ; Ryser’s conjecture
• 刊名：Periodica Mathematica Hungarica
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：74
• 期：1
• 页码：108-111
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics, general;
• 出版者：Springer Netherlands
• ISSN：1588-2829
• 卷排序：74

文摘

Suppose that k is a non-negative integer and a bipartite multigraph G is the union of $$\begin{aligned} N=\left\lfloor \frac{k+2}{k+1}n\right\rfloor -(k+1) \end{aligned}$$matchings \(M_1,\dots ,M_N\), each of size n. We show that G has a rainbow matching of size \(n-k\), i.e. a matching of size \(n-k\) with all edges coming from different \(M_i\)’s. Several choices of the parameter k relate to known results and conjectures.KeywordsFactorizationsRainbow matchingsRyser’s conjectureReferences1.R. Aharoni, personal communication2.R. Aharoni, E. Berger, Rainbow matchings in \(r\)-partite \(r\)-graphs. Electron. J. Combin. 16(1), R119 (2009)MathSciNetMATHGoogle Scholar3.R. Aharoni, P. Charbit, D. Howard, On a generalization of the Ryser–Brualdi–Stein conjecture. J. Graph Theory 78(2), 143–156 (2015)MathSciNetCrossRefMATHGoogle Scholar4.R.A. Brualdi, H.J. Ryser, Combinatorial Matrix Theory (Cambridge University Press, Cambridge, UK, 1991)CrossRefMATHGoogle Scholar5.A.E. Brouwer, A.J. de Vries, R.M.A. Wieringa, A lower bound for the length of partial transversals in a Latin square. Nieuw Arch. Wisk. 24(3), 330–332 (1978)MathSciNetMATHGoogle Scholar6.D. Clemens, J. Ehrenmüller, An improved bound on the sizes of matchings guaranteeing a rainbow matching, arXiv:1503.00438 7.A.A. Drisko, Transversals in row-latin rectangles. J. Combin. Theory Ser. A 84, 181–195 (1998)MathSciNetCrossRefMATHGoogle Scholar8.P. Hatami, P.W. Shor, A lower bound for the length of a partial transversal in a Latin square. J. Combin. Theory Ser. A 115, 1103–1113 (2008)MathSciNetCrossRefMATHGoogle Scholar9.D. Kotlar, R. Ziv, Large matchings in bipartite graphs have a rainbow matching. Eur. J. Combin. 38, 97–101 (2014)MathSciNetCrossRefMATHGoogle Scholar10.H.J. Ryser, Neuere probleme der kombinatorik (Vorträge über Kombinatorik Oberwolfach, Mathematisches Forschungsinstitut Oberwolfach, July 1967)11.P.W. Shor, A lower bound for the length of a partial transversal in a Latin square. J. Combin. Theory Ser. A 33, 1–8 (1982)MathSciNetCrossRefMATHGoogle Scholar12.S.K. Stein, Transversals of latin squares and their generalizations. Pacific J. Math. 59, 567–575 (1975)MathSciNetCrossRefMATHGoogle Scholar13.D.E. Woolbright, An \(n\times n\) Latin square has a transversal with at least \(n-\sqrt{n}\) distinct symbols. J. Combin. Theory Ser. A 24, 235–237 (1978)MathSciNetCrossRefMATHGoogle ScholarCopyright information© Akadémiai Kiadó, Budapest, Hungary 2016Authors and AffiliationsJános Barát1András Gyárfás2Email authorGábor N. Sárközy231.MTA-ELTE Geometric and Algebraic Combinatorics Research GroupBudapestHungary2.Alfréd Rényi Institute of MathematicsHungarian Academy of SciencesBudapestHungary3.Computer Science DepartmentWorcester Polytechnic InstituteWorcesterUSA About this article CrossMark Publisher Name Springer Netherlands Print ISSN 0031-5303 Online ISSN 1588-2829 About this journal Reprints and Permissions Article actions .buybox { margin: 16px 0 0; position: relative; } .buybox { font-family: Source Sans Pro, Helvetica, Arial, sans-serif; font-size: 14px; font-size: .875rem; } .buybox { zoom: 1; } .buybox:after, .buybox:before { content: ''; display: table; } .buybox:after { clear: both; } /*---------------------------------*/ .buybox .buybox__header { border: 1px solid #b3b3b3; border-bottom: 0; padding: 8px 12px; position: relative; background-color: #f2f2f2; } .buybox__header .buybox__login { font-family: Source Sans Pro, Helvetica, Arial, sans-serif; font-size: 14px; font-size: .875rem; letter-spacing: .017em; display: inline-block; line-height: 1.2; padding: 0; } .buybox__header .buybox__login:before { position: absolute; top: 50%; -webkit-transform: perspective(1px) translateY(-50%); transform: perspective(1px) translateY(-50%); content: '\A'; width: 34px; height: 34px; left: 10px; } /*---------------------------------*/ .buybox .buybox__body { padding: 0; padding-bottom: 16px; position: relative; text-align: center; background-color: #fcfcfc; border: 1px solid #b3b3b3; } .buybox__body .buybox__section { padding: 16px 12px 0 12px; text-align: left; } .buybox__section .buybox__buttons { text-align: center; width: 100%; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section .buybox__buttons { border-top: 0; padding-top: 0; } /******/ .buybox__section:nth-child(2) .buybox__buttons { border-top: 1px solid #b3b3b3; padding-top: 20px; } .buybox__buttons .buybox__buy-button { display: inline-block; text-align: center; margin-bottom: 5px; padding: 6px 12px; } .buybox__buttons .buybox__price { white-space: nowrap; text-align: center; font-size: larger; padding-top: 6px; } .buybox__section .buybox__meta { letter-spacing: 0; padding-top: 12px; } .buybox__section .buybox__meta:only-of-type { padding-top: 0; position: relative; bottom: 6px; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section .buybox__meta { margin-top: 0; margin-bottom: 0; } /******/ .buybox__meta .buybox__product-title { display: inline; font-weight: bold; } .buybox__meta .buybox__list { line-height: 1.3; } .buybox__meta .buybox__list li { position: relative; padding-left: 1em; list-style: none; margin-bottom: 5px; } .buybox__meta .buybox__list li:before { font-size: 1em; content: '\2022'; float: left; position: relative; top: .1em; font-family: serif; font-weight: 600; text-align: center; line-height: inherit; color: #666; width: auto; margin-left: -1em; } .buybox__meta .buybox__list li:last-child { margin-bottom: 0; } /*---------------------------------*/ .buybox .buybox__footer { border: 1px solid #b3b3b3; border-top: 0; padding: 8px 12px; position: relative; border-style: dashed; } /*-----------------------------------------------------------------*/ @media screen and (min-width: 460px) and (max-width: 1074px) { .buybox__body .buybox__section { display: inline-block; vertical-align: top; padding: 12px 12px; padding-bottom: 0; text-align: left; width: 48%; } .buybox__body .buybox__section { padding-top: 16px; padding-left: 0; } .buybox__section:nth-of-type(2) .buybox__meta { border-left: 1px solid #d3d3d3; padding-left: 28px; } .buybox__section:nth-of-type(2) .buybox__buttons { border-top: 0; padding-top: 0; padding-left: 16px ; } .buybox__buttons .buybox__buy-button { } /********** article buybox specific **********/ .buybox.article__buybox .buybox__section:nth-of-type(2) { margin-top: 16px; padding-top: 0; } .buybox.article__buybox .buybox__section:nth-of-type(2) .buybox__meta { margin-top: 40px; padding-top: 0; padding-bottom: 45px; } .buybox.article__buybox .buybox__section:nth-of-type(2) .buybox__meta:only-of-type { margin-top: 8px; padding-top: 12px; padding-bottom: 12px; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section:first-child { width: 69%; } .buybox.mycopy__buybox .buybox__section:last-child { width: 29%; } /******/ } /*-----------------------------------------------------------------*/ @media screen and (max-width: 459px) { /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__body { padding-bottom: 5px; } .buybox.mycopy__buybox .buybox__section:last-child { text-align: center; width: 100%; } .buybox.mycopy__buybox .buybox__buttons { display: inline-block; width: 150px ; } /******/ } /*-----------------------------------------------------------------*/ Log in to check access Buy (PDF) EUR 34,95 Unlimited access to the full article Instant download Include local sales tax if applicable Find out about institutional subscriptions (function () { var forEach = function (array, callback, scope) { for (var i = 0; i Export citation .RIS Papers Reference Manager RefWorks Zotero .ENW EndNote .BIB BibTeX JabRef Mendeley Share article Email Facebook Twitter LinkedIn Cookies We use cookies to improve your experience with our site. More information Accept Over 10 million scientific documents at your fingertips