On stability of rainbow matchings

Abstract

We show that for any integer $k\ge 1$ there exists an integer $t_0(k)$ such that for integers $t,k_1,\dots ,k_{t+1},n$ with $t>t_0(k)$, $\max \{k_1,\dots ,k_{t+1}\}\le k$, and $n>2k(t+1)$, the following holds: If $F_i\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k_i}\right)$ and $|F_i|>\left(\genfrac{}{}{0ex}{}{n}{k_i}\right)-\left(\genfrac{}{}{0ex}{}{n-t}{k_i}\right)-\left(\genfrac{}{}{0ex}{}{n-t-k}{k_i-1}\right)+1$ for all $i\in [t+1]$, then either $\{F_1,\dots ,F_{t+1}\}$ admits a rainbow matching of size $t+1$ or there exists $W\in \left(\genfrac{}{}{0ex}{}{[n]}{t}\right)$ such that $W$ is a vertex cover of $F_i$ for all $i\in [t+1]$. This may be viewed as a rainbow non-uniform extension of the classical Hilton-Milner theorem. We also show that the same holds for every $t$ and $n>2k^{3}t$, generalizing a recent stability result of Frankl and Kupavskii on matchings to rainbow matchings.

arXiv admin note: text overlap with arXiv:2004.12561