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

Source 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\ge1$ and every $0\le x\le1/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,\ldots,X_k$. We also characterize all maximizing distributions. Using this result, we prove the Erdős Matching Conjecture for every fixed $k\ge3$, 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.