February 23, 3:30pm, Wean 8220

Cosmin Pohoata, Institute for Advanced Study

Rainbow matchings in hypergraphs

Cosmin Pohoata, Institute for Advanced Study

Rainbow matchings in hypergraphs

Abstract:

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 problem is also connected with different sides of additive combinatorics. In this talk, I will quickly survey some of these connections and then discuss some recent results that more or less completely answer the original question. Joint work with Lisa Sauermann and Dmitrii Zakharov.