Abstract:

Let M1,...,Mm be matchings in some graph G. A rainbow matching is a matching with at most one edge from each of M1,...,Mm. Let n>=2 be some natural number. In this talk, I show that a sufficient condition for the existence of a rainbow matching of size n is sum_{i=n}^m (|M_i|-n+1) > 5 n log2(n), (Where here we assume that each of M1,...,M(n-1) is at least as big as Mn,...,Mm). In particular, this holds when m >= n+sqrt(5 n log2(n)) and each of M1,...,Mm has size at least n+sqrt(5 n log2(n)). This improves a similar result by Correia, Pokrovskiy, and Sudakov with 20n^(7/8) instead of sqrt(5 n log2(n)).