Improved Bounds on Rainbow $k$-partite Matchings

Abstract

Let $n$, $s$, and $k$ be positive integers. We say that a sequence $f_1,\dots ,f_s$ of nonnegative integers is satisfying if for any collection of $s$ families ${\mathcal{F}}_1,\dots ,{\mathcal{F}}_s\subseteq [n{]}^k$ such that $|{\mathcal{F}}_i|=f_i$ for all $i$, there exists a rainbow matching, i.e., a list of pairwise disjoint tuples $F_1\in {\mathcal{F}}_1$, $\dots$, $F_s\in {\mathcal{F}}_s$. We investigate the question, posed by Kupavskii and Popova, of determining the smallest $c=c(n,s,k)$ such that the arithmetic progression $c$, $n^{k-1}+c$, $2n^{k-1}+c$, $\dots$, $(s-1)n^{k-1}+c$ is satisfying. We prove that the sequence is satisfying for $c={\Omega }_k(\max (s^2{n}^{k-2},s{n}^{k-3/2}\sqrt{\log s}))$, improving the previous result by Kupavskii and Popova. We also study satisfying sequences for $k=2$ using the polynomial method, extending the previous result by Kupavskii and Popova to when $n$ is not prime.

13 pages. To appear in European Journal of Combinatorics