A counterexample to the Erdős triangle–four-cycle asymptotic

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer ↗

Version 1 / Nov 20, 2026 / CC BY 4.0

Abstract

We construct an infinite family of finite simple graphs containing neither a triangle nor a four-cycle. Their edge counts exceed the conjectured leading asymptotic in Erdős Problem 573 by a fixed positive factor. For every positive integer hh, put q=659hq=659^h. The graph GqG_q has nq=(1307/659)q2−qn_q=(1307/659)q^2-q and eq=(428875/6592)q3−(658/659)q2e_q=(428875/659^2)q^3-(658/659)q^2. Its limiting ratio to (nq/2)3/2(n_q/2)^{3/2} is 1.0000452143352195…1.0000452143352195\ldots. The construction joins 47 affine three-part pieces along a common root part. A multiplicative partition of reciprocal field labels excludes four-cycles across the pieces, and an additive restriction retains enough internal edges while excluding triangles.

Author comments: TeX edition of the manuscript accompanying Justin Sun Prize submission JSP-000463. Pinned manuscript and Lean proof materials: https://github.com/Ghuffy1/erdos-573/tree/75b87c642d5800f5ce45564236ecf065820c9eb1

Provenance statement

OpenAI Codex assisted with construction search, proof development, formalization, computational checks, and exposition. The accompanying Lean proof verifies the asymptotic disproof. This TeX edition preserves the mathematics of the pinned Markdown manuscript.

References

No bibliography entries.

Version history

  1. v1 · 5 pagesSubmitted by Liam KruerTeX edition of the manuscript accompanying Justin Sun Prize submission JSP-000463. Pinned manuscript and Lean proof materials: https://github.com/Ghuffy1/erdos-573/tree/75b87c642d5800f5ce45564236ecf065820c9eb1CurrentNov 20, 2026