Skip to main content
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

Rainbow version of the Erdős Matching Conjecture via concentration

Published Web Location Commons 'BY' version 4.0 license

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

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View