Rainbow version of the Erd\H os Matching Conjecture via Concentration

Abstract

We say that the families ${\mathcal{F}}_1,\dots ,{\mathcal{F}}_{s+1}$ of $k$-element subsets of $[n]$ are cross-dependent if there are no pairwise disjoint sets $F_1,\dots ,F_{s+1}$, where $F_i\in {\mathcal{F}}_i$ for each $i$. The rainbow version of the Erd\H os Matching Conjecture due to Aharoni and Howard and independently to Huang, Loh and Sudakov states that ${\min }_i|{\mathcal{F}}_i|\le \max \left\{\right(\genfrac{}{}{0ex}{}{n}{k})-(\genfrac{}{}{0ex}{}{n-s}{k}),(\genfrac{}{}{0ex}{}{(s+1)k-1}{k}\left)\right\}$ 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 the author.

References in corpus (1)

• Global hypercontractivity and its applications

Cited by in corpus (3)

• Rainbow perfect matchings for 4-uniform hypergraphs
• Extremal Problem for Matchings and Rainbow Matchings on Direct Products
• Co-degree threshold for rainbow perfect matchings in uniform hypergraphs