A Near-Optimal Linear Range for the Erdős Matching Conjecture

Abstract

The Erdős Matching Conjecture is governed by two competing ways of excluding $s+1$ disjoint edges: one may concentrate all edges on fewer than $k(s+1)$ vertices, or force every edge to meet a fixed $s$-set. We determine a near-optimal range in which the second construction is extremal. For every fixed $k\ge 2$, there is $s_0(k)$ such that, whenever $s\ge s_0(k)$ and $n\ge (k+1)s$, every $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ with $\nu (\mathcal{F})\le s$ satisfies \[ |\mathcal{F}|\le\binom nk-\binom{n-s}k, \] with equality only for the family of all $k$-sets meeting a fixed $s$-set. This improves the best previous general linear coefficient from $(5k-2)/3$ to $k+1$. In particular, the parameterized form of our argument further lowers the coefficient to $k+0.6$ for $k\ge 5$. Since the two conjectured constructions exchange asymptotic dominance at $n=({\rho }_k+o(1))s$ for a coefficient ${\rho }_k\in (k,k+1)$, our range lies less than one unit above the unavoidable barrier. We also prove a stability theorem showing that cover families are the only near-extremal configurations throughout this range. A key ingredient in our proof is a probabilistic rigidity statement which forces near-extremal fractional covers to be almost integral.