Combinatorial Theory

We say that the families \(\mathcal{F}_1,\ldots, \mathcal{F}_{s+1}\) of \(k\)-element subsets of \([n]\) are cross-dependent if there are no pairwise disjoint sets \(F_1,\ldots, F_{s+1}\), where \(F_i\in \mathcal{F}_i\) for each \(i\). The rainbow version of the Erdős Matching Conjecture due to Aharoni and Howard and independently to Huang, Loh and Sudakov states that \(\min_{i} |\mathcal{F}_i|\le \max\big\{{n\choose k}-{n-s\choose k}, {(s+1)k-1\choose k}\big\}\) for \(n\ge (s+1)k\). In this paper, we prove this conjecture for \(n›3e(s+1)k\) and \(s›10^7\). One of the main tools in the proof is a concentration inequality due to Frankl and Kupavskii.

Mathematics Subject Classifications: 05D05

Keywords: Extremal set theory, Erdos matching conjecture, rainbow version