Erdős–Lovász covering-number problem: AI-found construction disproves Frankl’s 1996 conjecture
Awaiting review
Importance: major (4 of 5)The takeaway
Erdős and Lovász showed in 1975 that an intersecting family of k-sets that needs k points to cover it has at most k^k members. The best constructions stayed near (k/2)^(k−1) for 30 years. In 1996 Frankl, Ota and Tokushige conjectured that m(k) < (ck)^k for some c < 1. A 27 Oct preprint by Peter Frankl, Jian Wang and two Sichuan University students builds families of size k^k·exp(−50√(k log k)). With Zakharov’s 2024 upper bound this pins m(k) down to k^k·exp(−k^(1/2+o(1))) and refutes the 1996 conjecture. The authors write that ‘the construction was found using generative AI tools’. They do not name the models.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 29 October 2026
Your AI and this story
- GPT-6 Astra180 days after its cutoff
- Claude Opus 5.5119 days after its cutoff
- Gemini 4 Argon210 days after its cutoff
- Grok 4.7149 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 119 days before it.
Key facts
- Main theorem (abstract): ‘it is proved that for all k > e^32, m(k) ≥ k^k exp(−50√(k log k)). Together with Zakharov’s upper bound [12], this implies m(k) = k^k exp(−k^(1/2+o(1)))’
- Conjecture refuted (Conjecture 1.4 in the paper, Frankl–Ota–Tokushige, JCTA 1996): ‘There is an absolute constant c, with 1/2 < c < 1, such that m(k) < (ck)^k for all sufficiently large integers k.’ The paper says Theorem 1.5 ‘disproves Conjecture 1.4 for all sufficiently large k’. Frankl, a co-author of that conjecture, is the first author
- History as the paper recounts it: Erdős–Lovász (1975) proved m(k) ≤ k^k and m(k) ≥ ⌊k!(e − 1)⌋; Lovász conjectured the latter was exact; Frankl, Ota and Tokushige disproved that for k ≥ 4 with (k/2)^(k−1); upper bounds improved by Tuza, Arman–Retter, Frankl and Zakharov (CPC 2024). Small values: m(3) = 10 (Lovász), 42 ≤ m(4) ≤ 64
- AI declaration (verbatim): ‘The construction was found using generative AI tools. The authors verified the proofs and reworked the arguments to clarify the mathematical ideas underlying the construction and to provide a more conceptual exposition.’ No model is named
- Construction: a random intersecting k-graph built from an auxiliary hypergraph of classes of edges in edge-disjoint perfect matchings of K_2n, with many minimum covers (Theorem 1.6), then glued to a smaller Erdős–Lovász-type family
- Status: unrefereed preprint, no formalization; no expert comment found as of 29 Oct
What happened
A family of k-element sets is intersecting if any two members meet, and its covering number is the size of the smallest set that meets every member. Since every member is itself such a set, the covering number of an intersecting family is at most k. Erdős and Lovász proved in 1975 that families reaching the maximum, τ = k, have at most k^k members. How large they can actually be has been studied since. For thirty years the best constructions were near (k/2)^(k−1). In 1996 Frankl, Ota and Tokushige conjectured that the truth is (ck)^k with c < 1.
The new preprint gives a random construction of size k^k·exp(−50√(k log k)). Dmitrii Zakharov had shown in 2024 that m(k) is at most k^k·exp(−k^(1/2+o(1))), so the two bounds now agree up to the o(1) in the exponent. The authors write that the construction itself was found with generative AI tools, and that they verified and rewrote the arguments.
Why it matters
The question was posed by Erdős and Lovász in a 1975 problem paper, and Peter Frankl is one of the best-known people working on intersecting families. The result settles the order of magnitude of m(k) and refutes a conjecture Frankl co-authored. It is another case in which a model found a construction that experts had not expected. The paper does not name the models or say how much prompting was involved.
What is disputed or not yet verified
| Verification | Unrefereed arXiv preprint |
|---|
Sources
2 sources from 1 site. Numbers match the chips in the text.
2 sources: 2 primary
Primary
Changes
- Filed (arXiv PDF of 2610.37315)