Erdős Matching Conjecture (1965) proved for every fixed k and all large s, via a sharp tail bound whose k ≥ 6 cases generative AI completed
Awaiting review
Importance: major (4 of 5)The takeaway
Three Shanghai Jiao Tong mathematicians prove Erdős’s 1965 matching conjecture for all n once the matching size is large, by first settling a probability conjecture of Łuczak, Mieczkowska and Šileikis. Their disclosure credits AI with the unified argument for k ≥ 6 and with closing a gap.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 14 October 2026
Your AI and this story
- GPT-6 Astra165 days after its cutoff
- Claude Opus 5.5104 days after its cutoff
- Gemini 4 Argon195 days after its cutoff
- Grok 4.7134 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 104 days before it.
Key facts
- Paper: ‘A Proof of the Erdős Matching Conjecture for Large Matchings via Sharp Tail Probability for Sums of i.i.d. Nonnegative Random Variables’, Cheng Chi, Shuang Sun, Yan Wang (SJTU), arXiv 2610.16203 [math.CO], 12 Oct 2026
- Erdős (1965): the maximum number of edges of an n-vertex k-uniform hypergraph with no s+1 pairwise disjoint edges is max{C(k(s+1)−1, k), C(n,k) − C(n−s,k)} (clique vs cover construction)
- Result 1 (probability): for every k ≥ 1 and 0 ≤ x ≤ 1/k, sup over i.i.d. nonnegative X_i with E X_1 ≤ x of P(X_1 + … + X_k ≥ 1) equals max{1 − (1 − x)^k, (kx)^k}, with all maximizing distributions characterized; previously known for x < 1/(2k−1) (k ≥ 5), extended by Frankl–Kupavskii to x ≤ 3/(5k−2)
- Result 2 (hypergraphs): the Erdős Matching Conjecture for every fixed k ≥ 3, all sufficiently large s, and every n ≥ k(s+1), with the extremal families characterized
- AI use: ‘For Theorem 1.2, the authors independently developed the proof framework and proofs for k = 2, 3, 4, 5 and k ≥ 10^100 without any AI assistance. Building on the authors’ proof framework, generative AI developed a unified argument valid for every k ≥ 6 in early September 2026, thereby resolving the remaining cases’
- AI use (Theorem 1.4): the initial argument ‘left a gap of width o(s) in the range of n around n = ρ_k s … This gap was closed following a suggestion of using weak convergence, given by generative AI (see Lemma 8.3 and Section 8.2)’; the authors ‘independently checked all AI-generated arguments in detail’. The model is not named
What happened
On 12 Oct 2026 Cheng Chi, Shuang Sun and Yan Wang posted arXiv 2610.162031. Erdős asked in 1965 for the largest k-uniform hypergraph on n vertices without s+1 disjoint edges, and conjectured that one of two constructions (a clique on k(s+1)−1 vertices, or all edges meeting a fixed s-set) is always best. The conjecture had been proved for n large compared with ks and in special cases, but not in general.
The paper first settles a conjecture of Łuczak, Mieczkowska and Šileikis on how likely a sum of k i.i.d. nonnegative random variables with small mean is to reach 1, and then derives the Erdős Matching Conjecture for every fixed k ≥ 3 once s is large enough, across the whole range n ≥ k(s+1).
The disclosure is unusually specific about the division of labour: the humans proved the tail theorem for k = 2–5 and k ≥ 10^100, and “generative AI developed a unified argument valid for every k ≥ 6 in early September 2026, thereby resolving the remaining cases”. An AI suggestion (weak convergence) also closed a gap of width o(s) near the crossover point of the two constructions. The model is not named.
No expert reactions were found on 14 Oct (web search; X not searched directly).
Why it matters
The Erdős Matching Conjecture is one of the central open problems of extremal set theory. Here AI filled in a precise, bounded part of a human programme, the infinite middle range of k, rather than supplying the strategy. The k ≥ 10^100 boundary of the human proof shows how much that middle range was worth.
What is disputed or not yet verified
| Verification | Unrefereed preprint; authors checked AI arguments |
|---|
Sources
1 source from 1 site. Numbers match the chips in the text.
1 source: 1 primary
Primary
Changes
- Filed from the arXiv paper