Andrey Kupavskii, Institute for Advanced Study

Abstract

Consider a k-partite k-uniform hypergraph on [n]^k. It is not difficult to see that any such hypergraph with more than (s-1)n^{k-1} edges contains a matching of size s. Aharoni and Berger asked a "transversal" variant of this question: given s hypergraphs, each having more than (s-1)n^{k-1} edges, can we guarantee the existence of an s-matching with the i-th edge coming from the i-th 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.