Open Access Publications from the University of California

## Published Web Location

https://doi.org/10.5070/C63160414
Abstract

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