--- id: "2026-10-27-erdos-lovasz-intersecting-covering-number-frankl-ai-construction" url: "https://postcutoff.com/e/2026-10-27-erdos-lovasz-intersecting-covering-number-frankl-ai-construction/" as_of: "2026-10-30T13:42:00+01:00" date: "2026-10-27" date_precision: day category: science importance: 4 confidence: medium status: [Awaiting review] verification: Preprint only sources: 2 editor: human editor human_review: null version: "2026-10-29" --- As of: 2026-10-30 13:42 CET. 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-27-erdos-lovasz-intersecting-covering-number-frankl-ai-construction/ # Erdős–Lovász covering-number problem: AI-found construction disproves Frankl's 1996 conjecture Full title: Erdős–Lovász problem on intersecting k-graphs with covering number k nearly settled: a construction 'found using generative AI tools' gives m(k) = k^k·exp(−k^(1/2+o(1))) and disproves the 1996 Frankl–Ota–Tokushige conjecture, with Peter Frankl as co-author "The maximum size of intersecting k-graphs with covering number k" (Peter Frankl, Jian Wang, Yaoran Yang, Yutong Zhang; arXiv 2610.37315, 27 Oct 2026) proves m(k) ≥ k^k·exp(−50√(k log k)) for log k ≥ 32, where m(k) is the largest intersecting k-uniform family with covering number k. Erdős and Lovász (1975) proved m(k) ≤ k^k. The best lower bound was (k/2)^(k−1) (Frankl–Ota–Tokushige, 1996), and the best upper bound is Zakharov's k^k·exp(−k^(1/2+o(1))) (2024). The two bounds now match up to the o(1) in the exponent, and the Frankl–Ota–Tokushige conjecture fails for large k. AI declaration: "The construction was found using generative AI tools." ## 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 ## Your AI and this story - GPT-6 Astra (training cutoff April 2026): 180 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 119 days after its cutoff - Gemini 4 Argon (training cutoff March 2026): 210 days after its cutoff - Grok 4.7 (training cutoff May 2026): 149 days after its cutoff ## Sources 1. [arXiv 2610.37315: The maximum size of intersecting k-graphs with covering number k (Frankl, Wang, Yang, Zhang)](https://arxiv.org/abs/2610.37315) (arxiv.org, paper) 2. [Zakharov, On the size of maximal intersecting families (CPC 2024; arXiv 2010.02541)](https://arxiv.org/abs/2010.02541) (arxiv.org, paper) ## Changes - 2026-10-29 (filed): Created (arXiv PDF of 2610.37315) ## Related - 2026-10-29: [AI-assisted results, 29 Oct 2026 (part 2)](https://postcutoff.com/e/2026-10-29-ai-assisted-results-october-29-listing-2/index.md) - 2026-10-21: [AI-assisted results in the 21 Oct 2026 arXiv listing](https://postcutoff.com/e/2026-10-21-ai-assisted-results-october-21-listing/index.md)