Concentration inequalities for finding rainbow matchings
Concentration inequalities for finding rainbow matchings

Andrey Kupavskii, University of Oxford and IAS
Fine Hall 224
Consider a kpartite kuniform hypergraph on [n]^k. It is not difficult to see that any such hypergraph with more than (s1)n^{k1} edges contains a matching of size s. Aharoni and Berger asked a "transversal" variant of this question: given s hypergraphs, each having more than (s1)n^{k1} edges, can we guarantee the existence of an smatching with the ith edge coming from the ith hypergraph? In this talk, I will present our progress on this problem using a certain concentration inequality for the intersection of a family with a random matching. Joint work with Sergei Kiselev.