On rainbow matchings for hypergraphs

Abstract

For any posotive integer $m$, let $[m]:=\{1,\dots ,m\}$. Let $n,k,t$ be positive integers. Aharoni and Howard conjectured that if, for $i\in [t]$, $\mathcal{F}_i\subset[n]^k:= \{(a_1,\ldots,a_k): a_j\in [n] \mbox{ for } j\in [k]\}$ and $|{\mathcal{F}}_i|>(t-1)n^{k-1}$, then there exist $M\subseteq [n{]}^k$ such that $|M|=t$ and $|M\cap {\mathcal{F}}_i|=1$ for $i\in [t]$ We show that this conjecture holds when $n\ge 3(k-1)(t-1)$. Let $n,t,k_1\ge k_2\ge \dots \ge k_t$ be positive integers. Huang, Loh and Sudakov asked for the maximum ${\Pi }_{i=1}^t|{\mathcal{R}}_i|$ over all $\mathcal{R}=\{{\mathcal{R}}_1,\dots ,{\mathcal{R}}_t\}$ such that each ${\mathcal{R}}_i$ is a collection of $k_i$-subsets of $[n]$ for which there does not exist a collection $M$ of subsets of $[n]$ such that $|M|=t$ and $|M\cap {\mathcal{R}}_i|=1$ for $i\in [t]$ %and $\mathcal{R}$ does not admit a rainbow matching. We show that for sufficiently large $n$ with ${\sum }_{i=1}^t{k}_i\le n(1-(4k\ln n/n{)}^{1/k})$, ${\prod }_{i=1}^t|{\mathcal{R}}_i|\le \left(\genfrac{}{}{0ex}{}{n-1}{k_1-1}\right)\left(\genfrac{}{}{0ex}{}{n-1}{k_2-1}\right){\prod }_{i=3}^t\left(\genfrac{}{}{0ex}{}{n}{k_i}\right)$. This bound is tight.