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≥1 and every 0≤ x≤1/k, we prove sup𝔼 X1≤ xℙ(X1+⋯+Xk≥1) =max{1−(1−x)k,(kx)k}, where the supremum is over nonnegative i.i.d.\ random variables X1,…,Xk. We also characterize all maximizing distributions. Using this result, we prove the Erdős Matching Conjecture for every fixed k≥3, all sufficiently large s, and every n≥ 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{ binomk(s+1)−1k, binom nk−binomn−sk }. 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.
Related
- How to Secure General Acceptance for a Matching? - Inverse Popular Matchings
- The importance of the change-of-variables integration technique in deriving the PDFs of important probability distributions
- Dynamical Chowla conjecture for polynomials of several variables
- Towards the Erdős matching conjecture for 4‐uniform hypergraphs: Stability and applications
- Tuza's Ryser-conjecture claim for four-partite hypergraphs with matching number two
BibTeX
@misc{chi2026proof,
title = {{A Proof of the Erdős Matching Conjecture for Large Matchings via Sharp Tail Probability for Sums of i.i.d. Nonnegative Random Variables}},
author = {Cheng Chi and Shuang Sun and Yan Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16203},
eprint = {2610.16203},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16203},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Proof of the Erdős Matching Conjecture for Large Matchings via Sharp Tail Probability for Sums of i.i.d. Nonnegative Random Variables
AU - Cheng Chi
AU - Shuang Sun
AU - Yan Wang
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16203
UR - https://arxiv.org/abs/2610.16203
AB - 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≥1 and every 0≤ x≤1/k, we prove sup_𝔼 X_1≤ xℙ(X_1+⋯+X_k≥1) =max{1−(1−x)^k,(kx)^k}, where the supremum is over nonnegative i.i.d.\ random variables X_1,…,X_k. We also characterize all maximizing distributions. Using this result, we prove the Erdős Matching Conjecture for every fixed k≥3, all sufficiently large s, and every n≥ 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{ binomk(s+1)−1k, binom nk−binomn−sk }. 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.
ER -