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\ge2$, there is $s_0(k)$ such that, whenever $s\ge s_0(k)$ and $n\ge(k+1)s$, every $\mathcal{F}\subseteq\binom{[n]}k$ with $ν(\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 lowers the best previous general linear coefficient from $(5k-2)/3$ to $k+1$. Since the two conjectured constructions exchange asymptotic dominance at $n=(ρ_k+o(1))s$ for a coefficient $ρ_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.

Disclosure

“Acknowledgement The first and third authors gratefully acknowledge the Fourth ECOPRO Student Research Program, held at the Institute for Basic Science (IBS) in summer 2026, for its support. The authors acknowledge the use of AI tools during the exploratory stage of this project. All mathematical arguments and proofs presented in the final manuscript were developed and rigorously verified by the authors. The authors take full responsibility for the content of the manusc”

PDF page 18

Classification

Brainstorming or outlining

Multiplier

2

Verified

2026-08-22T18:29:45.275879Z

Structural counts