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≥2, there is s0(k) such that, whenever s≥ s0(k) and n≥(k+1)s, every ℱ⊆binom[n]k with ν(ℱ)≤ s satisfies |ℱ|≤binom nk−binomn−sk, 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≥5. Since the two conjectured constructions exchange asymptotic dominance at n=(ρk+o(1))s for a coefficient ρk∈(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.
Related
- Towards the Erdős matching conjecture for 4‐uniform hypergraphs: Stability and applications
- The Erdős Matching Conjecture for 4-uniform hypergraphs
- A Proof of the Erdős Matching Conjecture for Large Matchings via Sharp Tail Probability for Sums of i.i.d. Nonnegative Random Variables
- A geometrically linear approximation of min-max optimal matching
- A linear-in-q range of dimensions for the MDS conjecture over 𝔽q in odd characteristic
BibTeX
@misc{cao2026nearoptimal,
title = {{A Near-Optimal Linear Range for the Erdős Matching Conjecture}},
author = {Mengyu Cao and Hong Liu and Haixiang Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.19118},
eprint = {2608.19118},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.19118},
}
RIS
TY - UNPB
TI - A Near-Optimal Linear Range for the Erdős Matching Conjecture
AU - Mengyu Cao
AU - Hong Liu
AU - Haixiang Zhang
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2608.19118
UR - https://arxiv.org/abs/2608.19118
AB - 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≥2, there is s_0(k) such that, whenever s≥ s_0(k) and n≥(k+1)s, every ℱ⊆binom[n]k with ν(ℱ)≤ s satisfies |ℱ|≤binom nk−binomn−sk, 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≥5. Since the two conjectured constructions exchange asymptotic dominance at n=(ρ_k+o(1))s for a coefficient ρ_k∈(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.
ER -