A Proof of the Erdős Matching Conjecture for Large Matchings via Sharp Tail Probability for Sums of i.i.d. Nonnegative Random Variables

Abstract

We resolve a conjecture of Łuczak, Mieczkowska and Šileikis on the maximal tail probability of sums of independent and identically distributed nonnegative random variables. Specifically, for every integer $k\ge 1$ and every $0\le x\le 1/k$, we prove \[ \sup_{\mathbb E X_1\le x}\mathbb{P}(X_1+\cdots+X_k\ge1) =\max\{1-(1-x)^k,(kx)^k\}, \] where the supremum is over nonnegative i.i.d.\ random variables $X_1,\dots ,X_k$. We also characterize all maximizing distributions. Using this result, we prove the Erdős Matching Conjecture for every fixed $k\ge 3$, all sufficiently large $s$, and every $n\ge k(s+1)$. More specifically, we show that in this range, the maximum number of edges in an $n$-vertex $k$-uniform hypergraph containing no $s+1$ pairwise disjoint edges is \[ \max\left\{ \binom{k(s+1)-1}{k}, \binom nk-\binom{n-s}{k} \right\}. \] Moreover, every extremal family consists either of all $k$-sets meeting a fixed $s$-set or of all $k$-sets contained in a fixed $(k(s+1)-1)$-set.