Computer Science/Discrete Mathematics Seminar II

Suppose we are given matchings $M_1,....,M_N$ of size t in some r-uniform hypergraph, and let us think of each matching having a different color. How large does N need to be (in terms of t and r) such that we can always find a rainbow matching of size t? This problem was first introduced by Aharoni and Berger, and has since been studied by several different authors. While interesting for its own sake in the context of finding transversals in Latin Squares (e.g. the Ryser–Brualdi–Stein Conjecture), it is perhaps not too surprising that this question is also connected with different sides of additive combinatorics. In this talk, we will survey some of these connections, discuss some recent results that more or less completely answer the original question when one of the parameters t or r is fixed, and then end with some (fairly arbitrary) speculations/open problems.

Joint work with Lisa Sauermann and Dmitrii Zakharov.