Two plausible rules about forbidden patterns fail
How many edges can remain when a graph must avoid specified small patterns?
Extremal graph theory asks how dense a network can be while avoiding a prescribed pattern. Two durable conjectures proposed that complicated avoidance rules should compress: a finite family should be governed by one member, and a locally sparse forbidden graph should impose a predictable density exponent. The manuscript gives separate counterexamples to both expectations.1manuscript The interest is not only that the guesses fail, but that they fail for different structural reasons.
Pack edges while keeping a pattern out
A graph is a set of vertices joined by edges. Fix a smaller graph H as forbidden. The extremal number ex(n,H) is the largest number of edges an n-vertex graph can have without containing H anywhere inside it. The host may contain many extra vertices and edges; one hidden copy of H is enough to fail.1manuscript
Avoiding a family ℱ means avoiding every member at once. It is natural to expect that one especially restrictive member F ∈ ℱ controls most of the cost. The compactness counterexample constructs a family where the combined restriction is polynomially stronger than forbidding any one member.
Degeneracy describes a removal order: a graph is 2-degenerate if every nonempty subgraph has some vertex with at most two remaining neighbors. That sounds sparse, but the low-degree vertices can alternate between the two sides of a bipartite graph. The second counterexample turns that alternation into a long entropy obstruction.1manuscript2walkthrough
Add edges while avoiding a forbidden subgraph
ex(n,H) is the maximum number of edges in an n-vertex graph that contains no copy of H. A forbidden copy may sit inside a larger graph with extra edges.
This fixed edge order illustrates pattern emergence; it does not compute ex(n,C₄).
Conjecture one: one family member should control the family
Erdős and Simonovits developed compactness principles for extremal problems in 1982.4Erdős After removing elementary counterexamples, the corrected question asks whether every finite nonempty family ℱ whose members all contain cycles has some F ∈ ℱ and constant C with ex(n,F) ≤ C·ex(n,ℱ) for all sufficiently large n.1manuscript8Bloom
The new family is unusually clean: it is finite, every member is connected and bipartite, and every member contains a cycle. Yet
ex(n,ℱ) = O(n4/3−1/48) = O(n21/16),
while, for every individual F ∈ ℱ,
ex(n,F) = Ω(n4/3).1manuscript
Their ratio grows at least like a constant times n1/48. Therefore no individual member stays within a constant factor of the family extremal number.1manuscript
Why earlier family constructions were insufficient
Earlier rooted-power constructions can realize rational extremal exponents for finite families.6Bukh But a family-level exponent alone does not refute compactness: an individual member may inherit the same obstruction. Nor does supersaturation solve the coordination problem. Many copies can concentrate around a small root set, and homomorphic images can overlap in ways that invalidate a disjoint-template argument.2walkthrough
The compactness construction: quotient-proof templates
Start with C₄ and C₆, forcing every allowed host to have girth at least eight. Add two finite template families J and K, built from subdivisions of K3,2 and K3,3. Crucially, include every admissible color-preserving quotient that stays injective on each marked subdivision.1manuscript
That quotient closure is a robustness device. If two intended template pieces overlap accidentally inside a host, identify the template vertices sharing an image. The resulting image is still one of the forbidden quotients. The proof never silently assumes the witnesses are disjoint.2walkthrough
From four-step walks to a vertex cover
In an ℱ-free host, a maximum cut and minimum-degree pruning produce a bipartite subgraph B with minimum degree d. Because C₄ and C₆ are forbidden, related vertex pairs have unique common neighbors, and non-backtracking four-edge walks encode controlled common-center configurations.1manuscript
Counting those walks forces every vertex to participate in many two-center configurations—on the order of d12/N² in the relevant subgraph. J-freeness prevents the possible base triples from concentrating, bounding their total number. The vertices that do not center a three-center configuration form a small exceptional set of size O(N⁵/d13).1manuscript2walkthrough
K-freeness supplies the global step: two nonexceptional vertices cannot be adjacent, because their configurations plus that edge would form an admissible K quotient. Thus every edge meets the exceptional set—it is a vertex cover. Combining this with the girth-based maximum-degree bound yields d16 = O(N⁵), and therefore e(G) = O(n21/16).1manuscript
The quantifier trick: different dense witnesses for different members
Every individual member still needs a dense avoiding graph. The proof uses incidence graphs of symplectic generalized quadrangles, with about n4/3 edges and girth eight. For C₄, C₆, and every J-type member, choose quadrangles over fields of even characteristic; for K-type members, choose odd characteristic.1manuscript
No one incidence graph is claimed to avoid the whole family—that would contradict the family upper bound. The witness is allowed to depend on F. Bounded spacing between powers of 2 or 3, followed by isolated-vertex padding, extends the construction from prime-power sizes to every sufficiently large n.2walkthrough This changing-witness quantifier is the heart of the separation.
The whole family coordinates two complementary obstructions. Each single member can be evaded by choosing the right field characteristic, but no single dense witness evades them all.1manuscript2walkthrough
Conjecture two: degeneracy should determine the exponent
Erdős conjectured that every fixed bipartite r-degenerate graph H satisfies ex(n,H) = O(n2−1/r).1manuscript9Bloom For r = 2, the predicted ceiling is O(n3/2). Positive results covered important cases, including graphs with one bipartition class of maximum degree at most r and r-degenerate blow-ups of trees.5Alon7Grzesik
But 2-degeneracy does not mean one side has degree at most two. A degeneracy ordering can remove low-degree vertices alternately from the two bipartition sides. Greedy embedding and dependent random choice can find useful parent pairs on one side, but the later pairs needed on the other side may be incompatible. At density around n1/2, imposing two neighborhood constraints leaves only a constant-size reservoir.2walkthrough
The degeneracy construction: an entropy staircase
Build one enormous but fixed graph H in layers. Start with V₀. For each unordered pair of vertices in Vi−1, add one child in Vi adjacent to its two parents. Layer parity makes H bipartite. In any nonempty subgraph, a vertex in the highest occupied layer has at most its two parent-neighbors, proving 2-degeneracy.1manuscript High-degree vertices occur on both color classes, so the example lies outside the known one-sided bounded-degree case.
The host takes two copies of the binary cube {0,1}m, joins opposite-side words within Hamming distance τm, and independently retains each vertex with probability 2−βm. Parameters are chosen so the thinned graph retains more than n3/2+ε edges.1manuscript
Low entropy disappears; high entropy overspends
For a proposed embedded child layer, coordinate profiles count how much conditional entropy the children have given their parent pairs. Random thinning eliminates all injective low-entropy child arrays with high probability. Repeated child words may be allowed while counting possibilities, but the independent retention probability is applied only after restricting to distinct children—a small order-of-operations point that prevents a false probability estimate.2walkthrough
Any surviving embedded layer must therefore have high conditional entropy. Yet every child is Hamming-close to both parents. A sharp binary entropy inequality bounds that conditional entropy by a constant plus half the increase in a marginal entropy potential Si, where 0 ≤ Si ≤ 1.1manuscript Each successful layer would force Si − Si−1 > w/2 for an explicit w ≈ 0.003728.2walkthrough
Choose a fixed number of layers s with sw/2 > 1. The smallest permitted depth is already at least 537, so H is huge but finite and independent of the eventual host size.2walkthrough An embedding would make a potential contained in [0,1] rise by more than 1—impossible. A second-moment estimate simultaneously guarantees enough retained edges.1manuscript
Local two-parent structure does not make the embedding constraints one-sided. Alternating layers repeatedly demand fresh conditional entropy until a globally bounded potential is exhausted.2walkthrough
Two proof maps, one page
Compactness track
- Close two subdivided templates under admissible quotients so incidental overlaps cannot escape the forbidden family.1manuscript
- Count non-backtracking four-step walks; J-freeness controls concentrated extensions and makes the bad set small.1manuscript
- Use K-freeness to turn that bad set into a vertex cover, giving the n21/16 family upper bound.1manuscript
- For each member separately, choose an even- or odd-characteristic generalized-quadrangle witness with Ω(n4/3) edges.1manuscript
Degeneracy track
- Build a fixed connected bipartite graph by repeatedly adding one child for every parent pair; highest-layer vertices prove it is 2-degenerate.1manuscript
- Thin a bipartite Hamming-distance graph at parameters inside a small positive entropy window.1manuscript
- Use profile counting to exclude low-entropy injective child arrays at every layer.2walkthrough
- Show any hypothetical embedding forces a bounded entropy potential to increase at every layer, then preserve enough edges by a second-moment bound.1manuscript
Technical layer · the two exponent calculations
Compactness. Four-path counting gives a d12/N² lower contribution per bad vertex. The J template bounds eligible triples by O(N³/d), hence |Bad| = O(N⁵/d13). Girth eight gives Δ(B) = O(N/d²). Since Bad is a vertex cover, Nd ≤ 2e(B) ≤ 2|Bad|Δ(B) = O(N⁶/d15), so d16 = O(N⁵). The minimum-degree reduction then yields e(G) = O(nN5/16) = O(n21/16).1manuscript2walkthrough
Degeneracy. Set τ = (√3−1)/2. The density and avoidance thresholds leave a positive window w ≈ 0.00372800177. Choosing β at its midpoint gives an explicit ε = w/[8(1−β)] ≈ 0.0043665 in the walkthrough’s parameterization.2walkthrough The theorem itself only needs fixed c,ε > 0.1manuscript
Exact scope and significance
Theorem 1.1 constructs one finite family of connected bipartite cyclic graphs with a polynomial n1/48 separation between the family extremal number and every singleton extremal number.1manuscript It refutes the corrected compactness conjecture, not every compactness phenomenon in extremal graph theory.
Theorem 1.2 constructs one fixed connected bipartite 2-degenerate graph H and constants c,ε > 0 such that ex(n,H) ≥ cn3/2+ε for every sufficiently large n.1manuscript It disproves the proposed general exponent for r-degenerate bipartite graphs. It does not invalidate the established positive subclasses.5Alon7Grzesik
The released Comparator manifests name the quantitative compactness counterexample and the two-degenerate extremal counterexample as formal targets.3formal artifact OpenAI describes a broader model–researcher–formalization review process.10announcement These are meaningful validation artifacts, not independent community acceptance.
Is the claim overhyped?
My calibrated verdict: two substantial counterexamples with unusually explicit mechanisms; the headline is fair when it preserves that they are separate constructions with carefully bounded scope.
The finite compactness family is polynomially stronger than each of its members.
The manuscript proves the exponents 21/16 for the family and 4/3 for every member, a gap of 1/48.1manuscript The quantitative comparison is a named formal target.3formal artifact
A fixed connected bipartite 2-degenerate graph can have extremal exponent above 3/2.
That is Theorem 1.2 and the target `twoDegenerateExtremalCounterexample`.1manuscript3formal artifact
Compactness principles and degeneracy bounds are generally useless.
No. Both topics retain strong positive theorems. The counterexamples defeat these universal formulations, not the surrounding methods or special classes.4Erdős5Alon7Grzesik
Formalization eliminates the need for graph-theory review.
Experts still need to audit the formal definitions, finite-geometric inputs, asymptotic quantifiers, entropy estimates, and correspondence between formal and prose theorems.3formal artifact10announcement
Full bibliography
10 fully annotated sources
- 01 · primary manuscript
OpenAI. Ten Advances in Mathematics and Theoretical Computer Science — Chapter 10, abstract, Theorems 1.1–1.2, and §§2–8, PDF pp. 236–249. Primary source for both constructions, exact exponents, and theorem scope. ↩
- 02 · reasoning walkthrough
OpenAI. Reasoning Walkthroughs — Chapters 11–12, §§11.1–11.9 and §§12.1–12.9, PDF pp. 51–58. Explains failed routes, quotient closure, path counting, field-dependent witnesses, and the entropy-potential counterexample. ↩
- 03 · formal certificate
OpenAI. CompactnessAndDegeneracy.lean and Comparator challenges — quantitativeCompactnessCounterexample, not_erdos_180, twoDegenerateExtremalCounterexample, and not_erdos_146; commit e62211d. Released Lean targets for the quantitative compactness separation and 2-degenerate counterexample. ↩
- 04 · peer-reviewed predecessor
Paul Erdős and Miklós Simonovits. Compactness results in extremal graph theory — Combinatorica 2(3), 275–288 (1982). Primary source for the compactness program; the manuscript addresses its corrected cyclic connected-bipartite form. ↩
- 05 · peer-reviewed predecessor
Noga Alon, Michael Krivelevich, and Benny Sudakov. Turán numbers of bipartite graphs and related Ramsey-type questions — Combinatorics, Probability and Computing 12, 477–494 (2003), Theorem 3.5. General upper-bound context and positive results when one bipartition side has bounded degree. ↩
- 06 · peer-reviewed predecessor
Boris Bukh and David Conlon. Rational exponents in extremal graph theory — Journal of the European Mathematical Society 20, 1747–1757 (2018). Rooted-power family constructions that inform the compactness templates. ↩
- 07 · peer-reviewed predecessor
Andrzej Grzesik, Oliver Janzer, and Zoltán Lóránt Nagy. The Turán number of blow-ups of trees — Journal of Combinatorial Theory, Series B 156, 299–309 (2022). A substantial positive class satisfying the conjectured degeneracy exponent. ↩
- 08 · authoritative reference
Thomas F. Bloom. Erdős Problem #180 — problem statement and historical notes. Community problem record for compactness. ↩
- 09 · authoritative reference
Thomas F. Bloom. Erdős Problem #146 — problem statement and historical notes. Community problem record for the degeneracy conjecture. ↩
- 10 · official announcement
OpenAI. Ten advances in mathematics and theoretical computer science — “How the results were developed” and “Verification” sections. Used only for OpenAI’s process description, not theorem correctness. ↩