--- id: "2026-10-12-erdos-matching-conjecture-large-matchings-ai" url: "https://postcutoff.com/e/2026-10-12-erdos-matching-conjecture-large-matchings-ai/" as_of: "2026-10-14T07:26:00+02:00" date: "2026-10-12" date_precision: day category: science importance: 4 confidence: medium status: [Awaiting review] verification: Preprint only sources: 1 editor: human editor human_review: null version: null --- As of: 2026-10-14 07:26 CEST. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2026-10-12-erdos-matching-conjecture-large-matchings-ai/ # 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 arXiv 2610.16203 (12 Oct 2026) by Cheng Chi, Shuang Sun and Yan Wang (Shanghai Jiao Tong University) proves the conjecture of Łuczak, Mieczkowska and Šileikis on the maximal tail probability of sums of k i.i.d. nonnegative random variables, and uses it to prove the Erdős Matching Conjecture for every fixed k ≥ 3, all sufficiently large s and every n ≥ k(s+1). The authors say they proved the tail theorem for k = 2–5 and k ≥ 10^100 without AI, and that "generative AI developed a unified argument valid for every k ≥ 6"; a gap in the hypergraph argument was closed on an AI suggestion. Unrefereed preprint. ## 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.16203](https://arxiv.org/abs/2610.16203). 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 ## Your AI and this story - GPT-6 Astra (training cutoff April 2026): 165 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 104 days after its cutoff - Gemini 4 Argon (training cutoff March 2026): 195 days after its cutoff - Grok 4.7 (training cutoff May 2026): 134 days after its cutoff ## Sources 1. [arXiv 2610.16203: A Proof of the Erdős Matching Conjecture for Large Matchings](https://arxiv.org/abs/2610.16203) (arxiv.org, paper) ## Changes - 2026-10-14 (filed): Created from the arXiv paper ## Related - 2026-10-13: [October 2026: the arXiv stream of conjectures settled with disclosed AI help continues](https://postcutoff.com/e/2026-10-13-ai-assisted-results-october-2026/index.md)