The Erdős Matching Conjecture and concentration inequalities

Abstract

More than 50 years ago, Erd\H os asked the following question: what is the maximum size of a family $\mathcal{F}$ of $k$-element subsets of an $n$-element set if it has no $s+1$ pairwise disjoint sets? This question attracted a lot of attention recently, in particular, due to its connection to various combinatorial, probabilistic and theoretical computer science problems. Improving the previous best bound due to the first author, we prove that $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{k}\right)-\left(\genfrac{}{}{0ex}{}{n-s}{k}\right)$, provided $n\ge \frac{5}{3}sk-\frac{2}{3}s$ and $s$ is sufficiently large. We derive several corollaries concerning Dirac thresholds and deviations of sums of random variables. We also obtain several related results.