Eli Berger (Haifa) — Rainbow Matchings

Eli Berger (Haifa) — Rainbow Matchings

Eli Berger (Haifa) — Rainbow Matchings

Wednesday, February 14, 2024
  • Lecturer: Eli Berger
  • Organizer: Chaim Even Zohar
  • Location: 814 Amado
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)).
Print to PDF