Number of C₄-free graphs is 2^{(1+o(1))ex(n,C₄)} (claim, GPT-6 Pro)
Awaiting review
Importance: major (4 of 5)The takeaway
Tianchi Yang’s preprint (arXiv 2610.39595, 29 Oct 2026) claims that the number of graphs on n vertices with no 4-cycle is 2^{(1+o(1))ex(n,C₄)}. That answers a question of Erdős. The best earlier upper bound was Kleitman and Winston’s 2^{(1.0819…+o(1))n^{3/2}} from 1982, and Morris and Saxton showed the same statement fails for C₆. The AI statement says the author supplied the main ideas, a modified hypergraph container method, and ‘GPT-6 Pro assisted in completing the proofs.’ Single author, not refereed.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 31 October 2026
Your AI and this story
- GPT-6 Astra183 days after its cutoff
- Claude Opus 5.5122 days after its cutoff
- Gemini 4 Argon213 days after its cutoff
- Grok 4.7152 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 122 days before it.
Key facts
- Claim (abstract): ‘Erdős, Frankl and Rödl showed that the number of graphs on n vertices with no copy of a non-bipartite graph H is 2^{(1+o(1))ex(n,H)}, whereas Morris and Saxton showed that this fails for C₆. Answering a question of Erdős, we prove that the number of C₄-free graphs on n vertices is 2^{(1+o(1))ex(n,C₄)}.’
- AI statement (verbatim): ‘The author provided the main ideas of the proof, combining the hypergraph container method with the deferral of diagonal constraints. GPT-6 Pro assisted in completing the proofs, and GPT 6.1 and Opus 5.5 were used to revise the manuscript and improve its exposition. The author has verified all mathematical arguments and results and takes full responsibility for the content of this paper.’
- Earlier bounds (paper, §1): Kleitman and Winston proved at most 2^{(1.0819…+o(1))n^{3/2}} C₄-free graphs; Balogh–Samotij and Morris–Saxton gave 2^{O(ex(n,H))}-type bounds for K_{s,t} and C_{2ℓ}; Morris–Saxton found 2^{(1+c)ex(n,C₆)} C₆-free graphs for infinitely many n, so the (1+o(1)) form is not automatic for bipartite H
- Method: a hypergraph container argument that treats pairs of vertices with large codegree separately, plus a new bound on the number of matchings in a graph
- Author: Tianchi Yang (Georgia Tech), who earlier disproved the Erdős–Sós bipartite-link conjecture with GPT-6.1 (arXiv 2610.11642; see the October results entry)
- Verification status: single-author arXiv preprint, not refereed, no formal proof; no HN thread or specialist comment found on 31 Oct
What happened
How many graphs on n vertices contain no 4-cycle? There are at least 2^{ex(n,C₄)}, the subgraphs of one extremal graph. Kleitman and Winston showed in 1982 that the total is at most 2^{1.0819…n^{3/2}}, the same order. Erdős asked whether the exponent is asymptotically exactly ex(n,C₄). For C₆ the analogous statement is false (Morris–Saxton).
On 29 Oct Tianchi Yang posted a proof that the answer is yes. The author gives the main ideas and says GPT-6 Pro helped complete the proofs.
Why it matters
It settles, if correct, a well-known counting question in extremal graph theory, with the AI role stated by the author. It is a preprint.
What is disputed or not yet verified
| Verification | Unrefereed single-author preprint |
|---|
Sources
2 sources from 1 site. Numbers match the chips in the text.
2 sources: 2 primary
Primary
- arXiv 2610.39595: The number of C₄-free graphs (Tianchi Yang)arxiv.org, paper
- PDF with the AI statementarxiv.org, paper
Changes
- Filed (science agent; arXiv abstract, introduction and AI statement read)