Cyclic Erdős–Simonovits extremal-graph compactness

Must a finite family of connected cyclic bipartite forbidden graphs have essentially the extremal growth of one member? The Erdős–Simonovits compactness question compares simultaneous avoidance with the separate extremal numbers.

Why it matters and what counts as progress

Why it matters: A polynomial gap would show that joint forbidden-subgraph behavior cannot always be reduced to the hardest individual member.

What counts as progress: Construct a family with a polynomial separation between joint and individual extremal numbers or prove compactness under additional restrictions.

How the problem developed

1982 · Conjecture [1]
Paul Erdős and Miklós Simonovits Introduced a compactness conjecture for extremal graph families; the original unrestricted formulation admits simple counterexamples.
6 Aug 2026 · Reported counterexample [2]
OpenAI Reported a counterexample even for the repaired version requiring each forbidden graph to contain a cycle: the family has aggregate extremal number O(n^(4/3−1/48)) although each member individually requires order n^(4/3).

AI contribution

Ten Advances in Mathematics and Theoretical Computer Science

OpenAI

A finite family of connected bipartite graphs, each containing a cycle, has joint extremal number O(n^(4/3−1/48)), while every member has extremal number Ω(n^(4/3)). This refutes the substantive cyclic version of the Erdős–Simonovits compactness claim.

AI involvementAI-led

ImportanceMajor

Technical verificationFormal (Lean 4.35.0-rc2 with Mathlib; Comparator, Lean and NanoDa kernels + human)

Human understandingFull