Two problems on matchings in set families - in the footsteps of Erdős and Kleitman

Abstract

The families ${\mathcal{F}}_1,\dots ,{\mathcal{F}}_s\subset 2^{[n]}$ are called $q$-dependent if there are no pairwise disjoint $F_1\in {\mathcal{F}}_1,\dots ,F_s\in {\mathcal{F}}_s$ satisfying $|F_1\cup \dots \cup F_s|\le q.$ We determine $\max |{\mathcal{F}}_1|+\dots +|{\mathcal{F}}_s|$ for all values $n\ge q,s\ge 2$. The result provides a far-reaching generalization of an important classical result of Kleitman. The well-known Erd\H os Matching Conjecture suggests the largest size of a family $\mathcal{F}\subset \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ with no $s$ pairwise disjoint sets. After more than 50 years its full solution is still not in sight. In the present paper, we provide a Hilton-Milner-type stability theorem for the Erdős Matching Conjecture in a relatively wide range, in particular, for $n\ge (2+o(1))sk$ with $o(1)$ depending on $s$ only. This is a considerable improvement of a classical result due to Bollobás, Daykin and Erdős. We apply our results to advance in the following anti-Ramsey-type problem, proposed by Özkahya and Young. Let $ar(n,k,s)$ be the minimum number $x$ of colors such that in any coloring of the $k$-element subsets of $[n]$ with $x$ (non-empty) colors there is a \textit{rainbow matching} of size $s$, that is, $s$ sets of different colors that are pairwise disjoint. We prove a stability result for the problem, which allows to determine $ar(n,k,s)$ for all $k\ge 3$ and $n\ge sk+(s-1)(k-1).$ Some other consequences of our results are presented as well.

Cited by in corpus (2)

• New inequalities for families without k pairwise disjoint members
• Minimum saturated families of sets