Rainbow matchings in bipartite multigraphs
- PDF / 347,523 Bytes
- 4 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 220 Views
Rainbow matchings in bipartite multigraphs János Barát1 · András Gyárfás2 · Gábor N. Sárközy2,3
Published online: 8 November 2016 © Akadémiai Kiadó, Budapest, Hungary 2016
Abstract Suppose that k is a non-negative integer and a bipartite multigraph G is the union of k+2 n − (k + 1) N= k+1 matchings M1 , . . . , 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 Mi ’s. Several choices of the parameter k relate to known results and conjectures. Keywords Factorizations · Rainbow matchings · Ryser’s conjecture
1 The result Suppose that a multigraph G is given with a proper N -edge coloring, i.e. the edge set of G is the union of N matchings M1 , . . . , M N . A rainbow matching is a matching whose edges are from different Mi ’s. A well-known conjecture of Ryser [10] states that for odd n every 1-factorization of K n,n has a rainbow matching of size n. The companion conjecture, attributed to Brualdi [4] and
B
András Gyárfás [email protected] János Barát [email protected] Gábor N. Sárközy [email protected]; [email protected]
1
MTA-ELTE Geometric and Algebraic Combinatorics Research Group, Budapest, Hungary
2
Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, P.O. Box 127, Budapest 1364, Hungary
3
Computer Science Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA
123
Rainbow matchings in bipartite multigraphs
109
Stein [12] states that for every n, every 1-factorization of K n,n has a rainbow matching of size at least n − 1. These conjectures are known to be true in an asymptotic sense, i.e. every 1-factorization of K n,n has a rainbow matching containing n − o(n) √ edges. For the o(n) term, Woolbright [13] and independently Brouwer et al. [5] proved n. Shor [11] improved this to 5.518(log n)2 , an error was corrected in [8]. There are several results for the case when K n,n is replaced by an arbitrary bipartite multigraph. The following conjecture of Aharoni et al. [3] strengthens the Brualdi-Stein conjecture. Conjecture 1.1 If a bipartite multigraph G is the union of n matchings of size n, then G contains a rainbow matching of size n − 1. As a relaxation, Kotlar and Ziv [9] noticed that the union of n matchings of size 23 n contains a rainbow matching of size n − 1. Conjecture 1.1 would follow from another one posed by Aharoni and Berger: Conjecture 1.2 If a bipartite multigraph G is the union of n matchings of size n + 1, then G contains a rainbow matching of size n. Recently, there has been gradual progress on this question. Aharoni et al. proved that matchings of size 47 n suffice [3]. Kotlar and Ziv [9] improved it to 53 n and Clemens and Ehrenmüller [6] to ( 23 + ε)n. One needs a lot more matchings of size n to guarantee a rainbow matching of size n. Aharoni and Berger [2] and (in a slightly weaker form) Drisko [7] proved the following. Theorem 1.3 If a bipartite multigraph G is the union of 2n − 1 matchings of size n, then G contains a rainbow matchi
Data Loading...
